DataStructs_Algos/Problems/tower_hanoi.py at main · ixig/DataStructs_Algos · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
'''
Tower of Hanoi
Move a set of discs from a starting peg to an ending peg, given one temporary
peg. A Larger disc cannot be placed on top of smaller disc. The starting peg
has the discs in the valid order (lagest at bottom, smallest on top).
'''

def hanoi1(stacks, src, dst, tmp):  # Recursive

    def print_stacks():  # [DEBUG]
        for i, stack in enumerate(stacks):
            print(f'{i}:{stack}', end=' ')
        print()

    def move_disks(num_discs, src, dst, tmp):
        if num_discs == 1:
            stacks[dst].append(stacks[src].pop())
            # assert sorted(stacks[dst], reverse=True) == stacks[dst]
            print(f'{src} => {dst}', end=' | '); print_stacks()
            return

        move_disks(num_discs - 1, src, tmp, dst)
        move_disks(1, src, dst, None)
        move_disks(num_discs - 1, tmp, dst, src)

    move_disks(len(stacks[src]), src, dst, tmp)

def hanoi2(stacks, src, dst, tmp):  # Iterative

    def print_stacks():  # [DEBUG]
        for i, stack in enumerate(stacks):
            print(f'{i}:{stack}', end=' ')
        print()

    def move_disks(num_discs, src, dst, tmp):
        params = [(num_discs, src, dst, tmp)]
        while params:
            num_discs, src, dst, tmp = params.pop()

            if num_discs == 1:
                stacks[dst].append(stacks[src].pop())
                # assert sorted(stacks[dst], reverse=True) == stacks[dst]
                print(f'{src} => {dst}', end=' | '); print_stacks()
                continue

            params.append((num_discs - 1, tmp, dst, src))
            params.append((1, src, dst, None))
            params.append((num_discs - 1, src, tmp, dst))

    move_disks(len(stacks[src]), src, dst, tmp)

# stacks0 = [[3,2,1], [], []]; hanoi1(stacks0, 0, 1, 2); print(stacks0)
stacks0 = [[3,2,1], [], []]; hanoi2(stacks0, 0, 1, 2); print(stacks0)
# stacks0 = [[4,3,2,1], [], []]; hanoi1(stacks0, 0, 2, 1); print(stacks0)
# stacks0 = [[4,3,2,1], [], []]; hanoi2(stacks0, 0, 2, 1); print(stacks0)