Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
We are all familiar with the towers of hanoi puzzle. It was most recently discussed at Recursion: The Towers of Hanoi problem. 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:
$ ./ 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 ||= "./"; 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 =head1 SYNPOSIS [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 ./ -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 "./ 3 4" and expect to see a solution to the hanoi puzzle with 3 pegs and 4 disks. ./ This will execute "./ 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. ./ --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.

In reply to Hanoi Challenge by tilly

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?

What's my password?
Create A New User
Domain Nodelet?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (2)
As of 2022-01-18 08:32 GMT
Find Nodes?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:

    Results (52 votes). Check out past polls.