いろんな言語でハノイの塔

概要

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

ハノイの塔

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

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

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

性能

言語	バージョン	CPU	OS	`-n 4`の実行時間[ms]
PowerShell	5.1.17763.592	Core i7-2620M (2.70GHz)	Windows 10 Pro (1809)	22.9854
PowerShell Core	6.2.0	ARMv7	Deban 9	74.4272
Cmd.exe	10.0.17763.592	Core i7-2620M (2.70GHz)	Windows 10 Pro (1809)	250
C (gcc)	4.9.3	Celeron N3150 (1.60GHz)	Vine Linux 6.5	3
C++ (g++)	4.9.3	Celeron N3150 (1.60GHz)	Vine Linux 6.5	8
Objective C (gcc)	4.9.3	Celeron N3150 (1.60GHz)	Vine Linux 6.5	-
Common Lisp	2.49	Celeron N3150 (1.60GHz)	Vine Linux 6.5	34
GNU Prolog	1.4.4	Celeron N3150 (1.60GHz)	Vine Linux 6.5	11
RVTL (Tiny BASIC)	4.01	Celeron N3150 (1.60GHz)	Vine Linux 6.5	7
Perl	5.12.3	Celeron N3150 (1.60GHz)	Vine Linux 6.5	14
Ruby	1.8.7	Celeron N3150 (1.60GHz)	Vine Linux 6.5	32
Python	2.6.6	Celeron N3150 (1.60GHz)	Vine Linux 6.5	52
bash	4.3.42	Celeron N3150 (1.60GHz)	Vine Linux 6.5	122
awk (gawk)	3.1.8	Celeron N3150 (1.60GHz)	Vine Linux 6.5	8
go	1.16.0	Core i3 5010U (2.1GHz)	Ubuntu 20.4 LTS	0.004
Rust	1.47.0	Core i3 5010U (2.1GHz)	Ubuntu 20.4 LTS	0.004

プログラム

PowerShell

能書き

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

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

コード

Hanoi.ps1として以下のコードを作成した。なお、デジタル署名するのが面倒くさかったので、実行にあたっては、実行ポリシーをAllSignedからRemoteSignedに変更した。 ²⁾ 管理者権限を使ってシステム全体のポリシーを変更するのがコワイ場合は、

PS C:\Users\araki> Set-ExecutionPolicy RemoteSignedd -Scope Process

のようにして、実行中のプロセス内でのみ許可することも出来る。この方法には管理者権限は不要なので、気軽にスクリプトを試すことが出来る。

一般的な関数型言語が採用している、関数呼び出しと違い、引数を括弧でくくってカンマで区切ってはいけない。括弧でくくってカンマで区切るとそれは配列として、関数の第一引数に全て渡されてしまう。あくまでシェルスタイルの、関数名の後ろにスペース区切りで引数を列挙すること。 ³⁾

基本的に、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>

Batch (Cmd.exe)

能書き

言わずと知れた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 (gcc)

能書き

何はなくとも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++ (g++)

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]%

Objective C

能書き

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

能書き

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との最初の出会いは、月刊ASCIIに掲載されていたPC-8801向けの処理系をせっせと打ち込んで手に入れた時だと思う。当時高校生だったと思うが、さっぱりPrologの考え方が分からないで、サンプルをちょいちょい打ち込んで動かして、あとはすっかり忘却してしまっていた。 Prologはパターンマッチングで動作し、そのパターンをプログラム自身が生成することが出来るので、人工知能向きの言語といわれていたが、Prologを実装するのに使っているCなどでもその動作を実現できるので、結果からいうとより高速な処理系にその役割を譲ることになり、今日に至る。

コード

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]%

Tiny BASIC

能書き

Tiny BASICは、非常にコンパクトなBASIC系の言語です。基本的にBASICなので、再帰など普通に扱うことはできませんが、その辺はローカル変数に相当するものを配列を使って、自分で再帰レベルを管理しながら処理することで、擬似的に再帰処理を実現しています。

コード

コードにはコメントをつけてあります。引数はなんとなくそんな感じになるように処理していますが、適当なので、あまり追求しないでください。

