From: Mark Day <mday@...>
Date: 2007-05-11T12:48:58+09:00
Subject: Re: Object-oriented solution to Tower of Hanoi

--Apple-Mail-1-832166813
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed

On May 10, 2007, at 5:34 PM, Daniel Waite wrote:

> Anyway, here's my (long) object-oriented version of the ToH. Tell me
> what you think. Oh, and if you have suggestions on where someone NOT
> interested in going to college can do to learn the math necessary to
> start programming "for real,"  please share! Thanks!

Good choice of a relatively simple problem to solve.  (I'm a newbie  
to Ruby, too.  I enjoyed putting a solution together.  Thanks!)   
Three concepts come to mind in this case:
* Understanding the problem (requirements)
* Abstraction
* Recursion

Understanding the problem (requirements):
It's important to understand what you're trying to solve.  I don't  
mean how to solve it, but what is the goal?  What are the  
requirements for your solution?  Just saying, "solve the Towers of  
Hanoi" is too vague.  Do you want to just print out the list of  
movements from one tower to another?  Do you want to print out which  
ring it is that's moving?  Do you want to ensure that the move is  
legal?  And what does "legal" mean anyway?  (No ring may be placed on  
top of a smaller ring.)  In the code below, I chose to print out the  
individual moves along with the ring being moved.  I chose not to  
verify that every move is legal.

Abstraction:
Distill things down to their essence.  You don't have to be literal  
by modeling every object in the real world.  In fact, many  
interesting problems don't map well (if at all) to the real world.  I  
mention this because you have a "hand" object in your code, and that  
seemed like too much detail.  An object for the game as a whole, and  
objects for each tower/peg, and for each disc/ring are all  
reasonable.  You'll notice in my solution below, I didn't create a  
separate class for rings/discs; all I really care about is indicating  
relative size, so a number from 1 to N is good enough, which means I  
can use an ordinary integer.

Recursion:
Recursion is defining a solution based on a similar, but smaller  
version of the same problem.  You define how the larger problem in  
terms of the smaller problem, and define what the smallest problem is  
(and how to solve it -- which is often trivial).  (There's also  
"mutual recursion" which involves defining several routines in terms  
of each other.  It's a more general form of recursion.  Feel free to  
Google it.)

Here's how I thought about the problem.  I have a Hanoi object which  
represents the entire game.  Hanoi contains three Towers.  Each Tower  
has some rings, in a specific order.  I represent rings as numbers in  
the range 1 to N, with 1 being the smallest ring, and N being the  
largest ring.  I can remove (pop) a ring from a Tower, place (push) a  
ring on a Tower, and see how many rings are on a Tower.  Towers also  
have names, so I can identify them in the printed output.  Hanoi has  
three Towers, with all of the rings starting on the left Tower, and  
all of the rings in order from the largest on bottom to the smallest  
on top.  A fundamental operation is to move some number of rings from  
one Tower to another.  Solving the puzzle is as simple as moving all  
of the rings from the left Tower to the right Tower.

How does recursion fit in?  If I want to solve a puzzle with 5 rings,  
that means I need to move 5 rings from left to right.  In order to do  
that, I need to temporarily move the top 4 rings from the left to the  
middle, move the bottom ring from left to right, and then move the 4  
rings from the middle to the right.  Notice how I described solving  
the 5 ring puzzle in terms of solving the 4 ring puzzle.  Moving 4  
rings involves moving the top 3 rings to an intermediate Tower,  
moving the bottom of the 4 rings to its destination, and moving the  
top 3 rings to the destination.  And so on.  Moving one ring is  
trivial -- just move it directly.

Here's my code.  Comments and critiques are welcome.  Note that I  
didn't actually check to see whether a given move is legal; I'm a  
trusting person.  ;-)  But if you want to do that, Tower#push would  
be a good place (and Tower#pop, if you want to make sure you don't  
try to take a ring from a Tower that has no rings).

Hope this helped.

-Mark

#
# Print out the moves to solve the Towers of Hanoi.
# Supply the number of rings as the one and only command line argument.
#

class Tower
	def initialize(name, rings)
		@name = name
		@rings = rings
	end
	
	def to_s
		@name
	end
	
	def pop
		@rings.pop
	end
	
	def push(ring)
		@rings.push ring
	end
	
	def height
		@rings.length
	end
end

class Hanoi
	def initialize(rings)
		@left = Tower.new("left", [*(1..rings)].reverse)
		@middle = Tower.new("middle", [])
		@right = Tower.new("right", [])
	end
	
	def move(rings, from, to, other)
		if rings == 1
			ring = from.pop
			puts "Move ring #{ring} from #{from} to #{to}"
			to.push ring
		else
			move(rings-1, from, other, to)
			move(1, from, to, other)
			move(rings-1, other, to, from)
		end
	end
	
	def solve
		move(@left.height, @left, @right, @middle)
	end
end

Hanoi.new(ARGV[0].to_i).solve


--Apple-Mail-1-832166813--