様々なプログラミング言語に手を出す時に、とりあえず書いてみているのが「ハノイの塔」である。 仕様としては、引数として、円盤の枚数をとり、省略時には3が指定されたものとする。 円盤の移動の手順を表示し、可能であればかかった経過時間を表示する。 円盤の移動は、1番の軸から2番の軸へ行うものとして、3番の軸を作業用に使用することが出来る。

いわゆるハノイの塔は64枚の円盤と三本の柱からなる。 64枚の円盤は下のものから順に小さくなっており、同じ大きさの円盤はなく、円盤は自身より大きな円盤の上にしか置けない。 これを、1の柱に64枚全てが入った状態から始めて、2の柱にすべての円盤が移動完了した時点で完成となる。

言い伝え（？）によれば、バラモン僧たちが手でこれを行っており、完成するときが世界の終わりになるらしい。

数学的には、n枚の円盤からなる場合、n-1個の円盤を1から3へ移動し、n番目の円盤を1から2へ移し、n-1個の円盤を3から2へ移動するという、帰納的な解法で解くことができることが知られており、いわゆる再帰型プログラムの代表的な例題となっている。

PowerShellはWindowsにおいて、Cmd.EXEにかわる新しいコマンドシェルであり、また .NET Frameworkのフロントエンドでもある。 MicrosoftはWindows環境のみならず、Linuxなどへの展開も積極的に行っているようである。 ハノイの塔ごっこは、別に PowerShellから始めたわけでもないのに、これが最初に書かれているのは、このWikiのエントリーを作った時に書いたのが PowerShell版だから。

なお、PowerShell Coreでも同じコードを利用している。 PowerShell Coreは、PowerShell のオープンソース版で、GitHubにレポジトリがあるが、事実上提供されているバイナリパッケージでのみ利用する方向のようである。 ¹⁾

Hanoi.ps1として以下のコードを作成した。 なお、デジタル署名するのが面倒くさかったので、実行にあたっては、実行ポリシーをAllSignedからRemoteSignedに変更した。 ²⁾ 一般的な関数型言語が採用している、関数呼び出しと違い、引数を括弧でくくってカンマで区切ってはいけない。 括弧でくくってカンマで区切るとそれは配列として、関数の第一引数に全て渡されてしまう。 あくまでシェルスタイルの、関数名の後ろにスペース区切りで引数を列挙すること。 ³⁾

基本的に、1-pass型のスクリプト言語なので、前方参照はできない。なので、関数などは、先に定義しておいて、後から呼び出すPascal的なスタイルとなる。

なお、Param()は便利な機能だが、関数⁴⁾の先頭以外にはおけないことに留意が必要。 Param()の前にコードがあると、Param()がエラーとなる。 分かりにくいので、気づきにくいミス。

Param([Int]$n = 3)

function Hanoi 
{
    Param([Int]$discs,[Int]$a=1,[Int]$b=2,[Int]$c=3)
    if ($discs -eq 0)
    {
        return
    }
    [Int]$n = $discs - 1
    Hanoi $n $a $c $b
    Write-Output "Disc ${discs} moved from ${a} to ${b}."
    Hanoi $n $c $b $a
    return
}

$s = Get-Date
Hanoi $n
$e = Get-Date
$diff = $e - $s
$msec = $diff.TotalMilliseconds
Write-Output "Elapsed Time: ${msec} [msec]."

第2世代Core i7のVAIO Z2(VPCZ2)上のWindows 10/PowerShell 5.1.17763.592で実行した。

PS C:\Users\araki> .\Documents\Hanoi.ps1 -n 4
Disc 1 moved from 1 to 3.
Disc 2 moved from 1 to 2.
Disc 1 moved from 3 to 2.
Disc 3 moved from 1 to 3.
Disc 1 moved from 2 to 1.
Disc 2 moved from 2 to 3.
Disc 1 moved from 1 to 3.
Disc 4 moved from 1 to 2.
Disc 1 moved from 3 to 2.
Disc 2 moved from 3 to 1.
Disc 1 moved from 2 to 1.
Disc 3 moved from 3 to 2.
Disc 1 moved from 1 to 3.
Disc 2 moved from 1 to 2.
Disc 1 moved from 3 to 2.
Elapsed Time: 22.9854 [msec].

