108 Ways To Do The Towers of Hanoi

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 :)"

Comments

Whitespace?

[hkroger]

Hmm, not all the important languages are represented in the list. I didn't see e.g. whitespace implementation.

Why is the C++ version so complex...

[Viol8]

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

Re:Reminds me of...

[Gorobei]

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

My favourite

[vorwerk]

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

Towers of hanoi and bit flip correlation

[nebaz]

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

[Chilltowner]

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>