#!/usr/bin/env rvtlw
1000 !=^GETARG       : Set Number of Discs
1010 N=0             : Nesting Level
1020 T=*             : Pseudo Stack pointer
1030 A=1             : Pole #1
1040 B=2             : Pole #2
1050 C=3             : Pole #3
1060 *=*+(32*16)     : Stack size == 32 nest levels * 16bytes
1070 !=^HANOI        : Call HANOI(S, A, B, C)
1080 #=-1            : STOP
1090 ^HANOI          : Function HANOI(S, A, B, C)
1100 ;=S=0 N=N-1 ]   : if (s == 0) return;   // Nesting level should be --N
1110 W=X             : Save stack pointer to W
1120 X=T+(N*16)      : Setup stack pointer
1130 X(0)=S          : Push S
1140 X(1)=A          : Push A
1150 X(2)=B          : Push B
1160 X(3)=C          : Push C
1170 X(4)=N          : Push N
1180 X;1]=W          : Save stack pointer (64bit) / X[2]=W in case 32bit
1190 A=X(1)          : Setup arguments for recursive call
1200 B=X(3)
1210 C=X(2)
1220 S=X(0)-1
1230 N=X(4)+1        : Increase Nesting level
1240 !=^HANOI        : Call HANOI(N - 1, A, C, B)
1250 "Disc " ?=X(0) " moved from " ?=X(1) " to " ?=X(2) "." /
1260 A=X(3)          : Setup arguments for recursive call
1270 B=X(2)
1280 C=X(1)
1290 S=X(0)-1
1300 N=X(4)+1        : Increase Nesting level
1310 !=^HANOI        : Call HANOI(N - 1, C, B, A)
1320 X=X;1]          : Restore stack pointer
1330 ]               : return
5000 ^GETARG
5010 *=*+1024
5020 [=0
5030 s=&
5040 s*=\0
5050 ;=%=0 S=3 #=^NOARG
5060 i=0 S=0
5070 @
5080   S=S*10+(s(i)-$30)
5090   i=i+1
5100 @=(s(i)=0)
5110 ^NOARG
5120 [=1
5130 ]
#=1

実行結果

処理系が優秀だからか、あるいは、そもそも、関数呼び出しなどの処理が軽いからなのか、かなり高速だと思います。

araki@chive[109]% time ./hanoi.vtl -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.000u 0.007s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
araki@chive[110]%

Perl

能書き

スクリプト言語の雄。何はなくともPerl。とにかく一頃は何でもPerlで書かれていました。今も多く使われていると思います。 Perlは徐々に仕様を拡張してきた結果、同じ事をするのに様々なやり方があって、気をつけないとコードに一貫性がなくなってしまったり、人によって同じ結果を得るための書き方が違っていて、他人のコードが理解しずらかったりと、あまり保守性に優れているとは言いがたいので個人的には好きではありません。また、型を $やら @やら %やらで表現するのも、個人的には好みではありません。とはいえ、場合によっては Perlなら使ってよしだったりするので、好む好まないに関わらず、使わざるを得ない言語でもあります。

コード

Perl 5を使うのだから、クラスを使おう。と、いうことでクラスを使っています。 Hanoiはクラス(package)として定義されています。 Hanoiのインスタンスを作る際に円盤の枚数を宣言します。あとは、$hanoi→do;とするだけで、処理を行います。

#!/usr/bin/perl -w

use strict;

package Hanoi;

sub new {
    my $class = shift;
    my %args = @_;
    my $self = \%args || {};
    $self->{size} = 3 unless defined($self->{size});
    bless $self, $class;
}

sub size
{
    my $self = shift;
    $self->{size}
}

sub do
{
    my $self = shift;
    my $n = shift;
    my $a = shift || 1;
    my $b = shift || 2;
    my $c = shift || 3;

    $n = $self->{size} unless defined($n);
    die "Same Placement: $a, $b, and $c ." if ($a == $b || $b == $c || $c == $a);
    return if $n == 0;
    $self->do($n - 1, $a, $c, $b);
    print "Disc $n moved from $a to $b\n";
    $self->do($n - 1, $c, $b, $a);
}

package main;

use Getopt::Std;

my %opts = (n => 3);
getopts("n:h", \%opts);

if(defined($opts{h}))
{
    print <<EOS;
Usage: $0
    -n <NUM>: number of discs.
    -h: show this message.
EOS
    exit(1);
}

my $hanoi = new Hanoi(size => $opts{n});
$hanoi->do;
1;

実行結果

araki@chive[125]% time ./hanoi.pl -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.004s 0:00.11 9.0%      0+0k 32+0io 0pf+0w
araki@chive[126]%

Ruby

能書き

Perlが来たらRubyを出さないわけにはいかないでしょう。日本発のスクリプト言語であるRubyはオブジェクト指向言語でもあります。 Perlのように、Object指向的に書けるというのではなく、そもそも、全てのデータがオブジェクトになっています。

豊富なライブラリやRailsのようなフレームワークもあり、多くのアプリケーション開発に利用されています。 MastodonもRailsを利用しています。

すっきりと書ける反面、やや速度が遅いという面があります。

コード

特にひねりもなく、普通に実装してあります。特筆するべきこともないかと思います。

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
#
require 'optparse'

opts = {
  :size => 3
}
OptionParser.new do |opt|
  opt.on('-n', '--size=NUM', 'Number of discs.') do |v| opts[:size] = v.to_i end
  opt.parse!(ARGV)
end

class Hanoi

    attr_reader :size

    def initialize(n = 3)
        @size = n
    end

    def do(n = @size, a = 1, b = 2, c = 3)
        return if n == 0
        self.do(n - 1, a, c, b)
        print "Disc #{n} moved from #{a} to #{b}\n"
        self.do(n - 1, c, b, a)
    end

end

hanoi = Hanoi.new(opts[:size])
hanoi.do

実行結果

araki@chive[131]% time ./hanoi.rb -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.017u 0.015s 0:00.07 28.5%     0+0k 672+0io 0pf+0w
araki@chive[132]%

Python

能書き

Perl、Rubyと来たら、Pythonを出さないわけにはいかないでしょう。今日では恐らくPythonが最も広く使われているのではないかと思います。

Pythonもオブジェクト指向言語であり、Perlよりずっとすっきりと記述できます。

ただ、個人的には、インデントでブロックを構成する仕様が好きになれなくて、PythonでもRubyでもいいならRubyを使いたい派です。インデントによるブロックが嫌いなのは、エディタによっては、勝手にいくつかのスペースをタブに置きかえる場合があり、これが発動すると、見た目にはOKなブロックが実は破綻しているなど、コーディングに集中できないケースがあるからです。

こちらも、Perlに比べて、実行速度の面では劣る傾向があります。

コード

こちらも、特にひねりもない実装かと思います。 if name == 'main':で、hanoi.pyをスクリプトとして起動した場合にのみ有効となるコードが記述されています。つまり、クラスライブラリとそれに付随するサンプル、あるいはテストコードをひとまとめにしておくことも出来るのはなかなかに便利だと思います。

#!/usr/bin/env python

import optparse, sys

class Hanoi:
    """ Hanoi's tower """
    def __init__(self, size = 3):
        self.size = size

    def size(self):
        return self.size

    def do(self, n = None, a = 1, b = 2, c = 3):
        if n is None:
            n = self.size
        if a == b or b == c or c == a:
            print "Same placement: ", a, ", ", b, ", and ", c
            raise
        if n == 0:
            return
        self.do(n - 1, a, c, b)
        print "Disc", n, "moved from", a, "to", b
        self.do(n - 1, c, b, a)

if __name__ == '__main__':
    parser = optparse.OptionParser()
    parser.add_option('-n', '--size', help='Number of discs.', nargs=1, type='int', default=3, dest='size', action = 'store')
    args,r = parser.parse_args()

    hanoi = Hanoi(args.size)
    hanoi.do()

実行結果

araki@chive[146]% time ./hanoi.py -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.043u 0.009s 0:00.06 66.6%     0+0k 112+0io 0pf+0w
araki@chive[147]%

bash

能書き

bashは、Bone Shell (sh)に変わって、現在のUNIX系システムの標準シェルの地位を確保しているシェルです。シェルスクリプトはそれなりに強力であり、簡単な処理であれば、これだけでこなすことができます。シェルがないUNIX環境は事実上ないので、どんな環境でも実行できるポータビリティは魅力です。

もちろん、本格的なプログラム言語に比べて見劣りする部分も少なくないですが、DOSのバッチに比べればはるかに強力です。 PowerShellとであれば、いい勝負でしょうか。 PowerShellはパイプでオブジェクトも渡せるので、システムの機能をフルに引き出すという点ではbashに勝りますが、他は似たようなものでしょう。

コード

特に凝ったことはしていません。基本的には shでも動くんじゃないかと思います。関数の引数は関数ローカルになっているので、ローカル変数を使わない限り普通に再帰もおこなえます。このため再帰呼び出しの際に n = discs - 1のようにして、減算を1回にしている他の言語と違って、呼び出しの度に`expr ${1} - 1`して、ローカル変数を避けています。

#!/usr/bin/env bash

function hanoi()
{
    if [ ${1} -gt 0 ]; then
        hanoi `expr ${1} - 1` ${2} ${4} ${3}
        echo "Disc ${1} moved from ${2} to ${3}"
        hanoi `expr ${1} - 1` ${4} ${3} ${2}
    fi
}

size=3
while [ $# -gt 0 ]; do
    case $1 in
    "-h" | "--help")
        echo " -n <NUM>: Number of discs."
        echo " -h: show this message."
        exit 1
        ;;
    "-n" | "--size")
        size=$2
        shift; shift;
        ;;
    *)
        shift
    esac
