Slashdot Log In
108 Ways To Do The Towers of Hanoi
Posted by
Hemos
on Mon Dec 08, 2003 06:48 AM
from the and-50-ways-to-leave-your-jacob's-ladder dept.
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.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Next up: 108 ways to post the same story on /. (Score:5, Funny)
Isn't there a legend involved? (Score:5, Funny)
Re:Isn't there a legend involved? (Score:5, Informative)
Parent
Re:Isn't there a legend involved? (Score:5, Informative)
With 3 poles, you need (2 ^ discs)-1 moves to solve the problem. With 64 disks, and one move per second it's more like 584 billion years.
Parent
Re:Isn't there a legend involved? (Score:2)
Re:Isn't there a legend involved? (Score:2, Interesting)
Re:Isn't there a legend involved? (Score:2, Informative)
Re:Isn't there a legend involved? (Score:5, Insightful)
He then goes on to generalize the algorithm to support n-dimensional stacks.
Parent
Re:Isn't there a legend involved? (Score:5, Informative)
When n is the number of disks:
The recurrence is T(n) = 2*T(n-1) + 1. (No, there isn't a faster way)
The function is T(n) = 2^n - 1
I can't quote the exact value of 2^64-1 offhand, but the maximum value of an unsigned 64-bit integer is definately pretty huge.
Parent
Reverse DOS? (Score:3, Interesting)
ping HanoiServer -tos=128
Send one packet, get a hundred thousand (I'm sure I lost count somewhere) in return?
Whitespace? (Score:5, Interesting)
Re:Whitespace? (Score:5, Funny)
Parent
Re:Whitespace? (Score:2, Funny)
My addition (Score:5, Funny)
Re:My addition (Score:5, Funny)
Parent
But what about... (Score:3, Funny)
pfff ... Big deal ... (Score:5, Funny)
Visual Studio.NET includes a standard wizard for that.
Reminds me of... (Score:4, Insightful)
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)
Or you can download the archive [kernelthread.com]
Re:Reminds me of... (Score:5, Interesting)
(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)))
Parent
Re:Reminds me of... (Score:2, Interesting)
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]
yeah... (Score:5, Funny)
Re:yeah... (Score:3, Funny)
Why is the C++ version so complex... (Score:5, Interesting)
language the C++ version is still way overkill.
Re:Why is the C++ version so complex... (Score:2, Informative)
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.
Re:Why is the C++ version so complex... (Score:3, Interesting)
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
Haskell? (Score:4, Insightful)
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.
Re:Haskell? (Score:2)
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
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
Re:Haskell? (Score:2)
d'oh.
Yes, if I'd run that perl would have complained at me because use strict was on.
Re:Haskell? (Score:4, Informative)
Parent
Missed a language (Score:2)
You can program anything in RLL. Not that you'd want to--but your Client probably wants you to.
What is the most disks you have solved for? (Score:2, Interesting)
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.
Re:What is the most disks you have solved for? (Score:3, Funny)
Yes, I'm still single. Why do you ask?
Re:What is the most disks you have solved for? (Score:3, Funny)
justin
not that you need recursion for this... (Score:2, Interesting)
for (x = 1; x max; x++)
printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);
yet another missing language (Score:2)
And the 109th way... with a guitar (Score:2)
My favourite (Score:5, Interesting)
Towers of hanoi and bit flip correlation (Score:5, Interesting)
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)
<?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>
Do It in Hardware (Score:3, Interesting)
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)
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)
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 C++ version sucks. (Score:4, Interesting)
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();
}
Not really non-recursive (Score:3, Interesting)
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)
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)
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)
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.
Re:what if he had spent his time on something usef (Score:5, Insightful)
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!
Parent
Re:what if he had spent his time on something usef (Score:5, Funny)
Parent