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 :)"
No, when somebody completes the problem with 64 disks, the world will end. It's an exponential-time function (big O of N^2), so doing that would take an insanely long time. I once calculated this out - assuming you could move 1 disk per second, it would take about 5 billion years, which is very roughly the predicted remaining lifespan of the sun.
--- Bwah?
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.
Or you can download the archive
Win a signed Stephen Carpenter ESP Guitar from the Deftones: http://def-tag.com/?r=0008781
True-ish, as that may be (64 disks with a move per second takes 585 billion years), computers can solve the puzzle much faster. A nanosecond per move is not entirely unreasonible, and a computer at that speed would have it solved in 585 years (namely, a billionth of the time ;).
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.
-Richard L. Owens
n^2 is quadratic, not exponential ;)
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.
Which is 584x10^9, in other words 584 billion... Learn to read standard form!
"(condition) or die" is perfectly good, non-confusing Perl. It's the way you're told to do it in the Camel book, for God's sake.
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 is a better one that actually works. I would have posted it here in the comment, but you can't format code in slashdot.