PS C:\Users\araki> 

言わずと知れたDOS由来のバッチコマンドによる実装である。 本来、リカーシブなコールなど書けないのだが、Windows NT以降の拡張でそれもなんとかこなせるようになっている。 プログラム言語として見たときに非常に非力なので、本来このようなことをさせることはないのだが、場合によっては、これしか使えないこともあるので、それなりに書けるスキルがあっても損はないだろう。

なお、実行速度は頭が痛くなるレベルである。

Hanoi.batとして以下のコードを作成した。 setlocal enabledelayedexpansionしているが、今コードを見返してみると全く必要性がないように思う。 おそらく、初期の実装でリカーシブな処理をするときに何かそのあたりの機能を使おうとした名残だと思われる。 :HANOIの中で、setlocalすることで、変数を関数ローカルにし、リカーシブな処理を実現している。 SET /A D=%1 - 1はDに%1 - 1を計算した値を設定するというコマンドで確かこれがNT由来の拡張機能だったはずなので、DOSのcommmand.comでは動作しないハズである。 経過時刻を求めるために、%TIME%環境変数を利用しているが、単純に時、分、秒に分解したときに、08や09という値は、八進数として扱われエラーとなる。 これを回避するために:NORMALIZEという関数を用意して、文字列08および09は、数値に置きかえるように処理している。

@echo off

setlocal enabledelayedexpansion

SET CMD=%~nx0
SET DISCS=3

:OPTPARSE
IF "%1" == "" GOTO MAIN
IF "%1" == "-h" GOTO HELP
IF "%1" == "-n" (
  SET DISCS=%2
  shift
)
shift
GOTO OPTPARSE

:MAIN
CALL :GETTIME
SET ST=%ERRORLEVEL%

CALL :HANOI %DISCS% 1 2 3

CALL :GETTIME
SET /A ET=%ERRORLEVEL% - %ST%

ECHO Elapsed Time %ET%0 msec. >&2

GOTO END

:HANOI
IF %1 == 0 EXIT /b
setlocal
SET /A D=%1 - 1
CALL :HANOI %D% %2 %4 %3
ECHO Disc %1 moved from %2 to %3
CALL :HANOI %D% %4 %3 %2
endlocal
exit /b

:GETTIME
CALL :NORMALIZE %TIME:~0,2%
SET H=%ERRORLEVEL%
CALL :NORMALIZE %TIME:~3,2%
SET M=%ERRORLEVEL%
CALL :NORMALIZE %TIME:~6,2%
SET S=%ERRORLEVEL%
CALL :NORMALIZE %TIME:~9,2%
SET MS=%ERRORLEVEL%

SET /A T1=%H% * 360000 + %M% * 6000 + %S% * 100 + %MS%

EXIT /b %T1%

:NORMALIZE
SET V=%1
SET V=%V:08=8%
SET V=%V:09=9%
EXIT /b %V%


:HELP
echo %CMD% :-
echo ^    -n ^<NUM^>: Number of discs.
echo ^    -h : show this message.
GOTO END

:END

endlocal
echo on

PowerShell版と同じ環境で実行したが、恐ろしく遅い。

C:\Users\araki\Documents>Hanoi -n 4
Disc 1 moved from 1 to 3
Disc 2 moved from 1 to 2
Disc 1 moved from 3 to 2
Disc 3 moved from 1 to 3
Disc 1 moved from 2 to 1
Disc 2 moved from 2 to 3
Disc 1 moved from 1 to 3
Disc 4 moved from 1 to 2
Disc 1 moved from 3 to 2
Disc 2 moved from 3 to 1
Disc 1 moved from 2 to 1
Disc 3 moved from 3 to 2
Disc 1 moved from 1 to 3
Disc 2 moved from 1 to 2
Disc 1 moved from 3 to 2
Elapsed Time 250 msec.

C:\Users\araki\Documents>

何はなくともC言語である。 特に何の工夫もなく、教科書に出ているようなサンプルのコードを実装した。 「実装した」といったが、どういうわけか、ソースが失われてバイナリだけが残っている。 別に、新しく書いてもいいんだけれど、面倒クサイので、コードはそのうち発掘されたら掲載する。 なので、今は何もない。 Cのコードくらいすぐ書けるわ！ ということで、帰宅中の東海道線の中で書いたので掲載しておく。

