Re: Hanoi Challenge

Here's my solution.

It's surely not optimal, but it's a very basic extension to the 3-peg solution, so the code is very short. It uses ~~O(d^1/(p-3)) moves~~ O(2^d/(p-2)) moves for the solution with d disks and p pegs (I'm too lazy to calculate the exact numbers).

(Updated fomula again. The O sign is meant if p is constant but d->inf)

Update: this is probably very suboptimal for more than 4 pegs.

#!/usr/local/bin/perl

use warnings; use strict;

$ARGV[0] =~ /(\d+)/ or die;
my $pegs = $1;
$ARGV[1] =~ /(\d+)/ or die;
my $disks = $1;

{
my @pegnames = "A" .. "Z";
sub printmove {
 my($d, $f, $t) = @_;
 print $d, ": ", $pegnames[$f], " -> ", $pegnames[$t], "\n"
}
}

sub rec {
 my($n, $s, $d, $t, @o) = @_;
 $n > 0 or return;
 my $k = @o < $n - 1 ? @o : $n - 1;
 #warn "[($n:${\($n-$k)} $s->$d]\n";
 rec($n - $k - 1, $s, $t, $d, @o);
 printmove($n - $k + $_, $s, $o[$_]) for 
  0 .. $k - 1;
 printmove($n, $s, $d);
 printmove($n - $k + $_, $o[$_], $d) for
  reverse(0 .. $k - 1);
 rec($n - $k - 1, $t, $d, $s, @o);
 #warn "[)]\n"
}

rec($disks, 0, 1, 2 .. $pegs - 1);


__END__
[download]

In Section Meditations