Re: [FWP] Towers of Hanoi

[Ilmari Karonen <iltzu@sci.fi>]

[Cc'd back to FWP, in case someone else wants to know..]

On Thu, 14 Sep 2000, Marko Schilde wrote:
> Um, can you explain to me what the Towers of Hanoi problem is about? Please?

Run the code and watch.  For the best effect, resize your terminal so that
you can only see one set of piles.

It's a simple game or puzzle.  In the physical version you have a board
with three sticks sticking up from it, and a set of disks with a hole in
the middle that fit around the sticks.  You start with all the disks on
the leftmost stick, and move them one at a time until they're all on the
rightmost stick.  The catch is that no two disks are the same size, and
you're not allowed to put a larger disk on top of a smaller one.

The toy version usually has about six disks.  The name comes from a legend
that says there is a temple hidden in Hanoi where a secret group of monks
are playing the game with 64 sacred disks, and that once they finish the
task the world will end.  As this will require at least 2**64 moves, there
isn't much cause to worry. :-)

Even the toy version can be quite frustrating unless you know the optimal
sequence, since it requires a sort of recursive "to go right, first go as
far left as you can" approach humans are notoriously bad at.

The Towers of Hanoi is intimately related to another puzzle known as
Chinese Rings.  This can be even more frustrating, both because cheating
is physically impossible (unless you break the puzzle) and because the
normal starting position is halfway between the goal and the worst
starting point.  This might seem like an advantage until you realize that
because of the recursive nature the goal and the worst position are almost
identical, and it's easy to work towards the wrong one..

The optimal sequence for Chinese Rings corresponds to the binary inverted
Gray code, which also has some relevance to the Towers of Hanoi.  This was
recently discussed in c.l.p.moderated, and it's also involved in one of my
one-line idler animations posted to c.l.p.misc and alt.ascii-art.animation
which are definitely Fun With Perl:

  perl -e '$|=1; print "\rPlease wait", grep tr/01/ ./ => unpack "b*"
           => pack "v" => $i^$i/2 while ++$i and sleep 1'

There.  I knew I'd get this back on topic.

-- 
Ilmari Karonen
http://www.sci.fi/~iltzu/


==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe