We are all familiar with the towers of hanoi puzzle. It was most recently discussed at
. In the puzzle you have 3 pegs and a series of disks sorted from largest to smallest on one peg. You want to transfer the disks to another peg, moving one disk at a time and never putting a larger disk on a smaller one. The solution is well-understood, and there is only one way to make real progress at any move.
But most of us have not seriously thought about the case where there are 4 or more pegs to work with. In one sense this problem is easier - after all you can ignore all but 3 pegs and recycle the existing solution. However if you use the extra pegs, you can be more efficient. How much more efficient? Nobody knows for sure. Nobody has managed to prove what the most efficient general algorithm is for 4 pegs. Let alone 5 or more.
So here is the challenge: how efficient of programs can people come up with to solve the Hanoi puzzle with 3 or more pegs and an arbitrary number of disks? Let me specify this in more detail...
Let's have our hanoi programs take 2 arguments on the command line, the number of pegs available and the number of disks. The program will name the pegs A, B, C, etc. All of the disks start on peg A. They need to wind up on peg B. Each move is announced as follows:
(disk): (peg from) -> (peg to)
Putting this together, we expect something like this:
$ ./hanoi.pl 3 3
1: A -> B
2: A -> C
1: B -> C
3: A -> B
1: C -> A
2: C -> B
1: A -> B
The following test driver can be used to test the validity of output (if the programs finish that is - please make sure that they'll finish reasonably quickly). Look in its examples for how to use it.
#! /usr/bin/perl -w
use strict;
use Getopt::Long;
use Pod::Usage;
GetOptions(
'pegs=i' => \ my $peg_count,
'disks=i' => \ my $disk_count,
'program=s' => \ my $program,
'verbose' => \ my $verbose,
'prompt' => \ my $prompt,
'help' => \ my $help,
) or pod2usage(2);
pod2usage(1) if $help;
$verbose ||= $prompt;
$peg_count ||= 3;
$disk_count ||= 4;
$program ||= "./hanoi.pl";
my @pegs;
my %disks;
my $peg = 'A';
for (1..$peg_count) {
push @pegs, $peg;
$disks{$peg} = [];
$peg++;
}
$disks{A} = [reverse 1..$disk_count];
open (PIPE, "$program $peg_count $disk_count |")
or die "Cannot run '$program': $!";
my $move = 0;
while (<PIPE>) {
chomp;
$move++;
print "Move $move: $_\n" if $verbose;
die "Move $move: Invalid input '$_'\n"
unless (/(\d+):\s*(\w+)\s*->\s*(\w+)/);
my $disk = $1;
my $from = $2;
my $to = $3;
die "Peg '$from' not found on move $move\n"
unless exists $disks{$from};
my $pile_from = $disks{$from};
die "Disk $disk is not on top of peg '$from' at move $move\n"
unless $pile_from->[-1] == $disk;
die "Peg '$to' not found on move $move\n"
unless exists $disks{$to};
my $pile_to = $disks{$to};
if (@$pile_to) {
my $top = $pile_to->[-1];
die "Disk $disk cannot go on top of disk $top at move $move\n"
unless $disk < $top;
}
pop @$pile_from;
if ($verbose) {
foreach my $peg (@pegs) {
print join " ", "$peg ", @{$disks{$peg}};
print " -" if $peg eq $from;
print " +$disk" if $peg eq $to;
print "\n";
}
if ($prompt) {
<STDIN>;
}
else {
print "\n";
}
}
push @$pile_to, $disk;
}
my @with_disks = grep {@{ $disks{$_} }} @pegs;
if (1 == @with_disks and $with_disks[0] eq 'B') {
print "Solved in $move moves\n";
}
else {
die "Not solved after $move moves\n";
}
__END__
=head1 NAME
hanoi-driver.pl
=head1 SYNPOSIS
hanoi-driver.pl [opts]
=head1 OPTIONS
-h --help Print help and exit
--pegs INT How many pegs to have. Default 3.
--disks INT How many disks to have. Default 4.
--program STR What test program to run. Default ./hanoi.pl.
-v --verbose Keep a running commentary up about each step
--prompt Wait for STDIN on each step. Implies verbose.
=head1 DESCRIPTION
Test driver for programs that solve the hanoi puzzle. It will
execute the program, study the output, die if any impossible
moves get made or the puzzle is not solved properly, and then
report how many steps it took.
If you set verbose mode it will show the game being played.
=head1 EXAMPLES
This will execute "./hanoi.pl 3 4" and expect to see a
solution to the hanoi puzzle with 3 pegs and 4 disks.
./hanoi-driver.pl
This will execute "./hanoi.pl 3 4" and expect to see a
solution to the hanoi puzzle with 3 pegs and 4 disks.
The output will play the solution out.
This will execute "./another_program" and expect to see a
solution to the hanoi puzzle with 5 pegs and 15 disks.
./hanoi-driver.pl --program=./another_program --pegs=5 --disks=15
=head1 AUTHOR
Ben Tilly (tilly on perlmonks)
Of course I have my own solution to offer. But given that I've had more time to think about this than anybody else, I'll not post that until tomorrow.
UPDATE: Added READMORE tag. I thought I had one, but Arunbear noticed that I did not. Fixed.
UPDATE: ambrus noticed that I had the wrong peg in an error message. Oops. Fixed.