done
hanoi ${size} 1 2 3

実行結果

araki@chive[152]% time ./hanoi.bash -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.051u 0.071s 0:00.13 92.3%     0+0k 0+0io 0pf+0w
araki@chive[153]%

awk

能書き

awkは、AT&Tのベル研で、エイホ、ワインバーガ、カーニハンの三人により開発された、CSV形式のデータなどの処理に特化したスクリプト言語である。一行野郎などと言われるように、本来は、単機能を実装したコマンドを、パイプでつないで、複雑な処理を実現するのが主な使い方であり、コードそのものをコマンドラインにタイプしてしまい、わざわざスクリプトファイルにしたりしないことも多い。

$ cat resul.txt | awk '{print $2;}' | sed -e "s/^(.*)$/'\1'/"

などのように、することで、ファイルの特定カラムの値を'でくくるなどの処理を簡単に行える。

言語仕様が単純なこともあって、処理はそれなりに早い。

また、パターンマッチングに正規表現が使えることも利点の一つである。

コード

普通の関数型言語の側面もあるので、そのまま、ストレートに実装してある。

#!/usr/bin/awk -f
function hanoi(n, a, b, c)
{
    if (n > 0) {
        hanoi(n-1, a, c, b);
        printf("Disc %d moved from %d to %d\n", n, a, b);
        hanoi(n-1, c, b, a);
    }
}

