Towers of Hanoi solution using a recursive function -- with animation

For a general description of the game, see http://en.wikipedia.org/wiki/Tower_of_Hanoi.

Requires JSAnimation and JSAnimation_frametools.

See http://faculty.washington.edu/rjl/classes/am583s2014/notes/animation.html.



In [ ]:

    
from pylab import *



In [ ]:

    
from JSAnimation import IPython_display
import JSAnimation_frametools as J



In [ ]:

    
def plot_disk(j,n,peg,position):
    """
    plot disk number j out of n (j=1 is the smallest, j=n the largest)
    also specify which peg (1,2, or 3) to plot it on, and its position.
    position=1 means it is on the base, position=2 is on top of one other disk, etc.
    """
    width = j/float(n)  # actually the half-width of the jth disk
    height = 1./float(n)  # so n of them fit between 0 and 1 in y-direction
    xpeg = 1 + 2.5*(peg-1)  # location of this peg (they are at x = 1, 3.5, 7)
    x = [xpeg-width, xpeg+width, xpeg+width, xpeg-width, xpeg-width]
    y0 = (position-1)*height
    y = [y0, y0, y0+height, y0+height, y0]
    fill(x,y,'r')  # fill in a rectangle with red, specified by the 5 (x,y) points
    
def plot_pegs(n):
    plot([0,7],[0,0],'k',linewidth=3)
    plot([1,1],[0,1.2],'k',linewidth=3)
    plot([3.5,3.5],[0,1.2],'k',linewidth=3)
    plot([6,6],[0,1.2],'k',linewidth=3)
    axis([0,7,0,1.5])

Create an empty directory to store png files for each frame, and define the function to plot the configuration at each step:



In [ ]:

    
plotdir = '_plots'  # to store png files for each figure
J.make_plotdir(plotdir, clobber=True)  # ok to clobber if it already exists

def plot_all_disks(n,peg,frameno):
    close('all')  # close all figures
    plot_pegs(n)
    for i in [1,2,3]:
        disks = peg[i]
        for j,disk in enumerate(disks):
            plot_disk(disk,n,i,len(disks)-j)
    J.save_frame(frameno,plotdir,verbose=False)
    next_frameno = frameno+1
    return next_frameno



In [ ]:

    
n = 4
peg = {}
peg[1] = range(1,n+1)
peg[2] = []
peg[3] = []

frameno = plot_all_disks(n,peg,frameno=0)
        
def move_disks2(itop, ibottom, from_peg, to_peg, frameno):
    if itop > ibottom:
        raise InputError("Require itop <= ibottom, got itop = %i, ibottom = %i" %(itop,ibottom))
    if itop==ibottom:
        print "Move Disk %i from Peg %i to Peg %i" % (itop, from_peg, to_peg)
        peg[from_peg] = peg[from_peg][1:]   # drop first element of list
        peg[to_peg] = [itop] + peg[to_peg]  # add as first element of list
        figure()
        frameno = plot_all_disks(n,peg,frameno)

    else:
        other_peg = 6 - from_peg - to_peg
        # recursive call:
        frameno = move_disks2(itop, ibottom-1, from_peg, other_peg, frameno)
        frameno = move_disks2(ibottom, ibottom, from_peg, to_peg, frameno)
        frameno = move_disks2(itop, ibottom-1, other_peg, to_peg, frameno)
    return frameno
        
frameno = move_disks2(1,n,1,3, frameno=1)



In [ ]:

    
anim = J.make_anim(plotdir, figsize=(8,4))
anim

You can also make a stand-alone html file:



In [ ]:

    
J.make_html(anim, file_name="Towers.html", title="Towers of Hanoi")



In [ ]:

    
from IPython.display import FileLink
FileLink('Towers.html')

<_plots/frame0000.png>