多分こんなだったと思い出しながら書いた。 getopt()を使ったはずだけれど、違ったかも知れない。 本体はHanoi()関数であり、それ以外の部分は全て冗長である。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <libgen.h>


char *cmd = NULL;
void
usage(void)
{
    fprintf(stderr, "%s:-\n"
                    "\t-n <int>: set number of discs. (default: 3)\n"
                    "\t-h: show this message.\n", cmd);
    exit(1);
}

void
Hanoi(int discs, int a, int b, int c)
{
    int n = discs - 1;
    if (discs == 0)
    {
        return;
    }
    Hanoi(n, a, c, b);
    printf("Disc %d moved from %d to %d\n", discs, a, b);
    Hanoi(n, c, b, a);
}

void
main(int argc, char *argv[])
{
    int c;
    opterr = 0; /*disable error log */
    int n = 3;
    cmd = basename(argv[0]);

    while ((c = getopt(argc, argv, "n:h")) != -1)
    {
        switch (c)
        {
            case 'h':
                usage();
                break;
            case 'n':
                n = strtol(optarg, NULL, 0);
                break;
            default:
                usage();
                break;
        }
    }
    Hanoi(n, 1, 2, 3);
    exit(0);
}

当たり前だが、非力なCeleron N3150環境下でも速い。 速すぎて計測に意味がない。 多分、-n 20くらいでやった方がいいんだろうと今更思う。

araki@chive[117]% time ./hanoic -n 4
Disc 1 moved from 1 to 3.
Disc 2 moved from 1 to 2.
Disc 1 moved from 3 to 2.
Disc 3 moved from 1 to 3.
Disc 1 moved from 2 to 1.
Disc 2 moved from 2 to 3.
Disc 1 moved from 1 to 3.
Disc 4 moved from 1 to 2.
Disc 1 moved from 3 to 2.
Disc 2 moved from 3 to 1.
Disc 1 moved from 2 to 1.
Disc 3 moved from 3 to 2.
Disc 1 moved from 1 to 3.
Disc 2 moved from 1 to 2.
Disc 1 moved from 3 to 2.
0.001u 0.003s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
araki@chive[118]%

Cが来たらばとりあえずC++でも書くだろう。

とりあえず、C++らしく、Hanoiをクラスにして、円盤の枚数を持ったインスタンスを作り、run関数を呼び出して実行する。 外向き(public)のrunは引数を持たないが、内部で再帰的に呼び出される方は、引数を持っている。 このあたりちょっとC++っぽく書いてある。 Boostを使っているのは、コマンドライン引数の処理をしてくれる手頃なライブラリだからというだけで、別にGNU のparseoptなんかを使っても良かったのだが、まあ、そんな感じで、多分このせいでCに比べてやや遅くなっている。

#include <iostream>
#include <string>
#include <boost/program_options.hpp>

class Hanoi
{
protected:
  int _size;
  void run(int n, int a, int b, int c) const
  {
    if (n == 0) return;
    run(n - 1, a, c, b);
    std::cout << "Disc " << n << " moved from " << a << " to " << b << std::endl;
    run(n - 1, c, b, a);
  }
public:
  Hanoi(int size = 3)
  {
     _size = size;
  }

  inline int size() const { return _size; }
  inline void run(void) const { return run(_size, 1, 2, 3); }
};

int
main(int argc, char *argv[])
{
  boost::program_options::options_description opt("Options");
  opt.add_options()
    ("help,h", "Show this message.")
    ("size,n", boost::program_options::value<int>()->default_value(3), "Number of discs.")
    ;
  boost::program_options::variables_map maps;
  boost::program_options::store(parse_command_line(argc, argv, opt), maps);
  boost::program_options::notify(maps);
  if (maps.count("help"))
  {
    std::cerr << opt << std::endl;
    return 1;
  }
  int size = maps["size"].as<int>();
  Hanoi *hanoi = new Hanoi(size);
  hanoi->run();
  return 0;
}