BEGIN {
    size = 3;
    for (i = 0 ; i < ARGC ; i++)
    {
        if (ARGV[i] == "-h" || ARGV[i] == "--help")
        {
            printf(" -n <NUM>: Number of discs.\n -h: show this message.\n");
            exit(1);
        }
        if (ARGV[i] == "-n" || ARGV[i] == "--size")
        {
            size = ARGV[++i];
        }
    }
    hanoi(size, 1, 2, 3);
}

実行結果

araki@chive[157]% time ./hanoi.awk -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.003u 0.005s 0:00.00 0.0%      0+0k 0+0io 0pf+0w
araki@chive[158]%

Go

能書き

Goは比較的新しいコンパイラ言語である。静的型付けを基本とする言語であるが、メモリ管理は言語側が行い、ガベージコレクションなどの機能も内包している。

関数型言語であり、構造体を使った、オブジェクト指向っぽい記述もできる。

コード

コマンドラインの引数をとるために flagを、表示の加工用に fmtモジュールを利用している以外は、コード内で完結している。

package main

import (
  "fmt"
  "flag"
)

type Discs int

type Hanoi struct {
    N Discs
    a int
    b int
    c int
}

func NewTower(n int) *Hanoi {
    h := new(Hanoi)
    h.N = Discs(n)
    h.a = 1
    h.b = 2
    h.c = 3
    return h
}

