Slashdot Mirror
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 :)"
nt
Is this truly the only Earth I can live on?
When someone works out every single way to solve the problem, the towers will crumble to dust and the world will vanish
"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?
Visit CryptoGnome in his home.
Hmm, not all the important languages are represented in the list. I didn't see e.g. whitespace implementation.
Here it is coded in Whitespace:
If I seem short sighted, it is because I stand on the shoulders of midgets
...Brainfuck?
Converting the Towers of Hanoi syntax into 108 different languages?
Visual Studio.NET includes a standard wizard for that.
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...
to the joy of millions of 1st year Computer Science students.
Sig it.
This is useful to him, RTFA.
In fact, while this has gone to an extream, a many developers have a pet progam they implement anytime they run across a new language/platform. This give the programmer a familiar program to implement in an unfamiliar environment. A great way to get your feet wet with something new. Whenever I start working with a new language or on a new platform, I have a game I implement that covers many of the basic program constructs. By the time I have finished the game I have a good enough working knowledge of teh new language and/or platform to begin some real work.
Here is the same basic explination from the web page (I am assuming it will get slashdotted soon):
I am often asked that since I do all this, whether I have a lot of free time on my hands. Between my work and my interests (both of which overlap to a great extent), I actually have no free time. As an aside, I would not (and should not) be expected to "know" so many programming languages, and I don't think I do! However, I do believe that knowing a computer language is a rather fuzzy idea. If one could write a useful (loosely speaking, again) program in a given language, it is instructive to question whether one knows it. It is ironical (yes, there is such a word) that the bigger challenge, at least in my opinion, lies not in writing programs in all these different languages and ways, but in rapidly setting up the respective compiler systems and/or development environments on an appropriate platform/operating system. Sometimes compilers, interpreters and other such software for a particular language may be readily available, and run "out of the box", but many times this is not the case. Sometimes it turns out to be a non-trivial problem to get a compiler to function (pun unintended). Of course, once you get past this, you do have to understand some subset of the language!
...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.
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.
...he said in a posting on slashdot.
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.
Rhymes that keep their secrets will unfold behind the clouds.There upon the rainbow is the answer to a neverending story
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) > 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>
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?
Time flies like an arrow. Fruit flies like a banana.
Imagine the disk are in a cricle. Repeat:
- move the smallest disk one step clockwise
- 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...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();
}
The best one still have to be the version implemented in the C preprocesser.
http://www0.us.ioccc.org/years.html#1995_vanschnit z
I wanted to ask "why"
Never ask a geek "why". Just nod slowly as you back away.
David Gould
main(i){putchar(340056100>>(i-1)*5&31|!!(i<6)<< 6)&&main(++i);}