-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy path128_Others_Tower_Of_Hannoi.py
executable file
·167 lines (136 loc) · 5.53 KB
/
128_Others_Tower_Of_Hannoi.py
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
"""
The Tower of Hanoi is a puzzle game with three rods and n disks, each a different size.
All the disks start off on the first rod in a stack. They are ordered by size, with the largest disk on the
bottom and the smallest one at the top.
The goal of this puzzle is to move all the disks from the first rod to the last rod while following these rules:
You can only move one disk at a time.
A move consists of taking the uppermost disk from one of the stacks and placing it on top of another stack.
You cannot place a larger disk on top of a smaller disk.
Write a function that prints out all the steps necessary to complete the Tower of Hanoi. You should assume that the
rods are numbered, with the first rod being 1, the second (auxiliary) rod being 2, and the last (goal) rod being 3.
For example, with n = 3, we can do this in 7 moves:
Move 1 to 3
Move 1 to 2
Move 3 to 2
Move 1 to 3
Move 2 to 1
Move 2 to 3
Move 1 to 3
"""
from copy import deepcopy
# Breadth-first search solution
# Very poor performance
class hanoi:
def __init__(self):
self.peg_1 = [] # stack 1
self.peg_2 = [] # stack 2
self.peg_3 = [] # stack 3
self.moves = []
self.num_of_disks = 0
def add_discs(self, n):
# add all the discs to peg_1
self.num_of_disks = n
for i in range(1, n + 1):
self.peg_1.append(i)
def execute_move(self):
new_game_states = []
# see if discs from peg_1 can be moved:
if self.peg_1:
# pick first disk:
disk = self.peg_1[0]
# see if it can be moved to other two pegs
if len(self.peg_2) ==0 or self.peg_2[0] > disk:
new_state = deepcopy(self)
disk = new_state.peg_1.pop(0) # pick up disk
new_state.peg_2.insert(0, disk)
new_state.moves.append('Move {} to 2'.format(disk))
new_game_states.append(new_state)
if len(self.peg_3) == 0 or self.peg_3[0] > disk:
new_state = deepcopy(self)
disk = new_state.peg_1.pop(0) # pick up disk
new_state.moves.append('Move {} to 3'.format(disk))
new_state.peg_3.insert(0, disk)
new_game_states.append(new_state)
# see if discs from peg_2 can be moved:
if self.peg_2:
# pick first disk:
disk = self.peg_2[0]
# see if it can be moved to other two pegs
if len(self.peg_1) == 0 or self.peg_1[0] > disk:
new_state = deepcopy(self)
disk = new_state.peg_2.pop(0) # pick up disk
new_state.peg_1.insert(0, disk)
new_state.moves.append('Move {} to 1'.format(disk))
new_game_states.append(new_state)
if len(self.peg_3) == 0 or self.peg_3[0] > disk:
new_state = deepcopy(self)
disk = new_state.peg_2.pop(0) # pick up disk
new_state.peg_3.insert(0, disk)
new_state.moves.append('Move {} to 3'.format(disk))
new_game_states.append(new_state)
# see if discs from peg_3 can be moved:
if self.peg_3:
# pick first disk:
disk = self.peg_3[0]
# see if it can be moved to other two pegs
if len(self.peg_1) == 0 or self.peg_1[0] > disk:
new_state = deepcopy(self)
disk = new_state.peg_3.pop(0) # pick up disk
new_state.peg_1.insert(0, disk)
new_state.moves.append('Move {} to 1'.format(disk))
new_game_states.append(new_state)
if len(self.peg_2) == 0 or self.peg_2[0] > disk:
new_state = deepcopy(self)
disk = new_state.peg_3.pop(0) # pick up disk
new_state.peg_2.insert(0, disk)
new_state.moves.append('Move {} to 2'.format(disk))
new_game_states.append(new_state)
return new_game_states
def solved(self):
if len(self.peg_3) == self.num_of_disks:
return True
def __repr__(self):
return "1:{} , 2: {}, 3:{}".format(self.peg_1, self.peg_2, self.peg_3)
def solve_hanoi(game):
queue = []
queue.append(game)
while queue:
# print(len(queue))
curr_game_state = queue.pop(0)
if curr_game_state.solved():
for move in curr_game_state.moves:
print(move)
return # all done
queue.extend(curr_game_state.execute_move())
# --------------------
# Better Implementation
# https://www.freecodecamp.org/news/analyzing-the-algorithm-to-solve-the-tower-of-hanoi-problem-686685f032e3/
# this class is just used as an enum
class Towers:
peg_1 = 1
peg_2 = 2
peg_3 = 3
def solve_hanoi_redux(disks,source, inter, dest):
if disks == 1:
print("Move {} to {}".format(disks, dest))
else:
solve_hanoi_redux(disks-1, source, dest, inter)
print("Move {} to {}".format(disks, dest))
solve_hanoi_redux(disks-1, inter, source, dest)
if __name__ == '__main__':
# puzzle = hanoi()
# puzzle.add_discs(n=3)
# solve_hanoi(puzzle)
#
# print("\n------\n")
# puzzle = hanoi()
# puzzle.add_discs(n=3)
# solve_hanoi(puzzle)
print("Disks=3")
solve_hanoi_redux(3, Towers.peg_1, Towers.peg_2, Towers.peg_3)
print('-------------')
print("Disks=4")
solve_hanoi_redux(4, Towers.peg_1, Towers.peg_2, Towers.peg_3)
print('-------------')
print("Disks=5")
solve_hanoi_redux(5, Towers.peg_1, Towers.peg_2, Towers.peg_3)