Forgot your password?
typodupeerror
PC Games (Games) Programming IT Technology

108 Ways To Do The Towers of Hanoi 192

Posted by Hemos
from the and-50-ways-to-leave-your-jacob's-ladder dept.
hlarwood74 writes "While it is common to program in a few different languages, somebody has written "towers of hanoi" in 108 different ways, most of them in different programming languages. It's not just the number of languages though ... there are many neat implementations and in some cases he's come up with some strange ways of solving hanoi such as this: "you ping the hanoi machine with the number of disks encoded in the type of service field, and you get response packets whose sequence numbers represent the disk moves need to solve the puzzle". I wanted to ask "why" but the title of the page (hanoimania) explains a few things :)"
This discussion has been archived. No new comments can be posted.

108 Ways To Do The Towers of Hanoi

Comments Filter:
  • Reverse DOS? (Score:3, Interesting)

    by Crypto Gnome (651401) on Monday December 08, 2003 @07:57AM (#7658600) Homepage Journal
    "you ping the hanoi machine with the number of disks encoded in the type of service field, and you get response packets whose sequence numbers represent the disk moves need to solve the puzzle"

    ping HanoiServer -tos=128

    Send one packet, get a hundred thousand (I'm sure I lost count somewhere) in return?
  • Whitespace? (Score:5, Interesting)

    by hkroger (666340) on Monday December 08, 2003 @07:57AM (#7658604)
    Hmm, not all the important languages are represented in the list. I didn't see e.g. whitespace [dur.ac.uk] implementation.
  • by Colonel Cholling (715787) on Monday December 08, 2003 @08:36AM (#7658739)
    Besides, if I remember the legend correctly, the disks were supposed to be moved at the rate of one per year. (They're heavy, ok?)
  • by Viol8 (599362) on Monday December 08, 2003 @08:42AM (#7658756)
    ...when the C version is so simple? He could have used the C version for both. Even if he was trying to show off the features of the
    language the C++ version is still way overkill.
  • by fliptout (9217) on Monday December 08, 2003 @10:20AM (#7659230) Homepage
    I've solved the towers of hanoi with 8 disks.. Curious if anyone has solved a more insane number without computer assistance.

    Though it seems pretty pointless and boring to solve for a high number of disks as the learning curve drops sharply after you figure out how to solve for the basic three disks.
  • by johntromp (565732) on Monday December 08, 2003 @10:27AM (#7659280)
    max = 1 no_of_discs;
    for (x = 1; x max; x++)
    printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);

  • Re:Reminds me of... (Score:5, Interesting)

    by Gorobei (127755) on Monday December 08, 2003 @10:38AM (#7659360)
    The first one I checked (Common Lisp,) was just wrong:

    (defun dohanoi(n to from u)
    (if (> n 0)
    (eval
    (dohanoi (- n 1) u from to)
    (format t "move ~D --> ~D~&" from to)
    (dohanoi (- n 1) to u from)
    )
    )
    )

    (defun hanoi(n)
    (eval
    (dohanoi n 3 1 2)
    )
    )

    eval is not what we want here (it evaluates a single form in the current dynamic environment.) Also, we can use 1- and indent trailing parens correctly. For extra credit, we could make dohanoi local to hanoi.

    (defun dohanoi(n to from u)
    (when (> n 0)
    (dohanoi (1- n) u from to)
    (format t "move ~D --> ~D~&" from to)
    (dohanoi (1- n) to u from)))

  • Re:Reminds me of... (Score:2, Interesting)

    by edalytical (671270) on Monday December 08, 2003 @10:41AM (#7659374)
    The keyword here is
    all.
    Indeed, the keyword is all.

    http://www2.latech.edu/~acm/HelloWorld.shtml

    Is missing:

    BLISS
    Cecil
    Demeter
    Elf
    Escher
    Hope
    Infer
    NESL
    Obliq
    Proteus
    SGML
    Sisal
    Theta
    Tycoon
    emacs
    Lotus 1,2,3
    Unisys' WFL
    OWL
    MFC
    ZApp
    Zinc

    And those are just the languages listed that don't have a link at the Hello World! page http://www2.latech.edu/~acm/HelloWorld.shtml [latech.edu]

  • by fnj (64210) on Monday December 08, 2003 @10:53AM (#7659434)
    my question is why he made his own stack object. i could have sworn the STL has a stack object included.

    Er, just a guess, but maybe the original concept of his code predated the wide availability of STL. Or quite likely, as a tutorial, he just wanted to depend on nothing beyond iostreams.

    I'm more concerned with some other points:

    Why "#define STYPE int" instead of "typedef int stype"?

    Why the #defines for EMPTY, FULL, and PUSH_OK instead of an enum?

    Why the "Stack::Stack(void)" instead of just "Stack::Stack()" (the former is a C anachronism)?

    Then, of course, to get really nitpicky, he doesn't need his destructor at all (one will be generated by the compiler).
  • My favourite (Score:5, Interesting)

    by vorwerk (543034) on Monday December 08, 2003 @11:01AM (#7659486)
    A quick scan of the listing didn't show my favourite one -- a non-recursive implementation.
    #include <stdio.h>

    #define NO_OF_DISKS 4

    void main()
    {
    int max, x;

    max = 1 << NO_OF_DISKS;
    for (x = 1; x < max; x++) {
    printf("Move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);
    }
    }
  • by musikit (716987) on Monday December 08, 2003 @11:04AM (#7659500)
    very true. i guess it goes to another comment that someone else had about writing code in C and it being compilable in C++. while true there are different ways your suppose to write C++ code vs. C code. however it seems a large amount of people use a mix. Or maybe no one is teaching people to program in C++ but in C with C++ constructs.
  • by nebaz (453974) on Monday December 08, 2003 @11:43AM (#7659770)
    One neat thing I discovered about the towers of hanoi is that the sequence of disks to move for a solution

    1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5...
    is the exact same sequence that you get when you look at the number of bits flipped between consecutive binary numbers (i.e.
    00000->00001 (1 flip),
    00001->00010 (2 flips),
    00010->00011 (1 flip),
    00011->00100 (3 flips),
    00100->00101 (1 flip),
    00101->00110 (2 flips)
    etc... (1,2,1,3,1,2,...)

    The reason it works is because just like the towers of hanoi algorithm, when the general solution to move n disks is:
    Recursively solve the puzzle for n-1 disks
    Take the nth disk and move it to the goal
    Recursively solve the puzzle for n-1 disks.

    The bit flipping goes like this:
    While the nth bit is 0, the solution works for the n-1 disk solution
    When we go from 011111 (n-1 1's) to 10000000 (n-1 0's) we flip n bits
    Then the nth bit stays 1 and we repeat the solution for the n-1 disks.

  • XML/XSL (Score:5, Interesting)

    by Chilltowner (647305) on Monday December 08, 2003 @11:51AM (#7659827) Homepage Journal
    As an XSL guy, I felt left out. So, given this xml:
    <?xml version="1.0"?>
    <hanoi>
    <arg n="3"/>
    </hanoi>

    you can transform with this:
    <?xml version="1.0"?>
    <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:template match="/">
    <xsl:variable name="n">
    <xsl:value-of select="//arg/@n"/>
    </xsl:variable>
    <xsl:element name="hanoi-solve">
    <xsl:call-template name="dohanoi">
    <xsl:with-param name="n" select="number($n)"/>
    <xsl:with-param name="to" select="3"/>
    <xsl:with-param name="from" select="1"/>
    <xsl:with-param name="using" select="2"/>
    </xsl:call-template>
    </xsl:element>
    </xsl:template>
    <xsl:template name="dohanoi">
    <xsl:param name="n"/>
    <xsl:param name="to"/>
    <xsl:param name="from"/>
    <xsl:param name="using"/>
    <xsl:if test="number($n) &gt; 0">
    <xsl:call-template name="dohanoi">
    <xsl:with-param name="n" select="number($n) - 1"/>
    <xsl:with-param name="to" select="$using"/>
    <xsl:with-param name="from" select="$from"/>
    <xsl:with-param name="using" select="$to"/>
    </xsl:call-template>
    <xsl:element name="move">
    <xsl:attribute name="from">
    <xsl:value-of select="$from"/>
    </xsl:attribute>
    <xsl:attribute name="to">
    <xsl:value-of select="$to"/>
    </xsl:attribute>
    </xsl:element>
    <xsl:call-template name="dohanoi">
    <xsl:with-param name="n" select="number($n) - 1"/>
    <xsl:with-param name="to" select="$to"/>
    <xsl:with-param name="from" select="$using"/>
    <xsl:with-param name="using" select="$from"/>
    </xsl:call-template>
    </xsl:if>
    </xsl:template>
    </xsl:stylesheet>
  • Do It in Hardware (Score:3, Interesting)

    by 4of12 (97621) on Monday December 08, 2003 @11:53AM (#7659842) Homepage Journal

    I remember decades ago coming across the towers of Hanoi built with wooden dowels and hardwood disks with holes in them. This was late one evening when everyone else had retired.

    After playing around with it for a few minutes, my mind just naturally got into the algorithm. The disks were flying around with hardly any conscious thought required on my part.

    Just one of those cool game zombie states...

    Probably because I'm prone to addictive behaviors I tend to avoid getting involved too closely with games; but I still remember the great buzz of doing Towers of Hanoi the first time.

    [There's another hardware puzzle, like a Chinese lock with multiple loops, that's similarly fun for the recursively minded.]

  • by WayneConrad (312222) * <wconrad.yagni@com> on Monday December 08, 2003 @01:12PM (#7660447) Homepage

    Gravatite [slashdot.org] and I like to code Combsort when we're learning a new language. Combsort a very simple modification to bubblesort that makes it competative with Quicksort but without quite as much complexity -- it's good for those rare occasions where you have to hand-code a sort and don't need all the fuss of quicksort.

    I've done combsort in about a dozen dozen languages [yagni.com], and Gravatite has done it in a few more languages, including postscript [nickstoys.com].

  • by pclminion (145572) on Monday December 08, 2003 @01:44PM (#7660702)
    That's the worst C++ feature-masturbation I've ever seen.

    Here's a version using C++ template metaprogramming I just whipped up:

    #include <iostream>

    template <int N, int From, int To, int Using>
    class HanoiSolver
    {
    public:
    static void solve()
    {
    HanoiSolver<N-1, From, Using, To>::solve();
    std::cout << "Move " << From << " to " << To << std::endl;
    HanoiSolver<N-1, Using, To, From>::solve();
    }
    };

    template <int From, int To, int Using>
    class HanoiSolver<0, From, To, Using>
    {
    public:
    static void solve()
    {
    }
    };

    int main()
    {
    HanoiSolver<10, 1, 2, 3>::solve();
    }
  • by darkonc (47285) <stephen_samuelNO@SPAMbcgreen.com> on Monday December 08, 2003 @02:21PM (#7661001) Homepage Journal
    His "non-recursive" solutions aren't really non-recursive. They simply store the state (what's being moved where) onto the stack, and then pulls and pops the state. It's just a simple enough 'machine' that you only have 4 variables (from, to, using, depth). All you've really done is taken the stackwork away frm th compiler.

    Back in the late '70s, me and some friends came up with a solution that is more honestly non-recursive:

    Move the smallest disk to the right (cyclically). If the other two stacks are empty, you're done, else move the smallest top disk of the two stacks to the other stack (the only move you can make if you're not moving disk 1 again).

    (note: The above solution only works for an even number of disks... For an odd number of disks, disk 1 moves to the LEFT.)

    Oh, sigh... The perl implementation of this is on my website [bcgreen.com].

    Yes, the solution is provably correct, but I don't have the time to write it up right now... Just consider the fact that you can never move disk1 twice in a row, (or you're wasting a move), and if you're not moving disk1, there's only one move, then you have to move disk1 again (or you're wasting a move). All you have to do then is prove that disk1 always moves in the same direction.

  • cpp (Score:3, Interesting)

    by mr_klaw (103631) on Monday December 08, 2003 @04:24PM (#7661992)

    The best one still have to be the version implemented in the C preprocesser.

    http://www0.us.ioccc.org/years.html#1995_vanschnit z [ioccc.org]

  • by Anonymous Coward on Monday December 08, 2003 @07:04PM (#7663467)
    So yeah fine towers of hanoi in 108 ways is cool, but i looked around the guy's site, and it seems hanoi is not the only cool thing he does. Check these out -

    The operating systems [kernelthread.com] the guy uses ...

    The operating systems [kernelthread.com] he runs on his apple notebook ...

    The guy's projects [kernelthread.com] - particularly the Sun Solaris Virutalization ...

    The art [kernelthread.com] stuff... the comic [kernelthread.com] etc. ... WOW! Somebody *does* have a lot of time, not to say talent!!!

  • by aebrain (184502) <aebrain@webone.com.au> on Monday December 08, 2003 @08:31PM (#7664347) Homepage Journal

    Everyone agrees that arguments about Languages are Religious, right?

    Well, maybe not. Just have a look at these samplings of code. Now you can argue that some implementations are un-neccessarily complex, and others inefficient. Fair enough. But apart from such deliberately obfuscated grotesques such as the sed implementation, you can get a "within an order of magnitude" estimate of how simple/powerful/readable a language is by looking at the sources.

    For example, contrast the PERL [kernelthread.com] implementation with the C [kernelthread.com] implementation.
    Now look at the Java [kernelthread.com] vs the Ada [kernelthread.com] implementations.
    The similarities, and differences, are instructional.

    Parenthetically, with the forthcoming release of Java 1.5, which has Ada facilities such as strong typing of enumerations and generics, the architectural similarities between Ada and Java will become even more pronounced. IMHO Java has a far neater notation of Object-Oriented features than Ada-95's, but in all other respects suffers from C's over-terse syntax. But that's just my opinion. Look at the examples and form your own.
    What is not a matter of opinion is that readability helps improve code quality. And wonder why "everyone knows" Ada is over-complicated, too difficult to implement, and too costly - especially when open-source free compilers have been around for nearly a decade now.

Heuristics are bug ridden by definition. If they didn't have bugs, then they'd be algorithms.

Working...