Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
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); } }
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
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":



  • 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 How to display code and escape characters are good places to start.
Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (8)
As of 2024-03-29 08:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found