# 
# cubewalk
#   Random walk on the cube
#   Computes return time to start vertex
#
from random import randint

# How many trials (times to walk)
trials = 10000

# results is a dictionary that holds pairs (return time, frequency)
results = dict()

max = 0   # track the maximum walk length seen
for trial in range(trials):
  # start walk at [0,0,0]
  v = [0,0,0]
  n=0
  # walk until get back to [0,0,0]
  while n == 0 or v != [0,0,0]:
    i = randint(0,2)
    v[i] = 1-v[i]
    n += 1

  # update the results dictionary.. may need to add a new key
  if n in results:
    results[n] += 1
  else:
    results[n] = 1
    if n > max:
      max = n

# print histogram
histwidth = 80
divisor = trials/histwidth
for i in range(2,max+1,2):
   print "%2d" % i,
   if i not in results:
     print
   else:
     if results[i]/divisor == 0:
       print '.'
     else:
       print 'o'*(results[i]/divisor)

# print stats
totalsteps = 0
for i in range(2,max+1,2):
   if i in results:
     totalsteps += results[i]*i
print 'Average walk length:', totalsteps/float(trials)