Object-oriented solution to Tower of Hanoi

Discussion in 'Ruby' started by Daniel Waite, May 11, 2007.

  1. Daniel Waite

    Daniel Waite Guest

    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
     
    Daniel Waite, May 11, 2007
    #1
    1. Advertisements

  2. Daniel Waite

    darren kirby Guest

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

    keep on keepin' on,
    -d
     
    darren kirby, May 11, 2007
    #2
    1. Advertisements

  3. 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
     
    Robert Klemme, May 11, 2007
    #3
  4. Daniel Waite

    darren kirby Guest

    quoth the Robert Klemme:
    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, May 11, 2007
    #4
  5. Daniel Waite

    Daniel Waite Guest

    Yup, I feel you there. I've got a geometry book at home waiting eagerly
    awaiting to be cracked open.
    At least you're submitting to Ruby Quiz! I tried a few of them and
    they're pretty tough. So good work!

    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
     
    Daniel Waite, May 11, 2007
    #5
  6. Daniel Waite

    Rich Morin Guest

    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
    http://www.cfcl.com/rdm/weblog +1 650-873-7841

    Technical editing and writing, programming, and web development
     
    Rich Morin, May 11, 2007
    #6
  7. Lloyd Linklater, May 12, 2007
    #7
  8. give http://www.brpreiss.com/books/opus8/ a look.

    martin
     
    Martin DeMello, May 12, 2007
    #8
  9. Daniel Waite

    Phrogz Guest

    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.
     
    Phrogz, May 15, 2007
    #9
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.