typodupeerror

## 108 Ways To Do The Towers of Hanoi192

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

• #### Re:Isn't there a legend involved? (Score:5, Informative)

on Monday December 08, 2003 @08:16AM (#7658665)
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.
• #### Re:Isn't there a legend involved? (Score:5, Informative)

on Monday December 08, 2003 @08:28AM (#7658700) Homepage
It's an exponential-time function (big O of N^2).

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.

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

on Monday December 08, 2003 @08:32AM (#7658719)
You can view the source code if you click on the name of the language in the section of the page labeled: "The Implementations"

• #### Re:Isn't there a legend involved? (Score:2, Informative)

on Monday December 08, 2003 @08:45AM (#7658769)
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 ;).
• #### Re:Why is the C++ version so complex... (Score:2, Informative)

on Monday December 08, 2003 @09:13AM (#7658885)
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.
• #### Re:Isn't there a legend involved? (Score:5, Informative)

on Monday December 08, 2003 @09:21AM (#7658928)
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.
• #### Re:Isn't there a legend involved? (Score:1, Informative)

by Anonymous Coward on Monday December 08, 2003 @10:23AM (#7659257)
Which is 584x10^9, in other words 584 billion... Learn to read standard form!

by Anonymous Coward on Monday December 08, 2003 @10:25AM (#7659265)
"(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 Common Lisp version doesn't work (Score:3, Informative)

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.

#### Related LinksTop of the: day, week, month.

"If it's not loud, it doesn't work!" -- Blank Reg, from "Max Headroom"

Working...