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

Re:Isn't there a legend involved?

[Bagels]

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?

[daveq]

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.