問題3.4

ハノイの塔。懐かしい。
某国営放送N○Kの入社試験で出題された記憶。笑。
学生時代からテレビ無かったので、面接で好きなテレビ番組聞かれて答えられずに落ちました^ ^;

問題

古典的なハノイの塔の問題では、3つの塔とN枚のサイズの異なる円盤を用いて塔の間を移動させます。最初は円盤が下から上に向かって小さくなるように(どの円盤も自身より大きな円盤の上に乗っているように)なっています。そして以下のような制約を持ちます。

(1) 一度に1枚の円盤しか動かせない。
(2) 塔の一番上にある円盤を他の塔に移動させる。
(3) 円盤を置くときは、それ自身より大きなものの上にしか置けない。

スタックを用いて、最初の塔に積み上がっている円盤を最後の塔に移動させるプログラムを書いてください。

doctestって1行にすればfor文とか使えるんですね。これはいいことに気がついた。

#encoding: utf-8


class Tower():
    '''
    ハノイの塔を解くクラス。再帰使用。
    >>> DISK_NUM = 1
    >>> towers = []
    >>> for tower_num in range(0, 3): towers.append(Tower())
    >>> for disk_num in range(0, DISK_NUM): towers[0].add_disk(disk_num)
    >>> towers[0].move_disks(DISK_NUM, towers[2], towers[1])
    >>> towers[0].show_disks()
    >>> towers[2].show_disks()
    0
    >>> DISK_NUM = 2
    >>> towers = []
    >>> for tower_num in range(0, 3): towers.append(Tower())
    >>> for disk_num in range(0, DISK_NUM): towers[0].add_disk(disk_num)
    >>> towers[0].move_disks(DISK_NUM, towers[2], towers[1])
    >>> towers[0].show_disks()
    >>> towers[2].show_disks()
    0
    1
    >>> DISK_NUM = 3
    >>> towers = []
    >>> for tower_num in range(0, 3): towers.append(Tower())
    >>> for disk_num in range(0, DISK_NUM): towers[0].add_disk(disk_num)
    >>> towers[0].move_disks(DISK_NUM, towers[2], towers[1])
    >>> towers[0].show_disks()
    >>> towers[2].show_disks()
    0
    1
    2
    '''
    def __init__(self):
        # ディスク格納用スタック。
        self.disks_stack = []

    # タワーのトップのディスクをtarget_towerに移動。
    def _move_top(self, target_tower):
        target_tower.add_disk(self.disks_stack.pop())

    # diskをタワーに追加。
    def add_disk(self, disk):
        self.disks_stack.append(disk)

    # selfからtarget_towerへディスクを移動。buffer_towerを一時バッファとして使用。
    def move_disks(self, index, target_tower, buffer_tower):
        if index > 0:
            self.move_disks(index - 1, buffer_tower, target_tower)
            self._move_top(target_tower)
            buffer_tower.move_disks(index - 1, target_tower, self)
        else:
            pass

    # タワーのスタックに格納されたディスクの表示
    def show_disks(self):
        count = 0
        while len(self.disks_stack) > count:
            print self.disks_stack[count]
            count += 1


def _test():
    import doctest
    doctest.testmod()


if __name__ == '__main__':
    _test()