import time
def elapsed(expression,number=1):
''' computes elapsed time for executing code
number of times (default is 1 time). expression should
be a string representing a Python expression. '''
t1=time.clock()
for i in range(number):
eval(expression)
t2=time.clock()
return t2-t1
def roi_iter_hanoi_move(start, via, target,n,k):
'''
iterative solution to the hanoi move problem
this solution uses a repeating pattern found along the problem's solutions.
the pattern holds 2 conditions:
1. disk 1 for even n goes by the pattern:
start->via, via->target, target->start
disk 1 for odd n goes by the pattern:
start->target, target->via, via->start
2. disk a for n disks acts like disk a-1 for n-1 disks
though this is still a quite recursive-thinking definition,
this is its iterative solution
by Roi Tagar
'''
moves = compose_moves(start, via, target)
if k == 2**n - 1:
return format_move(n, (start, target))
'''
here we need to find the LSB that holds '1' in the binary represenation of k
lower-level languages might have more efficient solutions for this problem
also, knowing the system architecture for large integer representations,
we can binary-search (or block-search) using the CPU's native integer size,
reducing this loop to log(n) or n/bits-of-integer
(eg: a 32 bit processor handles a 32 bit scan in one atomic action)
'''
times = 0
while k % 2 == 0:
times+=1
k//=2
# now k%2 == 1
disk = 1 + times
move = moves[((k-1)//2)%3 + 3*((n-times)%2)]
return format_move(disk, move)
def format_move(disk, move):
return str.format('disk {} from {} to {}', disk, move[0], move[1])
def compose_moves(start, via, target):
'''
Generates a 'moves' list, that matches the pattern
The result for "A", "B", "C"
moves=['AB', 'BC', 'CA', 'AC', 'CB', 'BA']
'''
return [(start,via), (via,target), (target,start),\
(start,target), (target,via), (via,start)]
# print(roi_iter_hanoi_move("A", "B", "C", 400, 5**90))
# print(roi_iter_hanoi_move("A", "B", "C", 8000, 5**900+75))
# print(roi_iter_hanoi_move("A", "B", "C", 23000, 5**1900+76))
def roi_iter():
return roi_iter_hanoi_move("A", "B", "C", 8500, 5**900+7**800)
import timeit
# print(timeit.timeit(roi_iter, number=10))