Forum: Ruby Object-oriented solution to Tower of Hanoi

Hi all. First off, be gentle. I imagine what I'm about to present is
pretty amateur, but I've been a programmer for about 6 years and up
until now have gotten away with knowing little about math (real math --
the kind with few numbers and lots of letters and symbols).

But as my interest grows beyond the world of web-based applications, I
find my lack of math is hurting me -- I know a given problem can be
solved with math, but I can't do it with math because I don't know it.
So what I DO do is tell it like a story with objects (which I will
present below). In fact, most of my non-trivial algos read like stories.
They're longer than an equivalent solution in math would be, but I
understand it.

I've observed that most "real" algorithms are heavy with the stuff, and
my eyes glaze over when I see something as simple as solutions to the
Tower of Hanoi.

However, I do think I'm a pretty good at developing object-oriented
programs. I've read the literature from David West and done some
research on Alan Kay. It's becoming easier for me to see systems as
tiny, interrelated objects with few responsibilities, manipulated by a
director.

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!

Here's the pastie: http://pastie.caboo.se/60604

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

quoth the Daniel Waite:
> They're longer than an equivalent solution in math would be, but I
> understand it.
>
> I've observed that most "real" algorithms are heavy with the stuff, and
> my eyes glaze over when I see something as simple as solutions to the
> Tower of Hanoi.

Very interesting. I find myself in exactly the same boat. I fell into my 
love
of computers/programming late in life (ie: after college), and I also 
have a
very weak background in math. I have found it had held me back a great 
deal.
Everytime I try to improve my math skills, I find myself having to 
backtrack
more and more because I am coming across concepts I just don't 
understand,
until I find myself all the way back at the high school level<shudder>.

I find myself often writing code by "mashing it around" until I get the 
output
I am looking for, with no real understanding or concept of a decent
algorithm.

You can see this manifested in all my submissions to the Ruby Quiz, 
which
always run waaaaaaaay slower than everyone else's ;)

I am trying though, I have some '...for dummies' books on algebra and
calculus, and I am working through SICP and the 6.001 tutor at MIT Open
Courseware, so perhaps there may be hope for me someday...

keep on keepin' on,
-d

On 11.05.2007 06:06, darren kirby wrote:
>> present below). In fact, most of my non-trivial algos read like stories.
> Everytime I try to improve my math skills, I find myself having to backtrack 
> I am trying though, I have some '...for dummies' books on algebra and 
> calculus, and I am working through SICP and the 6.001 tutor at MIT Open 
> Courseware, so perhaps there may be hope for me someday...

While it is certainly a good thing to improve your knowledge of algebra,
I suggest you also read a decent book on data structures and algorithms
(Knut, Sedgewick or the like).  It's not so much mathematics you will
learn from them but to analyze problems and find proper algorithms and
data structures.  You'll learn why it is more efficient to use a Hash
for lookups than traversing an array with key value pairs.  Things like
that.  Hope that helps.

Kind regards

  robert

quoth the Robert Klemme:

>   robert
Thanks Robert, good advice...

Apropos to your points, "Introduction to Algorithms" by Corman, 
Leiserson et
al is currently on the way to my house via Amazon.

I was looking at the (in)famous Knuth books, but the word on the 
playground is
that they are absolutely steeped in mathematical theory. This may or may 
not
be true for all I know, but the fact that MIT Open Courseware
6.046 -   "Introduction to Algorithms" uses the Corman book as text 
sealed my
choice.

Thanks again,
-d

darren kirby wrote:
> Very interesting. I find myself in exactly the same boat. I fell into my 
> love of computers/programming late in life (ie: after college), and I also 
> have a very weak background in math. I have found it had held me back a great 
> deal. Everytime I try to improve my math skills, I find myself having to 
> backtrack more and more because I am coming across concepts I just don't 
> understand until I find myself all the way back at the high school
> level<shudder>.

Yup, I feel you there. I've got a geometry book at home waiting eagerly 
awaiting to be cracked open.

> You can see this manifested in all my submissions to the Ruby Quiz, 
> which always run waaaaaaaay slower than everyone else's ;)

At least you're submitting to Ruby Quiz! I tried a few of them and 
they're pretty tough. So good work!

Robert Klemme wrote:
> While it is certainly a good thing to improve your knowledge of algebra,
> I suggest you also read a decent book on data structures and algorithms
> (Knut, Sedgewick or the like).  It's not so much mathematics you will
> learn from them but to analyze problems and find proper algorithms and
> data structures.  You'll learn why it is more efficient to use a Hash
> for lookups than traversing an array with key value pairs.  Things like
> that.  Hope that helps.

Actually, that does help. A lot. Thanks Robert. I shall seek and find on 
Amazon, and into my wish list shall those books go.

Thanks for the (extensive) response Mark, I appreciate it. Yes, you're 
absolutely right about understanding the nature of the problem before 
trying to solve it. I think I do a pretty good job of that -- I just 
have to remind myself that, eventually, I have to stop pondering and 
start writing.

I started laughing when I read your comment about my Hand object. My 
first iteration didn't have the Hand object, and it worked fine, but I 
knew I wanted to include it before I started the project, so in it went. 
It makes more sense to me that way.

I've always been into writing (fiction, mostly) and I gather my brain 
just "works that way," whereby stories make more sense than numbers.

I think I score okay on your first two skills for the ToH, but the 
third, recursion, has always been difficult for me, except when it's 
not. I understand iteration and nested iterations and when and how to 
use them, but I trip up when a method calls itself repeatedly.

Anywho, thanks for the awesome replies everyone -- you guys are great! 
:)

- Daniel

> Robert Klemme wrote:
>> I suggest you also read a decent book on data structures and algorithms
>> (Knut, Sedgewick or the like).

I find Sedgewick to be a lot more useful than Knuth, because
he uses high-level (well, higher than assembly) code.  I'd
love to see a good book on algorithms for Ruby (hint!).

For a gentle introduction to many of these topics, I'd look
at Jon Bentley's "Programming Pearls" and "More Programming
Pearls".

-r
--
http://www.cfcl.com/rdm            Rich Morin
http://www.cfcl.com/rdm/resume     rdm@cfcl.com
http://www.cfcl.com/rdm/weblog     +1 650-873-7841

Technical editing and writing, programming, and web development

The idea behind the solution as well as the source code (in java) and a 
graphical way to watch it run can be found at 
http://yupana.autonoma.edu.co/publicaciones/yupana/003/hanoi/hanoi_eng.html

On May 10, 6:34 pm, Daniel Waite <rabbitb...@gmail.com> 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!

Many days later, I finally wrote up my own version of ToH (without
looking at anyone else's code). Thought I'd share it just for fun:

http://pastie.caboo.se/61781

The move_stack method could be made a little cleaner by checking for
num_rings > 0 (since lines 44 and 47 are the same, and the 46 and 48
are just recursive calls)...but for some reason I prefer this slightly-
less-dry version. It just matches my mental model of the solution
better.

On 5/12/07, Rich Morin <rdm@cfcl.com> wrote:
> > Robert Klemme wrote:
> >> I suggest you also read a decent book on data structures and algorithms
> >> (Knut, Sedgewick or the like).
>
> I find Sedgewick to be a lot more useful than Knuth, because
> he uses high-level (well, higher than assembly) code.  I'd
> love to see a good book on algorithms for Ruby (hint!).

give http://www.brpreiss.com/books/opus8/ a look.

martin