Python歴3時間でハノイの塔

# 前提

- それなりに色々な言語経験があるがPythonは触ったこと無かった。
- 昼食後からPython入門してみようと思って練習問題を解き始めて、夕方にハノイの塔。
- 教材はGoogle先生。
- ハノイの塔は当然知っていたが、解き方は今回考えた。

# 問題
[ハノイの塔(Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94)
> 以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

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

今回はこれを

- 実際に動かして終了時の手数と状態を出力する。
- 机上の手数と実際の手数が等しいことを検証する。
- 一定タイミングで途中経過（現在の手数と塔の状態）を出力する。
- 塔の状態は「塔を右に90度回した状態」で出力する。ディスク無しは「-」を表示する。
- 塔の高さはハードコーディングで・・・

といった感じで作ってみます。

# 実装
``` Hanoi.py
import time
# ハノイの塔クラス
class Hanoi():
    def buildTower(self, N):
        # 塔の高さを取得
        self.N = N
        # 塔を建築
        self.tower = [[], [], []]
        for i in range(N): self.tower[0].append(i+1)
        # 必要手数を机上で計算
        self.T_MAX = 2**N-1
        # 進捗1/10ずつ、または5手ずつ経過を表示する
        self.T_MAX_DECI = max(int(self.T_MAX / 10), 5)
    def moved(self):
        # 手数を初期化
        self.T = 0
        # 開始宣言
        print("ハノイの塔[{0}]段を開始します。必要手数は[{1}]手です。".format(self.N, self.T_MAX))
        # 開始時刻取得
        self.START_TIME = time.time()
        # 再帰的に求める
        self.__hanoi(0, 2, self.N)
        # 結果出力
        print(self.toString())
        # 手数を検証
        assert self.T==self.T_MAX, "手数が想定と異なります。想定[{0}] 実際[{1}]".format(self.T_MAX, self.T)
        # 終了時刻取得
        self.END_TIME = time.time()
        # 完了のお知らせ
        print("\n移動が完了しました。実施手数は[{0}]手、所要時間は[{1}]ミリ秒でした。".format(str(self.T), round((self.END_TIME-self.START_TIME)*1000,4)))
    def __hanoi(self, moto, saki, disk):  # ここが再帰
        if(disk>1):  # より小さいディスクをどかす
            self.__hanoi(moto, (3-moto-saki), disk-1)
        self.__move(moto, saki, disk)  # 目的のディスクを動かす
        if(disk>1):  # どかしたディスクを戻す
            self.__hanoi((3-moto-saki), saki, disk-1)
    def __move(self, moto, saki, disk):
        # 移動予定のディスクを検証
        assert self.tower[moto][0]==disk, "動かそうとしているディスクが想定と異なります、想定[{0}] 実際[{1}]".format(str(disk), self.tower[moto][0])
        # 移動先のサイズを検証
        assert len(self.tower[saki])==0 or self.tower[saki][0]>disk, "小さいディスクの上に大きなディスクを載せようとしています。移動ディスク[{0}] 移動先[{1}]".format(disk, self.tower[saki][0])
        # 移動する
        self.tower[saki].insert(0, self.tower[moto].pop(0))
        self.T += 1
        # 経過出力
        if(self.T%self.T_MAX_DECI == 0): print(self.toString())
    def toString(self):
        result = []
        result.append("\n[{0}]手目".format(self.T))
        for i in range(3):
            if(len(self.tower[i])==0):
                result.append('-')
            else:
                self.tower[i].reverse()  # 逆順にする
                result.append(' '.join([str(i) for i in self.tower[i]]))
                self.tower[i].reverse()  # 戻しとく
        return '\n'.join(result) 

# メイン処理
def main():
    # インスタンス化
    hanoi = Hanoi()
    # 建築
    hanoi.buildTower(8)
    # 移動
    hanoi.moved()

# メイン処理を実行
if __name__ == '__main__':
    main()
```

# 感想

- 他言語の経験があれば直感的に使える、調べられる部分が多い。
- {}で括らないのが新鮮。誰もが正しいインデントを強制されると思うと飯が美味い。
- 配列やオブジェクトの感じがJavaScriptに似ていてやりやすい。
- 配列同士の連結はやりやすいが、配列を連結して文字列にするのが結構面倒くさい。
- 1行で複数の変数に値を代入出来るのがとても便利。
- メソッドの第一引数にselfを強制される理由がよくわからなかった。他言語のthis的にself使えれば良いのに。

# コメントで教えていただいたこと

- お作法的に、メイン処理（他言語で言うところのmain()の処理）は`if __name__ == '__main__':`の中で実行する。  
`__name__`は実行時に自動で設定されて、直接叩いた場合に`__main__`が入る。  
これを指定することで他のプログラムから再利用される(importされる)場合にメイン処理が走らない。