Here's my attempt: 
#!/usr/bin/perl
use strict;

my $pegs  = shift;
my $disks = shift;

my @pegs = (0, 'A' .. 'Z')[1 .. $pegs];
my %pegs = map { $_ => [] } @pegs;
$pegs{A} = [ 1 .. $disks ];

move($disks, @pegs);

sub move {
    my ($num, $from, $to, @rest) = @_;

    return unless $num;

    if ($num == 1) {
        my $d = shift @{ $pegs{$from} };
        print "$d: $from -> $to\n";
        unshift @{ $pegs{$to} }, $d;
        return;
    }

    $num--;

    for my $i (0 .. $#rest) {
        move( int(($num + $#rest - $i)/@rest),
              $from => $rest[$i],
              @rest[ grep { $_ > $i } 0 .. $#rest ], $to);
    }

    my $d = shift @{ $pegs{$from} };
    print "$d: $from -> $to\n";
    unshift @{ $pegs{$to} }, $d;

    for my $i (reverse 0 .. $#rest) {
        move( int(($num + $#rest - $i)/@rest),
              $rest[$i] => $to,
              @rest[ grep { $_ > $i } 0 .. $#rest ], $from);
    }

}

[download]
Analysis: In the 3-peg version, we reduce the problem of moving N disks to a problem of moving N-1 disks. This is because we have only one peg of "scratch" space, and all disks on top of the largest one must go to the "scratch" peg.

With more than 3 pegs, we have more scratch space, so we can split the problem up more evenly between the multiple scratch pegs. So this is what we do here. When moving N disks, we split the N-1 disks above us as evenly as possible among the available scratch space. (this is the int(($num + $#rest - $i)/@rest) business, it's just a fancy way of splitting up the disks so that if the piles can't be divided exactly evenly, the first piles will get the extras). Then we move the bottom disk to the destination, and move the subpiles back (in reverse order of course!)

The problem is assigning the subproblems their scratch space. The trick is that if a subpile was moved after us, it has larger disks than us, and can be used for scratch. But we can't use subpiles that were moved before us, because they contain smaller disks. This is why we have the grep { $_ > $i } @rest. Of course, we can also use the source and destination pegs when appropriate, just like in the 3-peg case, so they are added to the scratch space in the recursive call as well.

We can get a great improvement from having more pegs: 

10 disks with 3 pegs: Solved in 1023 moves
10 disks with 4 pegs: Solved in 57 moves
10 disks with 5 pegs: Solved in 35 moves
10 disks with 6 pegs: Solved in 29 moves
10 disks with 7 pegs: Solved in 27 moves
10 disks with 8 pegs: Solved in 25 moves
10 disks with 9 pegs: Solved in 23 moves
10 disks with 10 pegs: Solved in 21 moves
10 disks with 11 pegs: Solved in 19 moves

[download]
In fact, going from 3 pegs to 4 pegs is the most important, because instead of reducing the problem size by 1, we split it roughly in half every time (having 2 scrach pegs). This takes us from exponential number of moves needed to O(n log n). Then as the number of pegs approaches the number of disks, we approach O(n) number of moves, which makes sense because we only need to move each disk at most twice.

blokhead

In reply to Re: Hanoi Challenge by blokhead
in thread Hanoi Challenge by tilly

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


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.