読者です 読者をやめる 読者になる 読者になる

Higer order perl 1_3

perl hop

1_3。ハノイの塔。いかにも再帰な問題ですね。
初めて学生の授業でやったときは意味不明でしたね。


大学院でプログラミングの授業で教えるお手伝いをした
ときに意味が完全に理解できました。再帰のすごさを知る
いい問題だと思います。


Mooseで書いてみたが、全然うまく使えていない。
そっちの意味では大反省ですね。

��package Hanoi;
use Moose;

has num => (
    is  => 'ro',
    isa => 'Int',
    required => 1,
);

has from => (
    is => 'rw',
    isa => 'ArrayRef',
);

has to => (
    is => 'rw',
    isa => 'ArrayRef',
);

has tmp => (
    is => 'rw',
    isa => 'ArrayRef',
);

has moves => (
    is => 'rw',
    isa => 'Int',
    default => 0,
);

sub BUILD {
    my $self = shift;

    $self->from([]);
    push @{$self->from}, reverse 1..($self->num);
    $self->to([]);
    $self->tmp([]);
}

__PACKAGE__->meta->make_immutable;

no Moose;

sub solve {
    my $self = shift;

    $self->_print_tower();
    $self->_solve($self->num, $self->from, $self->to, $self->tmp);
    $self->_print_tower();

    print "moves = ", $self->moves, "\n";
}

sub _print_tower {
    my $self = shift;

    print "A: [";
    print "@{$self->from}", "]\n";

    print "B: [";
    print "@{$self->tmp}", "]\n";

    print "C: [";
    print "@{$self->to}", "]\n";

    print "\n";
}

sub _solve {
    my ($self, $n, $from, $to, $tmp) = @_;

    if ($n == 1) {
        $self->_move_to($from, $to);
    } else {
        $self->_solve($n - 1, $from, $tmp, $to);
        $self->_move_to($from, $to);
        $self->_solve($n - 1, $tmp, $to, $from);
    }
}

sub _move_to {
    my ($self, $from, $to) = @_;

    push @{$to}, pop @{$from};
    $self->_print_tower();

    $self->moves( $self->moves + 1 );
}

package main;

my $hanoi = Hanoi->new( num => 5 );

$hanoi->solve();