Hanoi 非递归解法

一直很孤陋寡闻的以为hanoi只能用递归解答，今天看到一个非递归解法让我汗了一下。

原文和源程序在这里，不过程序的变量命名个人觉得很混乱，看懂之后我加了一些注释和print语句在下面。

http://sanss.me/blog/14

我加了些注释的如下：

#!/bin/env python

"""
main logic:
    r = c
    while (not finished):
        choose two pillars from three pillars except c
        get a pillar who should move one of his disk (pillar: from)
        get this disk's destination pillar (pillar: dest)
        move
        c = dest pillar   
"""

class pillar():
    def __init__(self, name, disks=0):
        self.name = name
        if disks:
            self.p = [ i for i in range(disks, 0, -1)]
        else:
            self.p = []
   
    def name(self):    #interesting feature of python object. pillar_instance.name
        return self.name

    def getDiskCounts(self):
        return len(self.p)

    def getTopDisk(self):
        diskCounts = self.getDiskCounts()
        if diskCounts:
            return self.p[diskCounts-1]
        return None

    def moveDisk(self):
        self.p.pop()

    def addDisk(self, newDisk):
        self.p.append(newDisk)

# two pillar, if one pillar's top disk is bigger 
# return (pillar.disks, pillar.name)
def whichToMove(box):    #two pillars
    #tuple
    print "reduce which pillar?"
    print box[0].name, box[0].p
    print box[1].name, box[1].p
    mins = box[0].getTopDisk(), box[0].name
    if mins[0]:
        if box[1].getTopDisk() and mins[0] > box[1].getTopDisk():
            mins = box[1].getTopDisk(), box[1].name
            box[1].moveDisk()
        else:
            box[0].moveDisk()
    else:
        mins = box[1].getTopDisk(), box[1].name
        box[1].moveDisk()
    print mins[1]
    print "reduce which pillar."
    return mins

def toNext(num, a):    # a is the pillar who needs a move
    if disks%2 == 0:
        sequence = {'a':'b','b':'c','c':'a'}
    else:
        sequence = {'a':'c', 'c':'b', 'b':'a'}
    for i in [A,B,C]:
        if i.name == sequence[a]:    # i is the target pillar
            if not i.getTopDisk():
                #return i
                ret = i
            elif num < i.getTopDisk():
                #return i
                ret = i
            #return name2obj(sequence[i.name])
            else:
                ret = name2obj(sequence[i.name])    #roll again!
            print ret.name, ret.p
            return ret

def name2obj(a):
    for i in [A,B,C]:
        if i.name ==a:
            return i

def show():
    for i in [A,B,C]:
        print i.name, '----',i.p

def main():
    S=[A,B]    # initial S
    while C.getDiskCounts() < disks:
        mins = whichToMove(S)    # whose disk should be removed now?
        tonext = toNext(mins[0], mins[1])    # remove to where? acoording to disks%2
        tonext.addDisk(mins[0])    # target pillar add a disk.
        S=[A,B,C]
        S.remove(tonext)
        print 'move %c --> %c, \tdisk %d' % (mins[1], tonext.name, mins[0])

if __name__ == '__main__':
    disks = int(raw_input('how many disks: '))
    A = pillar('a', disks)
    B = pillar('b')
    C = pillar('c')
    show()
    main()
    show()