Towers of hanoi

gistfile1.py

#/usr/bin/env/python

""" towers of hanoi

There is a legend about an Indian temple which contains a large room
with three time-worn posts in it surrounded by 64 golden
disks. Brahmin priests, acting out the command of an ancient prophecy,
have been moving these disks, in accordance with the rules of the
puzzle, since that time. The puzzle is therefore also known as the
Tower of Brahma puzzle. According to the legend, when the last move of
the puzzle is completed, the world will end. (from wikipedia)
"""

import time

levels = 20
towers = [range(0, levels), [], []]

### recursive solution, breaks down at about 25 discs
def recursive_solve(towers, start_range, start, other, target):
    global moves
    moves += 1

    # move stack to other peg
    if start_range > 2:
	towers = recursive_solve(towers, start_range - 1, start, target, other)

    # move bottom disc in stack to target peg
    towers[target].append(towers[start].pop(-1))

    # move stack from other to target peg
    if start_range > 2:
	towers = recursive_solve(towers, start_range - 1, other, start, target)

    return towers

global moves
moves = 0
benchmark = time.clock()
towers = recursive_solve(towers, levels + 1, 0, 1, 2)
benchmark = time.clock() - benchmark
print("Recursive solution benchmark: %s seconds, made %s moves" % (benchmark, moves))
print("final result: %s" % towers)