hanoi-iter.py

"""
Iterative towers of Hanoi solution.

This is based on the idea that essentially, the towers problem is a binary
counter, with the disk that gets moved being equal to the bit that would be
set on any iteration of the counter.

The solution exploits a few other mathematical properties of the problem:

    To solve an N disk towers of Hanoi requires (2^n)-1 moves (easy to prove
    by induction)

    The disks move in circular (i.e. modular) patterns, with even disks moving
    clockwise and odd disks moving anti-clockwise (or the other way around,
    n depending on how you want to think of it).  Another way to think of this
    is that if we moved disk N-1 one space, we need to move disk N two spaces.
    This is implemented in the modulo 3 calculations below.
"""

POSTS = ['A', 'B', 'C']

def move(n):
    """Compute the nth move
    """
    disk = ((~(n-1)) & n).bit_length()
    times_moved = n // 2**disk
    from_stack = (((disk % 2) + 1) * times_moved) % 3
    to_stack = (((disk % 2) + 1) * (times_moved + 1)) % 3
    print "Move disk %s from %s to %s" % (disk, POSTS[from_stack],
                                          POSTS[to_stack])


def hanoi(n):
    for i in range(2**n - 1):
        move(i+1)

if __name__ == '__main__':
    hanoi(5)