examples/ugly.py

   1 from time import time
   2
   3 def value(x, y, z):
   4         return 2**x * 3**y * 5**z
   5
   6 def ugly(maxValue):
   7         uglies = []
   8         counter = 1
   9         d = {1 : (0, 0, 0)}
  10
  11         while len(uglies) < maxValue:
  12                 uglies.append(counter)
  13                 x, y, z = d[counter]
  14
  15                 d[value(x+1, y, z)] = (x+1, y, z)
  16                 d[value(x, y+1, z)] = (x, y+1, z)
  17                 d[value(x, y, z+1)] = (x, y, z+1)
  18
  19                 del d[counter]
  20
  21                 keys = d.keys()
  22                 keys.sort()
  23                 counter = keys[0]
  24
  25         return uglies[-1]
  26
  27 iterations = 1500
  28
  29 start = time()
  30 for i in range(10):
  31         uvalue = ugly(iterations)
  32 end = time()
  33 print iterations, "ugly value =", uvalue, "in", (end - start)*1000, "ms"
  34