Object-oriented solution to Tower of Hanoi

[Daniel Waite]

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

 

[darren kirby]

quoth the Daniel Waite:

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.

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

 

[Robert Klemme]

quoth the Daniel Waite:

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...

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

 

[darren kirby]

quoth the Robert Klemme:

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

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

 

[Daniel Waite]

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!

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

 

[Rich Morin]

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 (e-mail address removed)
http://www.cfcl.com/rdm/weblog +1 650-873-7841

Technical editing and writing, programming, and web development

 

[Lloyd Linklater]

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

 

[Martin DeMello]

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

 

[Phrogz]

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.