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...
Putting this together, we expect something like this:(disk): (peg from) -> (peg to)
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.$ ./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
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.#! /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)
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.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Hanoi Challenge
by blokhead (Monsignor) on Oct 22, 2004 at 19:10 UTC | |
by tye (Sage) on Oct 22, 2004 at 20:18 UTC | |
by blokhead (Monsignor) on Oct 22, 2004 at 20:30 UTC | |
by tilly (Archbishop) on Oct 22, 2004 at 20:21 UTC | |
by Elgon (Curate) on Oct 22, 2004 at 19:50 UTC | |
by thor (Priest) on Oct 22, 2004 at 20:16 UTC | |
Re: Hanoi Challenge
by tilly (Archbishop) on Oct 22, 2004 at 16:34 UTC | |
Re: Hanoi Challenge
by fruiture (Curate) on Oct 22, 2004 at 18:13 UTC | |
by tilly (Archbishop) on Oct 22, 2004 at 18:26 UTC | |
Re: Hanoi Challenge
by tilly (Archbishop) on Oct 23, 2004 at 17:04 UTC | |
Re: Hanoi Challenge
by ambrus (Abbot) on Oct 23, 2004 at 18:33 UTC |