[Date Prev][Date Next][Thread Prev][Thread Next] [Search] [Date Index] [Thread Index]

Re: [MacPerl] The Powers of Annoy



On Mon, 10 Jan 2000 21:40:44 +0200, miku wrote:

>P.S. Do you know a PERL Hanoi implementation that makes use of recursion?

In fact, that's the only implementation I know.

For the people who are not familiar with the problem: you have a pile of
disks of decreasing size, largest disk on the bottom. The intention is
to move this pile from position A to position C, with help of an
auxiliary position B. You may move one disk at a time, and a larger disk
may NEVER be on top of a smaller one.

So how do you move a pile (n items) from A to C? Well, you need to get
the largest disk at the bottom, from A to C. So you need to move the
pile on top of that disk (n-1 items) to B first. How do you move a pile
from A to B? By making sure the bottom disk gets from A to B, so you
need to move the pile on top of that (n-2 items) to C first. Etc...
until the problem is to move just one disk.

So on paper, the problem is solved. All you still need the computer for,
is the footwork. For some bizarre reason, this problem is teached in
classes of Artificial Intelligence, but there is nothing remotely
resembling machine intelligence involved. It's only footwork.

Here's my solution. Just for kicks, I've changed the use of a string to
anonymous arrays. You may change $number to move larger piles. The
traditional value is 3.

    #! perl -w
    my $number = 3;
    my @pile = ([reverse (1..$number)], [], []);
    my @letter = qw(A B C); # pile names
    movepile(0, 2, 1, $number);

    sub movepile {
        my($from, $to, $aux, $depth) = @_;
        if($depth>1) { # more than 1 disk
            movepile($from, $aux, $to, $depth-1);
            movedisk($from, $to);
            movepile($aux, $to, $from, $depth-1);
        } else {
            movedisk($from, $to);
        }
    }

    sub movedisk {
        my($from, $to) = @_;
        push @{$pile[$to]}, my $disk = pop @{$pile[$from]};
	print "Moving disk $disk from pile $letter[$from] ".
	  "to pile $letter[$to]\n"; # split for message wordwrap
    }
__END__
Moving disk 1 from pile A to pile C
Moving disk 2 from pile A to pile B
Moving disk 1 from pile C to pile B
Moving disk 3 from pile A to pile C
Moving disk 1 from pile B to pile A
Moving disk 2 from pile B to pile C
Moving disk 1 from pile A to pile C

-- 
	Bart.

# ===== Want to unsubscribe from this list?
# ===== Send mail with body "unsubscribe" to macperl-request@macperl.org