For my last post of the year, I want to cover a classic CS puzzle: the Tower of Hanoi. If you haven’t seen this puzzle before, I recommend reading up on it and then trying to solve it. In order to facilitate that, I’ve written a small program to display the physical movements of the disks. When used with a correct algorithm, it produces outout like this.

Save the following program as towerPrinter.py to try it out.

import curses
import itertools
import time

class TowerPrinter:
  # The number of blank lines above the towers:
  EXTRA_BLANK_LINES_TOP = 2
  # The number of rows between the towers and the extra debug list
  # (the towers printed as a regular Python list):
  DEBUG_LIST_PAD_TOP = 3

  def __init__(self, time_between_steps):
    self.time_between_steps = time_between_steps
    self.stdscr = curses.initscr()

  def update(self, towers):
    self.prettyPrint(towers)
    print("\n\n")
    time.sleep(self.time_between_steps)

  def prettyPrint(self, towers):
    num_disks = sum(len(x) for x in towers)
    self.stdscr.erase()
    rows = list(reversed([(" " if x is None else x for x in tower) \
        for tower in itertools.zip_longest(*towers)]))
    num_blank_lines = num_disks - len(rows) + self.EXTRA_BLANK_LINES_TOP
    for i, row in enumerate(rows):
      self.stdscr.addstr(i + num_blank_lines, 0, \
        "{}    {}    {}".format(*row))
    self.stdscr.addstr(num_disks + self.DEBUG_LIST_PAD_TOP, 0, str(towers))
    self.stdscr.refresh()

  def flashWinner(self):
    for i in range(5):
      self.stdscr.addstr(0, 0, "WINNER!")
      self.stdscr.refresh()
      time.sleep(0.75)
      self.stdscr.addstr(0, 0, "       ")
      self.stdscr.refresh()
      time.sleep(0.25)

  def finish(self):
    try:
      self.flashWinner()
    finally:
      curses.endwin()

This program on its own does nothing. In order to try it out, you’ll need to write the actual algorithm to move the disks. I’ve written the following starter code. You can save this code in the same directory as towerPrinter.py and run it. It should display the starting configuration for five seconds, then start flashing WINNER!.

# Tower representation
# --------------------
# - There are three towers and five disks total
# - Towers are represented as a list of three lists
# - Each tower's disks are listed from bottom to top
#
# For example, this:
#
# 1         4
# 2    3    5
#
# would be represented as [[2, 1], [3], [5, 4]]

# Using the tower printer
# -----------------------
# - Call tp.update(towers) to update the towers displayed
# - Call tp.finish() when your algorithm is finished

from towerPrinter import TowerPrinter

tp = TowerPrinter(time_between_steps = 5.0) # TODO: speed this up?
towers = [list(range(5, 0, -1)), [], []]
tp.update(towers)

# TODO: your code here. Feel free to add extra methods, etc.

tp.finish()

Finally, the following is my solution to the problem. Don’t read this if you don’t want the problem spoiled for you.

from towerPrinter import TowerPrinter

def moveDisks(towers, numDisks, src, dst, tmp):
  if numDisks == 0:
    return towers
  towers = moveDisks(towers, numDisks - 1, src, tmp, dst)
  diskToMove = towers[src].pop()
  towers[dst].append(diskToMove)
  tp.update(towers)
  towers = moveDisks(towers, numDisks - 1, tmp, dst, src)
  return towers

tp = TowerPrinter(time_between_steps = 0.5)
towers = [list(range(5, 0, -1)), [], []]
tp.update(towers)
moveDisks(towers, 5, 0, 2, 1)
tp.finish()