hanoi.md

「ハノイの塔」を解く

hanoi.py

"""ハノイの塔を解決するプログラム
"""

# 最大円盤数
MAX_DISKS = 100

# 円盤数
N = None

# 初期円盤数 N が奇数（True）か偶数（False）か？
# True  ならば、最小円盤（1）を左の peg へ移動させ、False なら右へ移動させる。
ODD = None

# ３つの塔、peg[0], peg[1], peg[2]
# peg[0] のすべての円盤を peg[2] へ移動させる。
peg = [None, None, None]

# peg[0], peg[1], peg[2] それぞれにある円盤の数
top = [None, None, None]

# 最小の円盤（1）が存在する peg の番号
one_peg = None

# 最小円盤（1）を移動させる Turn なら True、そうでないなら False
move_one = None


def initialize(n):
    """状態を初期化する
    初期円盤数を `n` で指定する。
    `n` が 0 以下、または `MAX_DISKS` より大きいとエラーになる。
    """
    global one_peg, move_one, N, ODD, MAX_DISKS, peg, top
    if (n <= 0) or (n > MAX_DISKS):
        raise ValueError('num of disks is illegal')
    N = n
    ODD = (n % 2 != 0)

    peg[0] = [i for i in range(n + 1, 0, -1)]
    peg[0][0] = MAX_DISKS + 1
    top[0] = n

    peg[1] = [0 for _ in range(n + 1)]
    peg[1][0] = MAX_DISKS + 1
    top[1] = 0

    peg[2] = [0 for _ in range(n + 1)]
    peg[2][0] = MAX_DISKS + 1
    top[2] = 0

    one_peg = 0
    move_one = True

def move():
    """円盤移動の操作を１回実行し、状態を変更する。"""
    global one_peg, move_one, N, ODD, MAX_DISKS, peg, top
    from_peg = to_peg = None
    if move_one:
        from_peg = one_peg
        to_peg = (from_peg - 1) if ODD else (from_peg + 1)
        if to_peg < 0:
            to_peg = 2
        elif to_peg > 2:
            to_peg = 0
        one_peg = to_peg
        move_one = False
    else:
        p1 = (one_peg + 1) % 3
        p2 = (one_peg + 2) % 3
        if peg[p1][top[p1]] < peg[p2][top[p2]]:
            from_peg = p1
            to_peg = p2
        else:
            from_peg = p2
            to_peg = p1
        move_one = True

    peg[to_peg][top[to_peg] + 1] = peg[from_peg][top[from_peg]]
    top[to_peg] += 1
    top[from_peg] -= 1

def was_finished():
    """円盤の移動が完了したか判定する。"""
    return top[2] == N

def print_pegs():
    """３つの塔の状況をプリントする。"""
    print('peg0:', peg[0][1:top[0]+1])
    print('peg1:', peg[1][1:top[1]+1])
    print('peg2:', peg[2][1:top[2]+1])

def main(n):
    initialize(n)
    print_pegs()
    counter = 0
    while not was_finished():
        print('Put enter key', end='')
        input()
        move()
        print_pegs()
        counter += 1
    
    print('Compeleted! {} times was needed.'.format(counter))


if __name__ == '__main__':
    print('Enter number of disks > ', end='')
    main(int(input()))