Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Hanoi Challenge

by blokhead (Monsignor)
on Oct 22, 2004 at 19:10 UTC ( #401639=note: print w/replies, xml ) Need Help??


in reply to Hanoi Challenge

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

Replies are listed 'Best First'.
Re^2: Best possible counts for a few test cases (in readmore) (Hanoi Challenge)
by tye (Sage) on Oct 22, 2004 at 20:18 UTC

    It can be done more efficiently than this. You shouldn't divide the work up evenly. Below are some special cases and the smallest solution sizes possible (I believe) for them.

    If P is the number of pegs, D is the number of disks, and M is the minimum number of moves for which a solution exists, then:

    I may write up why this is so, but I suspect someone else is likely to beat me to that. And if you try to figure out why I picked these cases, you'll probably have a good hint for part of a good solution for the general problem. (:

    - tye        

      I was just realizing something along these lines. It would be better to give a larger proportion of disks to the subpiles which will have more scratch space. How much more, I don't exactly know (yet). I've been trying to come up with a simple way to minimize the recurrence for the general case, but no luck.

      If all else fails, you could search through all partitions of N-1 to find the best subproblem split, but that's no fun ;)

      blokhead

Re^2: Hanoi Challenge
by tilly (Archbishop) on Oct 22, 2004 at 20:21 UTC
    I'd suggest revisiting your analysis of how good 4 pegs are. With your program I see:
    10 disks with 4 pegs: Solved in 57 moves 20 disks with 4 pegs: Solved in 1137 moves 30 disks with 4 pegs: Solved in 33377 moves 40 disks with 4 pegs: Solved in 1050849 moves
    That doesn't look like O(n*log(n)) to me!

    Does anyone else think that they can do better?

Re^2: Hanoi Challenge
by Elgon (Curate) on Oct 22, 2004 at 19:50 UTC
    Blokhead,

    A query; Surely it is possible only to solve the problem in exactly O(n) when there is one more peg than discs plus one. (It could be that I misunderstand the O(n), O(log n), O(n^2) notation...)

    Example: In the quickest solution for three pegs and three discs, for example, the large disc moves once, the medium disc moves twice and the smallest disc moves four times.

    Example 2: Where there are three rings and four pegs, each ring only moves twice.

    Elgon

    UPDATE:Thanks to Thor for pointing out my error, below. As a general rule, I find that for n pegs and n discs the number of moves required is 2n + 1. If, however, there are n discs and n + 1 (or more) pegs, then 2n - 1 moves are required. Can someone with a better understanding of the formalisms tell me whether either of these is O(n) ???

    It is better either to be silent, or to say things of more value than silence. Sooner throw a pearl at hazard than an idle or useless word; and do not say a little in many words, but a great deal in a few.

    Pythagoras (582 BC - 507 BC)

      Example 2: Where there are three rings and four pegs, each ring only moves twice.
      Does it? If we're trying to get ring C to peg 4
      A -> 1
      B -> 2
      C -> 4
      B -> 4
      A -> 4
      
      In the case of n disks and n+1 pegs, the last disk moves only once.

      thor

      Feel the white light, the light within
      Be your own disciple, fan the sparks of will
      For all of us waiting, your kingdom will come

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://401639]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (6)
As of 2021-12-07 18:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    R or B?



    Results (34 votes). Check out past polls.

    Notices?