Hanoi tower
Contents
Hanoi tower¶
The Hanoi Tower is a iterative puzzle which can be solved with recursion.
Fig. 4 Hanoi Tower Source: Wikipedia¶
The stack of disks need to be moved from right to left. There only smaller disks can be stacked on top of any given disk.
Solution¶
The lowest disk needs to me move first to the rightmost disk. Therefore all other disks needs to be moved to the middle disk. So multiple time the same problem means recursion.
To move \(N\) disks from left to right:
Recursively move \(N-1\) disks from left to middle
Move largest disk form left to right
Recursively move \(N-1\) disks from middle to right
Fig. 5 HAnoi Tower Solution Source: Wikipedia¶
Imports¶
import numpy
import math
import time
from IPython.display import clear_output
Algorithm¶
def hanoi(towers: list, tower_height: int, left: int=0, right: int=2, middle: int=1, display: bool=True):
"""Solve the Tower of Hanoi
Args:
towers (list): list of the tower itself
tower_height (int): height of the tower
left (int, optional): definition of left tower 0-n. Defaults to 0.
right (int, optional): definition of left tower 0-n. Defaults to 2.
middle (int, optional): definition of left tower 0-n. Defaults to 1.
display (bool, optional): print stack of towers in ASCII. Default to True.
"""
if tower_height > 0:
# move smaller from left to middle
hanoi(towers, tower_height - 1, left, middle, right, display)
# move biggest to indented position
if not display:
print("Move toppiece from {} to {}".format(left, right))
move_piece(towers, left, right)
if display:
display_towers(towers, tower_height)
clear_output(wait=True)
# move remaining from middle to right
hanoi(towers, tower_height - 1, middle, right, left, display)
def move_piece(towers: list, src_tower: int=0, dst_tower: int=1):
"""Move on piece from one tower to another tower
Args:
towers (list): list of the tower itself
src_tower (int, optional): tower to be moved from. Defaults to 0.
dst_tower (int, optional): tower to place on. Defaults to 1.
"""
_piece_to_move=0
# search for toppiece to move (top to bottom)
for y in range(len(towers[src_tower])):
if towers[src_tower][y] != 0:
_piece_to_move = towers[src_tower][y]
towers[src_tower][y] = 0
break
# search for empty toppiece to place (bottom to top)
for y in reversed(range(len(towers[dst_tower]))):
if towers[dst_tower][y] == 0:
towers[dst_tower][y] = _piece_to_move
break
def display_towers(towers: list, speed: int=0.5):
"""Display the tower as ASCII Characters
Args:
towers (list): list of the tower itself
speed (int): time to wait after display
"""
_screen = ""
for y in range(len(towers[0])):
for x in range(len(towers)):
_l = math.floor((len(towers[0])-towers[x][y])/2)
_m = towers[x][y]
_r = math.ceil((len(towers[0])-towers[x][y])/2)
if _m == 0:
_screen += " " + (_l-1)*" " + 1*"|" + _r*" " + " "
else:
_screen += " " + _l*" " + _m*"x" + _r*" " + " "
_screen += "\n"
print(_screen)
time.sleep(speed)
Test¶
tower_height = 4
nbr_of_towers = 3
# create empty list and populate it
towers = [[0 for columns in range(tower_height)] for rows in range(nbr_of_towers)]
for x in range(len(towers)):
for y in range(len(towers[0])):
if x == 0:
towers[x][y] = y+1
display_towers(towers, tower_height)
hanoi(towers, tower_height, display=False)
x | |
xx | |
xxx | |
xxxx | |
Move toppiece from 0 to 1
Move toppiece from 0 to 2
Move toppiece from 1 to 2
Move toppiece from 0 to 1
Move toppiece from 2 to 0
Move toppiece from 2 to 1
Move toppiece from 0 to 1
Move toppiece from 0 to 2
Move toppiece from 1 to 2
Move toppiece from 1 to 0
Move toppiece from 2 to 0
Move toppiece from 1 to 2
Move toppiece from 0 to 1
Move toppiece from 0 to 2
Move toppiece from 1 to 2
tower_height = 4
nbr_of_towers = 3
# create empty list and populate it
towers = [[0 for columns in range(tower_height)] for rows in range(nbr_of_towers)]
for x in range(len(towers)):
for y in range(len(towers[0])):
if x == 0:
towers[x][y] = y+1
display_towers(towers, tower_height)
clear_output(wait=True)
hanoi(towers, tower_height, display=True)
| | x
| | xx
| | xxx
| | xxxx