[FWP] Towers of Hanoi

[Ilmari Karonen <iltzu@sci.fi>]

There are plenty of ways to solve the Towers of Hanoi in the optimal
sequence of 2**n-1 steps.  This one is interesting in that it can compute
any given step of the sequence in O(n) without having to traverse all the
preceding steps.

All the magic is in the longest line, specifically in the long indexing
expression.  Everything else is just scaffolding.  The easiest way to see
how it works is probably to watch the output and follow one of the pieces,
noting the direction and frequency of its movements.

#!/usr/bin/perl -w
use strict;

sub hanoi {
  my $i = shift;
  my @piles = ([], [], []);
  push @{$piles[int(($i+(1<<$_))/(2<<$_))*(1+(@_+$_&1))%3]}, $_[$_] for 0..$#_;
  return @piles;
}

my $n = shift || 10;
my @pile = map $_.reverse($_) => map " "x($n-$_)."="x$_, 0..$n;
my $blank = shift @pile;

for (0 .. (1<<$n)-1) {
  my @piles = hanoi($_, @pile);
  unshift @$_, ($blank)x($n-@$_) for @piles;
  for my $row (0 .. $n-1) {
    print map(@$_[$row] => @piles), "\n";
  }
  sleep(1);
}

__END__

-- 
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