Amazing Refactoring Challenge

Alan Hensel put up an interesting refactoring challenge: Refactor the GOTO-heavy "AMAZING" program, originally written in Minimal Basic style TRS-80 BASIC.

His challenge is at http://www.mindspring.com/~alanh/refactoring/challenge.html

I've created a dumb Ruby transliteration of William Wake's Java version of this challenge (including the two unit tests). You can download it from http://silkandspinach.net/blog/2005/09/amazing_refacto.html -- KevinRutherford, 6-sep-05

And posted to the Yahoo XP group at http://groups.yahoo.com/group/extremeprogramming/message/64266 along with some responses on how one could or should do this with more automated regression testing.

In the spirit of this effort, I posted a page (http://sluug.org/~jeff/amazing/AmazingRefactoringChallenge.html) with a minimal Java conversion of the original program:

 http://sluug.org/~jeff/amazing/MazeGenerator.java

Having converted all the GOTOs to a loop, with a switch-case statement, it's up to the reader to refactor it into something less like horribly rotting code!

Hey; I put in *lots* of comments to document the mess, so what more can you ask for? And yes, the mess works: It produces mazes, and most of the time they're correct (one entrance; one exit). -- JeffGrigg

In summary, this is the Java program to refactor: http://sluug.org/~jeff/amazing/MazeGenerator.java.

What's our motivation for refactoring this mess?

Well, aside from the sheer joy of the educational experience, our fictitious "QA department" has reported some *BUGS* lurking in this mess of code:

Attempting to create a "one by one" maze hangs the system. (The program runs forever.)
Sometimes Mazes have no exit. (Hint: All mazes one wide (H=1) and any length (V>1) have no exit.) (Hint: Has been seen in a small number of 3x3 and 3x2 mazes. "Hard to reproduce.")

Anyone up to the challenge? ;->

Maybe.:-). After much hackery, see http://mysite.freeserve.com/phade/maze.java. Disclaimer: it doesn't work. It doesn't even compile. I don't know how (see below). I think it's easy to fix, I just need to learn more about Java. I do believe it's basically correct, and it has no GOTOs (faked via switches or otherwise).

Refactoring notes:

First step seems to be to remove the GOTOs that just GOTO somewhere else... e.g.

  case 590: // Move Left
     nextline = 940;
     break;

Next, remove the GOTO 990 (because it just drops through and 990 isn't used elsewhere and all cases in 990 set nextline to something)

Then inline case 380, 480, 560, 670, 750, 849, 910, 1050 since they're only used once.

Put 990 back :-( because 940 duplicates the code - remove the code from 940 and replace with a GOTO 990)

Inlining 1050 means both branches in 1020 now go to 1060 - and they are the only mentions of 1060. So replace the gotos with a drop through and remove case 1060

Similarly, 1090, 1120 and 1130 can be combined (with a bit of care 'cos there's an extra clause about creating exits)

Inline 1150 (part of that "make exit" clause) and then 1180 (more of same)

Then there's code like this (in case 600):

        if (S-1 == 0)             // At top of maze?
            nextLine = 790;       //  Yes: Can't go Up.
        else if (W[R][S-1] != 0)  // Been in the cell above us?
            nextLine = 790;       //  Yes: Can't go Up.
        else if (R == H)          // At right border?
            nextLine = 720;       //  Yes: Can't go Right (or Left. Up is OK.)
        else if (W[R+1][S] != 0)  // Been there?
            nextLine = 720;       //  Yes. (same)
        else

Where the first condition is a guard for the second. So change to

        if ((S-1 == 0) || (W[R][S-1] != 0))             // At top of maze or been in the cell above?
            nextLine = 790;       //  Yes: Can't go Up.
        else if ((R == H) || (W[R+1][S] != 0))          // At right border or been in the cell to the right?
            nextLine = 720;       //  Yes: Can't go Right (or Left. Up is OK.)
        else

... and now can inline 790 and 720.

Similar code involving 880 allows that to be inlined too. There's a CodeSmell because I think there should be another similar case here, but it's not obvious yet..

Case 600 is now horribly big, if a little better structured...

Case 270 contains similar code, clean up the conditions too... and inline 350 and 430 and 530

Move the body of 1200 out of the switch and while() (since it's always the last thing done).

We can't inline 600 straight away because 1020 uses it - but I think this is merely an optimization; if 1020 went to 270 like all similar code it would end up at 600 anyway (because we know we can't go left), but I'm not confident enough to make that change yet...Later: I did.

210 and 260 form a do... while () loop, but this is a day off for me and SWMBO is getting impatient ... more later.

Note that 1060 (now incorporated in 1050), 1130 contain near-equivalent code to 990, there's a CodeSmell here...in fact, can make all of the moves end with the same code as 990 (after factoring out the move-to-next-cell code and calling it in a few places)

Move the code dealing with the maybe-an-exit-at-the-last-row out of each clause of 270, because it's the same code (going to different places, but the same code). After that, the code gets a lot simpler and we can inline all the moves (well, more accurately, split them out into methods and call them from one or two place).

After this, and some other minor adjustments of the cases that don't actually move from the current cell, all paths through the big if end up at 990. So inline that. And note it's really a do-while loop, so change it into one.

Now all of the states of the state machine are gone. Remove the litter left behind. More or less done.

Most of the variables are in the wrong place (need to be static, rather than in the generator function). Leave that for later... Next, time to make it compile again :-) and then I think so we can write some more intention revealing methods? Other ideas?