araki@chive[131]% time ./hanoicc -n 4
Disc 1 moved from 1 to 3
Disc 2 moved from 1 to 2
Disc 1 moved from 3 to 2
Disc 3 moved from 1 to 3
Disc 1 moved from 2 to 1
Disc 2 moved from 2 to 3
Disc 1 moved from 1 to 3
Disc 4 moved from 1 to 2
Disc 1 moved from 3 to 2
Disc 2 moved from 3 to 1
Disc 1 moved from 2 to 1
Disc 3 moved from 3 to 2
Disc 1 moved from 1 to 3
Disc 2 moved from 1 to 2
Disc 1 moved from 3 to 2
0.005u 0.003s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
araki@chive[132]%

C、C++と来たら、Objective Cで書かないわけにはいかないでしょう？ そうでもない？ Objective Cは、NeXT STEPとか、初期のMacOS XやiOSの開発言語というイメージで、C++程はメジャーになれなかった印象ですが、よく考えてみればiOSの開発言語だったんだから十分にメジャーですな。

こういっては何ですが、後にも先にもObjective Cのコードはこれだけしか書いたことがありません。 @interfaceとか@implementationとかで、定義と実装とを分けているんですね。 でも、なんというか、C言語との食い合わせがいまいちなスタイルで、これが好きになれなかったんですよね。

#import <stdio.h>
#import <unistd.h>
#import <stdlib.h>
#import <objc/Object.h>

@interface Hanoi : Object
{
  int size;
}
- (id)init;
- (id)initWithN:(int)sz;
- (void)run;
- (void)run:(int)n:(int)a:(int)b:(int)c;
@end

@implementation Hanoi
- (id)init {
  [super init];
  return [self initWithN:3];
}
- (id)initWithN:(int)sz {
  self->size = sz;
  return self;
}
- (void)run {
  [self run:self->size:1:2:3];
}

- (void)run:(int)n:(int)a:(int)b:(int)c {
  if (n == 0) return;
  [self run:n-1:a:c:b];
  printf("Disc %d moved from %d to %d.\n", n, a, b);
  [self run:n-1:c:b:a];
}
@end

int
main(int argc, char *argv[])
{
  int opt;
  int opt_size = 3;
  char *e;
  while ((opt = getopt(argc, argv, "hn:")) >= 0)
  {
    switch(opt)
    {
      case 'h':
      case '?':
        fprintf(stderr, " -n <NUM>: Number of discs.\n");
        fprintf(stderr, " -h: show this message.\n");
        exit(1);
        break;
      case 'n':
        opt_size = strtol(optarg, &e, 10);
        break;
    }
  }
  id hanoi = [[Hanoi alloc] initWithN:opt_size];
  [hanoi run];
}

どういうわけか、SIGSEGVで落ちるようになってしまいました。

Common Lispといえば、リスト操作言語であり、ハノイの塔なんか解いている場合ではないのだけれど、やろうと思えば出来るというサンプルである。 勿論、本体は hanoi 関数であり、それ以外は、コマンドラインの走査だったり、余分なのだが、余分の方が大勢を占めている。 とはいえ、これはいろんな言語とその処理系を学ぶための素材なので、こういう部分も大事だったりする。 個人的には、(progn )はあんまりすきじゃないのだが、使わないで書く方法が思いつかなかったので、使っている。

Lispの特徴はリスト操作につきるのだが、本体のhanoi関数ではほとんど使わず、引数を走査しているparseの方が多く使っているのがご愛敬。 そもそも、こういう題材に向いている言語ではないんだよね。 Quick Sortとか書くと Lispっぽくていいんだけれどね。

;
(defun hanoi (n a b c)
  (if (> n 0)
      (progn
        (hanoi (1- n) a c b)
        (print (format t "Disc ~D moved from ~S to ~S." n a b))
        (hanoi (1- n) c b a)
        t
      )
      t
  )
)

(defun parse (args)
  (setq r nil)
  (loop
    (if (null args) (return r))
    (setq arg0 (car args)
          args (cdr args))
    (if (or (string= arg0 "-n") (string= arg0 "--size"))
        (setq r (parse-integer (car args))
              args (cdr args))
    )
  )
)
(setq n (parse *args*))
(print n)
(if (null n) (setq n 3))

