[PYTHON] Challenge the Tower of Hanoi with recursion + stack
Good evening everyone (* ^-^ *)
The other day, I studied recursion in the article "Challenge the Tower of Hanoi with Recursion". https://qiita.com/AKpirion/items/c0f7905c6227e086644e
- Isn't it possible to make hyperlinks? ??
So, I immediately plagiarized the following description that @shiracamus told me. Consider whether it can be achieved by adding a stack.
hanoi_reference.py
def move(n, a, b, c):
"""Move n disks from a to b as a temporary shelter to c"""
if n > 1:
move(n - 1, a, c, b) #Evacuate to b with c as a temporary shelter except for the bottom of a
print(f" {n}No. disk{a}From{c}Move to") #Move the bottom from a to c
if n > 1:
move(n - 1, b, a, c) #Move to c with a as a temporary shelter, except for the bottom that was saved in b.
def hanoi(n):
print(f"{n}Steps to move a disk from A to C")
move(n, 'A', 'B', 'C')
if __name__ == '__main__':
hanoi(2)
hanoi(3)
This time, we will move the two disks as in the previous article.
The recursion description always returns to print (f "move disk # {n} from {a} to {c}").
If so, the if statement is used to classify each value of {a} and {c}.
I thought that if you mix push and pop, you can realize the Tower of Hanoi with a stack.
First, I prepared dedicated stacks at positions A, B, and C, respectively.
hanoi_r1.py
class top:
def __init__(self,capacity:int = 2):
self.Astr = [2,1]
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
I don't think any supplement is necessary. Next is push, but basically it never becomes full, so The description can be simple.
hanoi_r1.py
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
Since pop does not have to worry about empty The description is simple.
hanoi_r1.py
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
No problem, right? The rest is move.
hanoi_r1.py
def move(self,n,a,b,c):
if n>1:
top.move(self,n-1,a,c,b)
print(f"{n}To{a}From{c}What")
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if n>1:
top.move(self,n-1,b,a,c)
As I wrote at the beginning, be sure to print (f "move disk # {n} from {a} to {c}") Since it will come down, I use if after this to classify the conditions. With three disks, it seems that there will be more cases (laughs) I wonder if there is any good way. .. (´Д ｀) y━─┛ ~~
To supplement the inside of the if statement a little more, Since push / pop only controls the behavior of the pointer ptr, Be sure to overwrite the value of the A / B / C stack body with None or it will not work. So I push None, It increments the ptr by 1, then use pop to restore it.
hanoi_r1.py
class top:
def __init__(self,capacity:int = 2):
self.Astr = [2,1]
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
def view(self):
print(f"A = {self.Astr}")
print(f"B = {self.Bstr}")
print(f"C = {self.Cstr}")
def move(self,n,a,b,c):
if n>1:
top.move(self,n-1,a,c,b)
print(f"{n}To{a}From{c}What")
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if n>1:
top.move(self,n-1,b,a,c)
test = top()
if __name__ =="__main__":
print("default setting")
print("A = [2,1]")
print("B = [None,None]")
print("C = [None,None]")
test.move(2,"A","B","C")
The execution result is here.
default setting
A = [2,1]
B = [None,None]
C = [None,None]
1 from A to B
A = [2, None]
B = [1, None]
C = [None, None]
2 from A to C
A = [None, None]
B = [1, None]
C = [2, None]
1 from B to C
A = [None, None]
B = [None, None]
C = [2, 1]
N = 2 Not fixed, but a configuration that can follow even if it is freely changed I will consider it again. Probably, even if the number of sheets increases, the place to move does not increase, so I feel like I can do something about it. Let's do it someday. .. (￣з￣)
--10/03 18:53
The children's athletic meet was over and he went to bed early. I have time. I'm going to update it.
The content of the update is to consider a configuration that can convert the number of disks to N. As I touched on last time, even if the number of disks increases, the number of moving points does not increase. Therefore, it is OK if you list all the movement patterns with an if statement.
A => B A => C B => C B => A C => A C => B
If you can divide the case, it's not smart The problem can be cleared.
hanoi_stack_r1.py
if a == "A" and c == "B":
top.Bpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "A" and c == "C":
top.Cpush(self,top.Apop(self))
top.Apush(self,None)
top.Apop(self)
top.view(self)
if a == "B" and c == "C":
top.Cpush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if a == "B" and c == "A":
top.Apush(self,top.Bpop(self))
top.Bpush(self,None)
top.Bpop(self)
top.view(self)
if a == "C" and c == "B":
top.Bpush(self,top.Cpop(self))
top.Cpush(self,None)
top.Cpop(self)
top.view(self)
if a == "C" and c == "A":
top.Apush(self,top.Cpop(self))
top.Cpush(self,None)
top.Cpop(self)
top.view(self)
It's OK. Next, make the number of disks to be prepared N, variable.
hanoi_stack_r1.py
class top:
def __init__(self,capacity):
self.Astr = [] * capacity #None is also data, so leave it empty here
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
self.Aptr = 0
self.Bptr = 0
self.Cptr = 0
for i in range(capacity): #If you put in 4, 0=> 1 => 2 =>3 and change
self.Astr.append(capacity-i) #Number of disks capacity-If i, 4=> 3 => 2 =>1 can be assigned to Astr
top.view(self)
if __name__ =="__main__":
num = int(input("enter: ")) #Define how many disks to use
test = top(num) # def__init__Substitute capacity, the initial value of, into num
test.move(num,"A","B","C") #num is effectively equal to the stack depth
Isn't it okay to have None in the first place? !! (Lol) I tried it with 5 sheets.
enter: 5
A = [5, 4, 3, 2, 1]
B = [None, None, None, None, None]
C = [None, None, None, None, None]
1 from A to C
A = [5, 4, 3, 2, None]
B = [None, None, None, None, None]
C = [1, None, None, None, None]
2 from A to B
A = [5, 4, 3, None, None]
B = [2, None, None, None, None]
C = [1, None, None, None, None]
1 from C to B
A = [5, 4, 3, None, None]
B = [2, 1, None, None, None]
C = [None, None, None, None, None]
3 from A to C
A = [5, 4, None, None, None]
B = [2, 1, None, None, None]
C = [3, None, None, None, None]
1 from B to A
A = [5, 4, 1, None, None]
B = [2, None, None, None, None]
C = [3, None, None, None, None]
2 from B to C
A = [5, 4, 1, None, None]
B = [None, None, None, None, None]
C = [3, 2, None, None, None]
1 from A to C
A = [5, 4, None, None, None]
B = [None, None, None, None, None]
C = [3, 2, 1, None, None]
4 from A to B
A = [5, None, None, None, None]
B = [4, None, None, None, None]
C = [3, 2, 1, None, None]
1 from C to B
A = [5, None, None, None, None]
B = [4, 1, None, None, None]
C = [3, 2, None, None, None]
2 from C to A
A = [5, 2, None, None, None]
B = [4, 1, None, None, None]
C = [3, None, None, None, None]
1 from B to A
A = [5, 2, 1, None, None]
B = [4, None, None, None, None]
C = [3, None, None, None, None]
3 from C to B
A = [5, 2, 1, None, None]
B = [4, 3, None, None, None]
C = [None, None, None, None, None]
1 from A to C
A = [5, 2, None, None, None]
B = [4, 3, None, None, None]
C = [1, None, None, None, None]
2 from A to B
A = [5, None, None, None, None]
B = [4, 3, 2, None, None]
C = [1, None, None, None, None]
1 from C to B
A = [5, None, None, None, None]
B = [4, 3, 2, 1, None]
C = [None, None, None, None, None]
5 from A to C
A = [None, None, None, None, None]
B = [4, 3, 2, 1, None]
C = [5, None, None, None, None]
1 from B to A
A = [1, None, None, None, None]
B = [4, 3, 2, None, None]
C = [5, None, None, None, None]
2 from B to C
A = [1, None, None, None, None]
B = [4, 3, None, None, None]
C = [5, 2, None, None, None]
1 from A to C
A = [None, None, None, None, None]
B = [4, 3, None, None, None]
C = [5, 2, 1, None, None]
3 from B to A
A = [3, None, None, None, None]
B = [4, None, None, None, None]
C = [5, 2, 1, None, None]
1 from C to B
A = [3, None, None, None, None]
B = [4, 1, None, None, None]
C = [5, 2, None, None, None]
2 from C to A
A = [3, 2, None, None, None]
B = [4, 1, None, None, None]
C = [5, None, None, None, None]
1 from B to A
A = [3, 2, 1, None, None]
B = [4, None, None, None, None]
C = [5, None, None, None, None]
4 from B to C
A = [3, 2, 1, None, None]
B = [None, None, None, None, None]
C = [5, 4, None, None, None]
1 from A to C
A = [3, 2, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 1, None, None]
2 from A to B
A = [3, None, None, None, None]
B = [2, None, None, None, None]
C = [5, 4, 1, None, None]
1 from C to B
A = [3, None, None, None, None]
B = [2, 1, None, None, None]
C = [5, 4, None, None, None]
3 from A to C
A = [None, None, None, None, None]
B = [2, 1, None, None, None]
C = [5, 4, 3, None, None]
1 from B to A
A = [1, None, None, None, None]
B = [2, None, None, None, None]
C = [5, 4, 3, None, None]
2 from B to C
A = [1, None, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 3, 2, None]
1 from A to C
A = [None, None, None, None, None]
B = [None, None, None, None, None]
C = [5, 4, 3, 2, 1]
Please check if anyone has any problems (laughs) Now, next is the hint given by @shiracamus I will try to make a pyhton-like description that can be simplified. I read @ shiracamus's code, After reading it, I laughed. Python can do that (laughs). Ah ~ embarrassing (* noωno) I'm writing an article for studying, so At this time, I don't care (laughs) For the time being, I tried running this first.
test.py
tower = {"A": [*range(3, 0, -1)], "B": [], "C": []}
print(tower)
{'A': [3, 2, 1], 'B': [], 'C': []}
What is this ?! Magic ?? By the way, if you delete the * in front of range. ..
{'A': [range(3, 0, -1)], 'B': [], 'C': []}
I was surprised. I see, if you add a magical "*", It turns into an array (..) φ memo memo
As mentioned above, None is also a type of data, so Go empty without using None, it's the same thing.
Next is the introduction of append () and pop (). append () behaves like push. Moreover, pop is exactly what pop thinks. What's more, it's convenient when you retrieve the data for pop. It is about to erase the data.
.. .. .. wait a minute. Does that mean that the control managed by pointers is no longer necessary ?! Let's optimize it immediately, the description of def __ init __.
test.py
def __init__(self,capacity):
###############################
self.Astr = [] * capacity #=> tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}Replace with
self.Bstr = [None] * capacity
self.Cstr = [None] * capacity
self.capa = capacity
###############################
self.Aptr = 0 #=> append,Since stack operation is realized by pop, variables for pointer management are unnecessary.
self.Bptr = 0
self.Cptr = 0
##############################
for i in range(capacity): #=> "A": [*range(n, 0, -1)],Unnecessary because it is replaced with
self.Astr.append(capacity-i)
top.view(self)
##############################
# || #
# \/ #
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
I laughed w. Next, if append and pop are the movements of the stack, Isn't the following description that manages the pointer operation at the time of push and pop unnecessary?
test.py
#All unnecessary!!!!#####################
def Apush(self,value):
self.Astr[self.Aptr] = value
self.Aptr += 1
def Bpush(self,value):
self.Bstr[self.Bptr] = value
self.Bptr += 1
def Cpush(self,value):
self.Cstr[self.Cptr] = value
self.Cptr += 1
def Apop(self):
self.Aptr -= 1
return self.Astr[self.Aptr]
def Bpop(self):
self.Bptr -= 1
return self.Bstr[self.Bptr]
def Cpop(self):
self.Cptr -= 1
return self.Cstr[self.Cptr]
################################
The tower is defined as the initial value, Let's move it using append and pop. In conclusion, this is what happened.
test.py
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}To{a}From{c}What")
self.tower[c].append(self.tower[a].pop())
if n>1:
hanoi.move(self,n-1,b,a,c)
My understanding is that self is used when passing variables between defs in class. So, if you declare self.tower, you can type def move (self,) and self. An understanding that you can bring self.tower into def move.
As for hanoi.move, it is an image that calls def move in class hanoi. hanoi.move () I was surprised. You may need to study a little more self.
I will go next. The following functions are defined to represent the state of each box.
test.py
def view(self):
print(f"A = {self.Astr}")
print(f"B = {self.Bstr}")
print(f"C = {self.Cstr}")
Now that Astr / Bstr / Cstr is no longer needed, Must be represented in another way. I'm not a genius enough to understand with just the code I received, I looked it up. There was an easy-to-understand explanation below.
https://note.nkmk.me/python-dict-keys-values-items/
According to this, the name of the box and the contents of the box can be expressed by turning the for statement. It was a thing.
test.py
def view(self):
for name,value in self.tower.items()
print(f"{name} = {value}")
I see. Let's incorporate it immediately.
test.py
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def view(self):
for name,value in self.tower.items():
print(f"{name} = {value}")
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}To{a}From{c}What")
self.tower[c].append(self.tower[a].pop())
hanoi.view(self)
if n>1:
hanoi.move(self,n-1,b,a,c)
It's simple enough to die. The whole picture is like this.
hanoi_stack_r2.py
class hanoi:
def __init__(self,n):
self.tower = {"A": [*range(n, 0, -1)], "B": [], "C": []}
def view(self):
for name,value in self.tower.items():
print(f"{name} = {value}")
def move(self,n,a,b,c):
if n>1:
hanoi.move(self,n-1,a,c,b)
print(f"{n}To{a}From{c}What")
self.tower[c].append(self.tower[a].pop())
hanoi.view(self)
if n>1:
hanoi.move(self,n-1,b,a,c)
if __name__ =="__main__":
num = int(input("enter: "))
test = hanoi(num)
test.move(num,"A","B","C")
Thanks to @shiracamus for the opportunity to study m (_ _) m
Recommended Posts