Algorithm learned with Python 13th: Tower of Hanoi

#Algorithm learned in Python

Introduction

Implement the basic algorithm in Python to deepen your understanding of the algorithm. The 13th edition deals with the Tower of Hanoi.

Tower of Hanoi

The Tower of Hanoi is well known. The rules are shown below. ・ Completed by moving from end to end in the same shape ・ You cannot move on something smaller than yourself

Implementation

Here, the program showing the movement procedure at that time by moving between the three axes and inputting only the number of blocks to be handled is shown below. I tried to visualize it, but since it is a little different from the essence of knowing the algorithm, I will show only the part I tried.

code

hanoi.py

"""
2020/12/31
@Yuya Shimizu

Tower of Hanoi
"""

#Arguments: number of blocks, move source, move destination, via
def hanoi(n, source, destination, via):
    if n > 1:
        hanoi(n-1, source, via, destination)  #Recursion
        print(source + '->' + destination)
        hanoi(n-1, via, destination, source)  #Recursion
    else:
        print(source + '->' + destination)

n = int(input('Number of steps in Hanoi>> '))
hanoi(n, 'a', 'c', 'b')

output

Number of steps in Hanoi>> 3     #Enter 3
a->c
a->b
c->b
a->c
b->a
b->c
a->c

code

hanoi_v.py

"""
2020/12/31
@Yuya Shimizu

Tower of Hanoi (visualization)
"""

def tower(n):
    result = ""
    for i in range(1,n+1):
        #Even rows
        if i %2 == 0:
            result += f"|  {' '*(n-i+1)}{'- '*(i//2)}{'- '*(i//2)}\t|  "
            result += f"{' '*(n-i+1)}{'- '*(i//2)}{'- '*(i//2)}\t|"
            result += f"  {' '*(n-i+1)}{'- '*(i//2)}{'- '*(i//2)}\t|  "

        #Odd lines
        else:
            result += f"|  {' '*(n-i+1)}{'- '*(i//2)}- {'- '*(i//2)}\t|  "
            result += f"{' '*(n-i+1)}{'- '*(i//2)}- {'- '*(i//2)}\t|"
            result += f"  {' '*(n-i+1)}{'- '*(i//2)}- {'- '*(i//2)}\t|  "

        result += "\n"
    return result

#Arguments: number of blocks, move source, move destination, via
def hanoi(n, source, destination, via):
    if n > 1:
        hanoi(n-1, source, via, destination)  #Recursion
        print(source + '->' + destination)
        hanoi(n-1, via, destination, source)  #Recursion
    else:
        print(source + '->' + destination)

#n = int(input('Number of steps in Hanoi>> '))
#hanoi(n, 'a', 'c', 'b')
print(tower(4))

output

|     -    |     -    |     - 	 |  
|    - -   |    - -   |    - - 	 |  
|   - - -  |   - - -  |   - - -  |  
|  - - - - |  - - - - |  - - - - |  

For the time being, I made only the figures that were all arranged. I will try it again when I feel like it. The visualization program is introduced by @shiracamus in the comment section.

Impressions

I learned the algorithm to solve the Tower of Hanoi, and learned that the processing time required at this time increases exponentially. He thought he could even visualize it, but realized that it would take some time, and I think it's a bit off in terms of learning algorithms, and I'll try to visualize it when I feel like it. According to other people's articles, it seems that python also has a module that even visualizes, and it seems that the existing Hanoi Tower program can be handled by the following operations.

$ pip install k-peg-hanoi
$ hanoi 4 4

Visualization in my own program is introduced by @shiracamus in the comment section.

References

Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha