Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
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 More

108 Ways To Do The Towers of Hanoi

Comments Filter:

  • Next up: 108 ways to post the same story on /. (Score:5, Funny)

    by corebreech ( 469871 ) on Monday December 08, 2003 @07:53AM (#7658590) Journal
    nt

  • Isn't there a legend involved? (Score:5, Funny)

    by 91degrees ( 207121 ) on Monday December 08, 2003 @07:54AM (#7658593) Journal
    When someone works out every single way to solve the problem, the towers will crumble to dust and the world will vanish

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

  • My addition (Score:5, Funny)

    by kinnell ( 607819 ) on Monday December 08, 2003 @08:02AM (#7658625)
    Here it is coded in Whitespace [dur.ac.uk]:





  • But what about... (Score:3, Funny)

    by Mr. Mosty-Toasty ( 449993 ) on Monday December 08, 2003 @08:02AM (#7658627) Homepage
    ...Brainfuck [muppetlabs.com]?

  • pfff ... Big deal ... (Score:5, Funny)

    by cablepokerface ( 718716 ) on Monday December 08, 2003 @08:09AM (#7658642)
    Converting the Towers of Hanoi syntax into 108 different languages?

    Visual Studio.NET includes a standard wizard for that.

  • Reminds me of... (Score:4, Insightful)

    by zhenlin ( 722930 ) on Monday December 08, 2003 @08:15AM (#7658659)
    http://www2.latech.edu/~acm/HelloWorld.shtml

    The Hello World page.

    The difference? The examples on the Hello World page all have source code. Hanoimania... Not so.

    But.... solving the Towers of Hanoi shows a lot more of the programming environment than Hello World does... Conditionals, branching, recursion, function calls...

    • Re:Reminds me of... (Score:3, Informative)

      by edalytical ( 671270 )
      You can view the source code if you click on the name of the language in the section of the page labeled: "The Implementations"

      Or you can download the archive [kernelthread.com]

      • The keyword here is all.

        The page clearly states that there are 4 for which there is no source code.They are:

        * Hanoi OS for SPARC
        * Sun Solaris /proc
        * Sun Solaris STREAMS
        * Sun Solaris kernel module

        Curious, isn't it, that they are all related to Sun?

      • 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)))

  • So which one of these should I run if I want to view it animated in X11?

  • yeah... (Score:5, Funny)

    by AbbyNormal ( 216235 ) on Monday December 08, 2003 @08:33AM (#7658727) Homepage
    to the joy of millions of 1st year Computer Science students.

    • Re:yeah... (Score:3, Funny)

      by cdrudge ( 68377 )
      And much to the chagrin of thousands of CS profs.
    • IAAFYCSS, and that happened to be my favorite lab :-)
    • But think of how convenient it will be every September when the new CS students start posting their questions to various news groups with subject lines like :

      Need Help ASAP! How Do I Do This??!!

      Now we can just point them to this page and ignore them istead of trying to explain how we're not here to do their homework for them. Ah, yes. The changing color of the leaves, the crisp coolness of the air, the desperate plea of the programmer newbies. Those are the first signs of autumn that I love so much.

  • Why is the C++ version so complex... (Score:5, Interesting)

    by Viol8 ( 599362 ) on Monday December 08, 2003 @08:42AM (#7658756) Homepage
    ...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.
    • Because the C++ version is non-recursive.

      I'm glad he did it this way. I had heard of a previous student that programmed it non-recursively. Now I have an example to look at.
    • my question is why he made his own stack object. i could have sworn the STL has a stack object included.
      • 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::S
        • 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.

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

          Probably because CAPACITY is too, and CAPACITY is a macro because this was probably written before static const ints could be used as array size initialisers.

          Presumably this also explains why he didn't use exceptions instead of EMPTY/FULL/PUSH_OK. There's no excuse for the variables starting with underscores, though.

          OK, here's my version [bromage.org].

  • Haskell? (Score:4, Insightful)

    by mattr ( 78516 ) <mattr&telebody,com> on Monday December 08, 2003 @08:43AM (#7658761) Homepage Journal
    Is it just me or does the Haskell one seem to have inverted parameters wrt the vanilla Perl one? Not that I know Haskell.. I was hoping to see some lexical wierdness in Perl and some lambdas and arrows all hanging out for the Haskell one. And wha-hey no smalltalk? well the world goes on..

    Neat idea, I like to see how things are done in other languages. It would be an interesting and intuitive way to show people what other languages are like, a list of programs the same in each language, plus commentary about the highlights of the language that are used.
    • The Perl one's really weird

      ($#ARGV == 0) or die "usage: $0 N\n";

      Wow, that's really confusing. It's trying to say unless we've got arguments, we need to die with an error message. Which can be witten as

      unless (@ARGV)
      { die "usage: $0 N\n"; }

      That's not the only other thing that's odd too. Using local instead of my is odd - though both will work. my will do proper lexical variables, whereas local is using main variables in the stash and creating temp copies each itteration of the subroutine.

      Oh, and w

  • Relay Ladder Logic


    You can program anything in RLL. Not that you'd want to--but your Client probably wants you to.

  • I once did a 3D-visualized Prolog implementation [it.kth.se] of the towers of Hanoi for a course assignment. It used the VR system DIVE for visualization, the Hanoi implementation was a simple proof of concept of the rudimentary Prolog interface to DIVE that was the actual assignment... Sweet memories :)

    (Un?)fortunately, the code is not publicly available.
  • 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.
    • As a younger child, a teacher would give this problem to "gifted" students who were bothering her. We couldn't ask another question until we solved it, with 10 disks.
    • Eight here too. In fact when I first heard of the problem (when I was 10 I think), it specified 8 disks. Never occurred to me to solve for a smaller problem first. It took me some 14 months to find a solution for the 8-disk problem by myself. Man, those were the days! I used playing cards instead of disks, and everybody around me thought I was playing some weird form of Solitaire. Sigh.
      Yes, I'm still single. Why do you ask?
    • 10 here. i wrote a computer program to draw a sexy 3d version of it and let me move pieces by tapping the 1, 2 and 3 keys. after solving 4 or 5 discs a few times my fingers would get into this wierd zone where they'd just fly over those three keys without any conscious thought. very cool.

      justin
  • 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);

  • where is the quakec implementation? This would make quite the interesting demonstration.
  • http://www.towersofhanoi.org

    • Re: your sig (Score:1, Offtopic)

      by dillon_rinker ( 17944 )
      A musician without the RIAA, is like a fish without a bicycle.

      Try this...A musician without the RIAA is like a fish without a hook.

      The RIAA is actually harmful. The original quote suggested simply that women didn't need men. (Also that women were slimy scaly smelly creatures and men were carefully engineered tools of great craftsmanship, but I digress...)

  • 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);
    }
    }
    • This algorithm has a slightly different result from the recursive algorithm.

      For an even number of disks it your code moves the disks from stack 0 to 1, and for an odd number of disks from stack 0 to 2.

      (The recursive algorithm in the 102 examples moves the disks from stack 0 to 2 always).

  • Towers of hanoi and bit flip correlation (Score:5, Interesting)

    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.

    • The Chinese rings puzzle is also based on the binary numbers. I have a puzzle called "The Brain" with rods that slide in and out. These are all really the same puzzle and have the same solution:

      Alternate moving the smallest ring and doing the only other move left.

      The only problem is that you need to go in the correct direction at the beginning, otherwise you're moving an odd number instead of even or vice-versa. I got to where I could solve the Brain (8 sliders) in a few seconds with my eyes closed.

  • Now here's a question:

    Do you think that this problem is representative of the language? e.g. Perl is more efficient than PHP. Or is this going about it all wrong because of the specialisation of programming? Perhaps a series of tests consisting of different types of problems would be possible?

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

  • the Common Lisp version doesn't work (Score:3, Informative)

    by e40 ( 448424 ) on Monday December 08, 2003 @12:43PM (#7660218) Journal

    The person that wrote it sure did not have a firm grasp of Lisp. The use of eval was completely bogus. In any case, eval takes one argument, not three.

    This [known.net] is a better one that actually works. I would have posted it here in the comment, but you can't format code in slashdot.

  • Very easy non-recursive solution (Score:5, Insightful)

    by OttoM ( 467655 ) on Monday December 08, 2003 @12:43PM (#7660222)
    This solution I always liked best:

    Imagine the disk are in a cricle. Repeat:

    1. move the smallest disk one step clockwise
    2. do the only legal move not involving the smallest disk
    Much easier to remember and perform by hand than the various iterative C programs posted. The proof that it works is left as an exercise to the reader...
  • The guy's Resume says that he works on Linux on the Desktop at IBM's research lab.

    Interesting to see IBM working with Linux on the Desktop at all.

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

  • His page also contains the best review of a PowerBook 17" [kernelthread.com] that I've ever read.
  • Malbolge. Who ever said programming was supposed to be easy or fun?

    Malbolge, Programming From Hell [mines.edu]

  • That C++ version sucks. (Score:4, Interesting)

    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();
    }

  • When I read the title.. (Score:1, Funny)

    by Anonymous Coward
    I thought of 108 Ways To Do The Girls of Hanoi.

    Much more, uh, arousing.
  • at one moment of the game, you have to resolve this kind of problem in Black & White [bwgame.com].

  • Not really non-recursive (Score:3, Interesting)

    by darkonc ( 47285 ) <stephen_samuel@b ... m ['n.c' in gap]> 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.

  • Ok, I know its slightly offtopic...

    Its true, the towers of Hanoi puzzle is actually present in the Star Wars: Knights of the Old Republic game. Its the 4 disk version.

    Always fun to see classic puzzles show up in computer games under a different guise.
  • 108 versions??

    Not to sound trollish but, this guy has way too much time on his hands and needs to get a life, or find something interesting to program.

    Maybe its just me but I get nightmares from Tower of Hanio programs.

    Its what made me decided that Biology and not CS is where I belonged.

    Shudder.

  • Laszlo LZX wasn't on the list so I fixed that...
    Here [mylaszlo.com] is an LZX version :)

    Laszlo Systems INC [laszlosystems.com]

    You'll have to be patient for the XAML (Longhorn) or Macromedia Flex versions since they're a ways off ;)
  • See the Brainfuck solution here [sange.fi].

    It begins like (lameness filter prevents a longer excerpt, just click the link):

    The first stack frame (0 0 0 0 0 0 0 0)
    is used to abort the recursion
    >>>>>>>>

    These are the parameters for the program
    (1 4 1 0 'a 'b 'c 3)
    +>++++>+>>
    >>>>++++++++[-]+>+>-]++>+++>+++>

    And so on.

  • 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]

  • Well, you know waht they say... (Score:4, Funny)

    by David Gould ( 4938 ) <david@dgould.org> on Monday December 08, 2003 @06:22PM (#7663109) Homepage

    I wanted to ask "why"

    Never ask a geek "why". Just nod slowly as you back away.

  • A Useful Tool in Religious Disputation (Score:3, Interesting)

    by aebrain ( 184502 ) <aebrain@gmail.com> 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.

  • towers implemented as a Slashdot thread (Score:2, Funny)

    by Anonymous Coward
    ``=I=`` I I
    `==I==` I I
    ===I=== I I

    Your move.

    (You wouldn't believe how long it took to get this to display correctly and get past the lameness filter)

Slashdot Top Deals

"Protozoa are small, and bacteria are small, but viruses are smaller than the both put together."

Close