func (n Discs) doit(a int, b int, c int) {
    if n > 0 {
        (n - 1).doit(a, c, b)
        fmt.Printf("Disc %d moved from %d to %d.\n", n, a, b)
        (n - 1).doit(c, b, a)
    }
}

func (h Hanoi) run() {
    h.N.doit(h.a, h.b, h.c)
}

func main() {
    n := flag.Int("n", 3, "n <NUM>: Number of Discs.")
    flag.Parse()
    hanoi := NewTower(*n)
    hanoi.run()
}

実行結果

araki@cherry:~/work/Hanoi$ time ./hanoigo -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.

real    0m0.004s
user    0m0.005s
sys     0m0.001s
araki@cherry:~/work/Hanoi$

Rust

能書き

システム記述言語として注目を集めているRust。メモリの管理が静的に行われており、予期せぬメモリリークなどによるセキュリティホールなどを言語レベルで防止できる。

cargoを使用してひな型を作り、getoptsによるオプション処理を加えた。ハノイの塔本体部分より、オプションの処理部分のほうが大きい。なお、ハノイの塔部分に関しては特にオブジェクト指向的なつくりにはしていない。

コード

コードは、RubyやPythonなどのスクリプト型言語と似た感じになっているが、静的な片付けが行われているところが、これらの言語とは違っている。また、ガベージコレクションによる動的なメモリ管理ではなく、静的な管理が中心となる。

use getopts::Options;
use std::process;
use std::env;

fn print_usage(prog_name: &str, opts: Options)
{
    let brief = format!("Usage: {} [Options]", prog_name);
    print!("{}", opts.usage(&brief));
    process::exit(1);
}

fn hanoi(n: i32, a: i32, b: i32, c: i32)
{
    if n > 0
    {
        hanoi(n - 1, a, c, b);
        println!("Disc {} moved from {} to {}", n, a, b);
        hanoi(n - 1, c, b, a);
    }
}

fn main()
{
    let args: Vec<String> = env::args().collect();
    let program = args[0].clone();

    let mut opts = Options::new();
    opts.optopt("n","discs","Set number of discs.", "NUM");
    opts.optflag("h","help","show this message.");
    let matches = match opts.parse(&args[1..])
    {
        Ok(m) => { m }
        Err(f) => { panic!(f.to_string()) }
    };
    if matches.opt_present("h")
    {
        print_usage(&program, opts);
        return;
    }
    let n = match matches.opt_get_default::<i32>("n", 3)
    {
        Ok(t) => { t }
        Err(f) => { panic!(f.to_string()) }
    };
    hanoi(n, 1, 2, 3);
}

実行結果

araki@cherry:~/work/Hanoi/hanoi$ time target/debug/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

real    0m0.004s
user    0m0.003s
sys     0m0.001s
araki@cherry:~/work/Hanoi/hanoi$

¹⁾

ソースからビルドもできるようだが、ビルド可能な環境はバイナリーパッケージのある環境に限られているため。

²⁾

管理者権限でPowerShellを起動してPS C:\Windows\System32> Set-ExectionPolicy RemoteSignedとする。

³⁾

或いは、hanoi -discs $n のように引数を明示するやり方もある。

⁴⁾

スクリプトの引数の場合はスクリプト

目次

いろんな言語でハノイの塔

概要

ハノイの塔

性能

プログラム

PowerShell

能書き

コード

実行結果

Batch (Cmd.exe)

能書き

コード

実行結果

C (gcc)

能書き

コード

実行結果

C++ (g++)

能書き

コード

実行結果

Objective C

能書き

コード

実行結果

Common Lisp

能書き

コード

実行結果

Prolog

能書き

コード

実行結果

Tiny BASIC

能書き

コード

実行結果

Perl

能書き

コード

実行結果

Ruby

能書き

コード

実行結果

Python

能書き

コード

実行結果

bash

能書き

コード

実行結果

awk

能書き

コード

実行結果

Go

能書き

コード

実行結果

Rust

能書き

コード

実行結果