This is a multi-part series. The first in the series is here.
Tower of Hanoi — With Rule Disks (and no stack)
The first passes at the Tower of Hanoi algorithm were all done with the algorithm being a recursive call on the stack. This is ‘true’ as an algorithm, but comes off as a bit unnatural for humans.
But it also has a problem in that the algorithm can not be ‘suspended’ in mid activity unless the language allows a feature (called a continuation) that can suspend the stack itself. Although Ruby is multi-threaded and running two threads works in RubyShoes, Rails does not work either with a stateful server (and multiple threads) or with continuations. At the end of each controller dispatch the session or the database has to have persisted all state. So we need to do something like formalizing the state of the Disks and Towers to make the Tower of Hanoi work with Rails.
Also, the Smalltalk code in this section was among the most ‘closure-oriented’, so this helps show how that maps to Ruby.
You aren’t capitalizing right?
Before continuing into the code, people should realize I actively object to Ruby’s choice to have only one ‘word’ delimiter by convention. See my article Ruby Naming Convention Failure for details and the naming conventions I use, especially for methods. But the quick summary is:
I use CamelCase for combining words into a ‘part’ of a method name or variable name
I use an underscore as a placeholder for the parameters of the method
I use an underscore to break up a phrase into logical parts
If Ruby supported some other word delimiter than underscore (say hyphen “-” or “:”), I would be agnostic to dropping the CamelCase, but without that second word delimiter, dropping CamelCase is a losing proposition in expressiveness. In a team setting we might have to discuss this, but in this case this is my code alone… and my standard actually makes it easier to convert to-from Smalltalk, Ruby, Flex, Java, etc. The standard works cleanly with all of them.
To migrate to the Rules version of the HanoiTower, it is easiest to start with the Disks themselves.
A Rules based HanoiDisk just needs to be able to say “Can I move somewhere” and “If so, where”. It does this in collaboration with the Tower. “@tower” is now an instance variable that every Disk has set when it is created. By using an instance variable, it is cleaner than using class variables (we can have multiple towers at the same time) and it works under Ruby serialization/marshalling.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Among the interesting things with the new RulesHanoiDisk is the extensive use of Blocks. By using Blocks, we can iterate over the collection of stacks without creating new collections. The Disk and the Tower collaborate to create custom iterators with minimal code. See RulesTowerOfHanoi for the example.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69