Tower of Hanoi

HOP perl algorithm

尊敬する友人が「Higher Order Perl」を買って読んでる、という話を聞いた。僕はHOPは「なんとなくめんど草そー」というか難しそうだったので避けてたんだけど、いい機会だから勉強してみようと買ってみる。こないだとどいた。最初と２つ目はすげー単純な10進 2進変換とか、順列組み合わせの数を再帰でやる、というありがちケース。次のハノイの塔も非常に有名なので・・・と思ったんだけど、どうやって自分でやるかふと迷った。
ので、これは読まずに自分でやってみようとか考え始める。

準備

とりあえず板を動かして表示するクラスを書いてみる（それMooseで。。。）

## Tower of Hanoi  --  Tower behavior & representation
##
package Hanoi;

use strict;
use warnings;

sub new {
	my ($class, $n) = @_;
	my $ref = {};

	$ref->{n} = $n;
	$ref->{peg} = [[1..$n], [], []];

	bless $ref, $class;
}

sub move {
	my ($self, $from, $to) = @_;
	my ($picked, $dst) = (shift @{$self->{peg}->[$from-1]},
			      $self->{peg}->[$to-1]);
	die "illegal move" if $dst->[0] && $picked > $dst->[0];
	unshift @$dst, $picked;
}

sub pad_string {
	my ($ary, $n, $padding) = @_;
	[($padding) x ($n - $#$ary -1), @$ary];
}

sub pad_pegs {
	my ($self) = @_;
	[map {pad_string($_, $self->{n}, "|")} @{$self->{peg}}];
}

sub transpose {
	my $ary = shift;
	my $ret = [];

	for my $i (0..$#$ary){
		my $j = 0;

		for my $c (@{$ary->[$i]}) {
			$ret->[$j] //= [];
			push @{$ret->[$j++]} , $c;
		}
	}
	$ret;
}

sub disp {
	my $self = shift;

	[map {join("  ",@$_)} 
		@{transpose($self->pad_pegs)}];
}

sub str {
	my $self = shift;

	join "\n", @{$self->disp};
}

sub print {
	my $self = shift;

	print join("\n", $self->str). "\n";
}

1;

まあちょっと確認目的だけだしいいか......
ついでにTest::Exceptionの練習がてらにテストも書いてみる。

## test for hanoi tower class    -- t/hanoi.t
##
use strict;
use Test::More tests => 8;
use Test::Differences;
use Test::Exception;

use_ok("Hanoi") or exit;

my $h = Hanoi->new(4);

isa_ok($h, "Hanoi");

ok($h->{n} == 4, "check size of Hanoi");

eq_or_diff (
    $h->pad_pegs,
    [[1,2,3,4],
     ["|","|","|","|"],
     ["|","|","|","|"]],
    'fill peg array with "|"');


eq_or_diff(
    $h->disp,
    [
     "1  |  |",
     "2  |  |",
     "3  |  |",
     "4  |  |",
    ],
    'display array reference');


$h->move(1,2);

eq_or_diff(
    $h->disp,
    [
     "|  |  |",
     "2  |  |",
     "3  |  |",
     "4  1  |",
    ],
    'just moving peg 1 to peg 2');

$h->move(1,3);
$h->move(2,3);
$h->move(1,2);
$h->move(3,1);

eq_or_diff(
    $h->disp,
    [
     "|  |  |",
     "|  |  |",
     "1  |  |",
     "4  3  2",
    ],
    'some more movement');

dies_ok {$h->move(2,1)} "illegal movement";

テスト開始。

quartz:pts/1% prove -v t                                                                                                       /home/kuro/Lang/Perl/Hanoi
t/Hanoi....
1..8
ok 1 - use Hanoi;
ok 2 - The object isa Hanoi
ok 3 - check size of Hanoi
ok 4 - fill peg array with "|"
ok 5 - display array reference
ok 6 - just moving peg 1 to peg 2
ok 7 - some more movement
ok 8 - illegal movement
ok
All tests successful.
Files=1, Tests=8,  0 wallclock secs ( 0.04 usr  0.01 sys +  0.04 cusr  0.01 csys =  0.10 CPU)
Result: PASS

よさ気。

本番

要するに i→jにn個移したかったら、i,jじゃないもう一本をkとして, i→ kに n-1個移す必要があるのだよね。

  A     B     C
  |     |     |
  *     |     |
 *2*    |     |
**3**   |     |

↑を↓にするには

  A     B     C
  |     |     |  
  |     |     *  
  |     |    *2* 
  |     |   **3**


その前に
  A     B     C
  |     |     |
  |     |     |
  |     *     |
**3**  *2*    |
こうなってないといけない

こうなってから**3**を Ｃに動かせばよいわけで。
素直に書くとこうか

use strict;
use warnings;

use Hanoi;

my $height_of_tower = 3;

my $hanoi = Hanoi->new($height_of_tower);

$hanoi->print;

sub hanoi {
  my ($from, $to, $n) = @_;
  my $another = (1+2+3)-$from-$to;
  if ($n == 1) { 
    $hanoi->move($from, $to);
	 print "-------------------\n";
    $hanoi->print;
    return;
  }
  hanoi($from, $another, $n -1);　# 一歩前の段階
  hanoi($from, $to, 1);           # 残った一枚（一番下）を目的のペグに移動
  hanoi($another, $to, $n -1);    # ↑にさっき動かした山を移動
}

hanoi(1,3, $height_of_tower);　　# 全部を1→3に移動（スタート）

やってみる

|  |  |
2  |  |
3  |  1
-------------------
|  |  |
|  |  |
3  2  1
-------------------
|  |  |
|  1  |
3  2  |
-------------------
|  |  |
|  1  |
|  2  3
-------------------
|  |  |
|  |  |
1  2  3
-------------------
|  |  |
|  |  2
1  |  3
-------------------
|  |  1
|  |  2
|  |  3
-------------------

ありゃ、簡単にできてしまった。なんかつまらない。というかやはり再帰って考え方は恐ろしく強力だと改めて思った。