(hanoi n '1 '2 '3)

araki@chive[171]% time clisp hanoi.cl -n 4

4 Disc 1 moved from 1 to 3.
NIL Disc 2 moved from 1 to 2.
NIL Disc 1 moved from 3 to 2.
NIL Disc 3 moved from 1 to 3.
NIL Disc 1 moved from 2 to 1.
NIL Disc 2 moved from 2 to 3.
NIL Disc 1 moved from 1 to 3.
NIL Disc 4 moved from 1 to 2.
NIL Disc 1 moved from 3 to 2.
NIL Disc 2 moved from 3 to 1.
NIL Disc 1 moved from 2 to 1.
NIL Disc 3 moved from 3 to 2.
NIL Disc 1 moved from 1 to 3.
NIL Disc 2 moved from 1 to 2.
NIL Disc 1 moved from 3 to 2.
NIL
0.013u 0.021s 0:00.03 100.0%    0+0k 0+0io 0pf+0w
araki@chive[172]% 

Prolog本体のコードは非常に短い。 Prologは、マッチするパターンを探して、それを実行する。 ハノイの塔のような再帰プログラムの場合は、再帰の打ち切り条件に相当するものを最初に定義して、それ以外の部分をそのあとに定義する。 こうすることで、打ち切り条件になるまでは再帰のコードを実行し、打ち切り条件になったら先頭の何もしないコードが呼び出され、再帰を逆にたどって元に返る。 きっとカットオペレータとか使う方法もあるんだろうけれど、カットオペレータが入ると途端に読みにくくなるので、よくわからないのです。

GNU Prologの場合ブートストラップコードをCで書くことが出来るので、コマンドライン引数の処理なんかはそっちでやっているから、本体だけしかないのでこのようになっている。 参考までにブートストラップのコードも載せておく。

hanoi(0,A,B,C) .
hanoi(N,A,B,C) :- N1 is N -1, hanoi(N1, A, C, B), format('Disc ~d moved from ~d to ~d\n', [N, A, B]), hanoi(N1, C, B, A) .

/*
 * Prolog Wrapper
 */

#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>
#include <gprolog.h>


#define SOL_SIZE_DEFAULT 10000
#define SOL_SIZE_STEP    10000
int
Main_Wrapper(int argc, char *argv[])
{
  int size = 3;
  int sol_size = SOL_SIZE_DEFAULT;
  int i, p, opt;
  int hanoi;
  PlTerm arg[4];
  char *sol = NULL;
  PlBool res;

  while ((opt = getopt(argc, argv, "n:h")) != -1)
  {
    switch (opt)
    {
    case 'n':
      size = strtol(optarg, NULL, 0);
      break;
    case 'h':
    default:
      fprintf(stderr, " -n <NUM>: Number of discs.\n -h: show this message.\n");
      exit(1);
      break;
    }
  }

  Pl_Start_Prolog(argc, argv);
  hanoi = Pl_Find_Atom("hanoi");
  Pl_Query_Begin(PL_TRUE);
  arg[0] = Pl_Mk_Integer(size);
  arg[1] = Pl_Mk_Integer(1);
  arg[2] = Pl_Mk_Integer(2);
  arg[3] = Pl_Mk_Integer(3);
  res = Pl_Query_Call(hanoi, 4, arg);
  Pl_Query_End(PL_RECOVER);
  Pl_Stop_Prolog();
  return 0;
}

int
main(int argc, char *argv[])
{
    return Main_Wrapper(argc, argv);
}

araki@chive[177]% time ./hanoipro -n 4
Disc 1 moved from 1 to 3
Disc 2 moved from 1 to 2
Disc 1 moved from 3 to 2
Disc 3 moved from 1 to 3
Disc 1 moved from 2 to 1
Disc 2 moved from 2 to 3
Disc 1 moved from 1 to 3
Disc 4 moved from 1 to 2
Disc 1 moved from 3 to 2
Disc 2 moved from 3 to 1
Disc 1 moved from 2 to 1
Disc 3 moved from 3 to 2
Disc 1 moved from 1 to 3
Disc 2 moved from 1 to 2
Disc 1 moved from 3 to 2
0.010u 0.001s 0:00.01 100.0%    0+0k 0+0io 0pf+0w
araki@chive[178]%