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

Re: [MacPerl] The Powers of Annoy



On Tue, Jan 11, 2000 at 08:14:31AM +0000, Bart Lateur wrote:
> 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.

Well, I can do something about that.

Here is an iterative implementation of the Towers of Hanoi.  It makes use
of the simple pattern of movements in the solution.  Every odd-numbered
movement involves the smallest disk, which always moves in the same
direction.  Every even-numbered movement is the only move available other
than moving the smallest disk.  The biggest disk is moved only once, so the
program counts up until this disk moves, and then counts back down to 0.

Each tower has a base of size $number+1; this simplifies the code when a
disk is being moved to an empty tower.

I stole your movedisk() function with minor changes.  This script has the
same output as yours.

#!perl -w

my $number = 3;
my $disk1 = 0;
my @towers = ([reverse 1..$number+1], [$number+1], [$number+1]);
my @letters = qw(A B C);

my $moves = 0;
my $dir = 1;

while (1) {
    my $from = $disk1;

    my $to = $from + 1;
    $to > 2 and $to = 0;

    $disk1 = $to;
    movedisk($from, $to);

    $moves += $dir;
    last if $moves <= 0;

    my $other = $from - 1;
    $other < 0 and $other = 2;

    if ($towers[$other][-1] < $towers[$from][-1]) {
        $to = $from;
        $from = $other;
    } else {
        $to = $other;
    }

    my $disk = movedisk($from, $to);
    if ($disk == $number) {
        $dir = -1;
    } else {
        $moves += $dir;
    }
}

sub movedisk {
    my($from, $to) = @_;
    push @{$towers[$to]}, my $disk = pop @{$towers[$from]};
    print "Moving disk $disk from pile $letters[$from] " .
      "to pile $letters[$to]\n";
    return $disk;
}

__END__


Ronald

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