Of course, it would help testing if I knew how to run a Java program :-) Anyone able to give me concise instructions? (Linux) ...

-- PaulHudson

Amazing what you can do when you have the necessary compiler. ;-> I fixed the syntax errors in your effort, and posted it here:

 http://sluug.org/~jeff/amazing/PaulHudsonMaze.java

It still works:

I'm pretty stunned it works. And feeling fairly smug :-) -- PaulHudson

 <CLS>
 AMAZING
 COPYRIGHT BY
 CREATIVE COMPUTING  MORRISTOWN, NEW JERSEY
 :--:--:--:--:--:--:--:  :--:--:
 I                       I     I
 :  :--:--:--:  :--:--:--:  :  :
 I     I     I              I  I
 :--:  :  :  :--:--:--:--:--:  :
 I  I     I     I           I  I
 :  :--:  :--:  :  :--:--:  :  :
 I  I     I  I  I     I     I  I
 :  :  :--:  :  :  :  :--:--:  :
 I  I  I     I  I  I     I     I
 :  :  :--:  :  :  :--:  :  :  :
 I  I     I  I     I     I  I  I
 :  :--:  :  :  :--:  :--:  :  :
 I        I  I     I  I     I  I
 :--:--:--:  :--:--:  :  :--:  :
 I  I        I        I  I  I  I
 :  :  :  :--:  :--:--:  :  :  :
 I  I  I        I        I  I  I
 :  :  :  :--:--:  :--:--:  :  :
 I     I        I        I     I
 :--:--:--:--:--:--:--:  :--:--:

Actually, I was hoping that someone would build some tests, and then do refactoring, protected by the tests. -- JeffGrigg

Yeah, I suspected that, but that didn't sound as much fun. On the other hand, who needs tests? :-) (Semi-seriously, it was all pretty mechanical stuff. Had I had a decent refactoring browser to help me be more confident I wasn't making typos, I'm not sure how much I would have got from tests).

In this case, tests are interesting, because of the random number generator. I'm pretty sure my version would produce the same mazes as the original if fed a "canned" sequence of random numbers. I think Alan's version (which I didn't even discover existed until after I'd done mine) would not, because he's changed the way it decides where to move next (compatibly in that the probabilities are the same, but the actual directions for any given choice may not be the same even if the "random" numbers were the same.