Kinx アルゴリズム - ハノイの塔

はじめに

「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。「プログラム＝アルゴリズム＋データ構造」。アルゴリズムの実装例をご紹介。

元ネタは「C言語による（30年経っても）最新アルゴリズム事典」。今回はライフゲームです。

• 参考
  • 最初の動機 ... スクリプト言語 KINX（ご紹介）
    • 個別記事へのリンクは全てここに集約してあります。
  • リポジトリ ... https://github.com/Kray-G/kinx
    • Pull Request 等お待ちしております。

最新アルゴリズム事典にはこういうのも結構載ってる。パズル的な。

Kinx では最初のころにこのサンプルコードを書いて、再帰関数の確認に使った。良いテストになった。

ハノイの塔

• https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94

Wikipedia より

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

• 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
• 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

ソースコード

function movedisk(n, a, b) {
    if (n > 1) movedisk(n - 1, a, 6 - a - b);
    System.println("円盤 %d を %d から %d に移す" % n % a % b);
    if (n > 1) movedisk(n - 1, 6 - a - b, b);
}

const N = 4;
System.println("円盤 %d 枚を柱 1 から柱 2 に移す方法は"
        "次の %u 手です." % N % ((1 << N) - 1));
movedisk(N, 1, 2);

結果

円盤 4 枚を柱 1 から柱 2 に移す方法は次の 15 手です.
円盤 1 を 1 から 3 に移す
円盤 2 を 1 から 2 に移す
円盤 1 を 3 から 2 に移す
円盤 3 を 1 から 3 に移す
円盤 1 を 2 から 1 に移す
円盤 2 を 2 から 3 に移す
円盤 1 を 1 から 3 に移す
円盤 4 を 1 から 2 に移す
円盤 1 を 3 から 2 に移す
円盤 2 を 3 から 1 に移す
円盤 1 を 2 から 1 に移す
円盤 3 を 3 から 2 に移す
円盤 1 を 1 から 3 に移す
円盤 2 を 1 から 2 に移す
円盤 1 を 3 から 2 に移す

おわりに

こちらも C 言語版ほぼそのままです。GitHub は英語基準なのでこれまで文言を英語に直していましたが、一応日本語でも動くので、今回の上記のソースコードは日本語のままにしました。ただし GitHub に例としてコミットしているものは英語にしてあります。

ではまた、次回。