SHARE
TWEET

cryptarithms.py

agnishom Mar 9th, 2015 361 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. F,S,R = "JUNE","JULY", "APRIL"
  2.  
  3. internal_population_size = 500
  4. nThreads = 30
  5. nBests = 100
  6.  
  7. import threading, random, sys, time
  8.  
  9. letters = list(set(F+S+R))
  10. rand_digit = lambda : random.choice(range(10))
  11. rand_digit_2 = lambda : random.choice(range(1,10))
  12.  
  13. isFirstLetter = lambda x: (F[0] == x) or (S[0] == x) or (R[0] == x)
  14.  
  15. def fitness(chromosome):
  16.         f = int(reduce(lambda a,b: a+b, [str(chromosome.index(i)) for i in F]))
  17.         s = int(reduce(lambda a,b: a+b, [str(chromosome.index(i)) for i in S]))
  18.         r = int(reduce(lambda a,b: a+b, [str(chromosome.index(i)) for i in R]))
  19.         return abs(f + s - r)
  20.  
  21. def takeBest(n=nBests):
  22.         global all_populations
  23.         global coordinator_signal
  24.         global generator_signals
  25.         bests = []
  26.         while len(bests) < n:
  27.                 heads = [i[0][1] for i in all_populations]
  28.                 i = heads.index(min(heads))
  29.                 bests.append(all_populations[i].pop(0))
  30.         others = [j for i in all_populations for j in i]
  31.         random.shuffle(others)
  32.         others = others[:(internal_population_size - n)]
  33.         new_temp = []
  34.         for other in others:
  35.                 f = other[1]
  36.                 if new_temp == []:
  37.                         new_temp.append(other)
  38.                         continue
  39.                 i = 0
  40.                 while (i < len(new_temp)):
  41.                         if new_temp[i][1] >= f:
  42.                                 new_temp.insert(i,other)
  43.                                 break
  44.                         else:
  45.                                 i += 1
  46.                 else:
  47.                         new_temp.insert(i,other)
  48.         return bests+new_temp
  49.  
  50. def rand_population():
  51.         new_temp = []
  52.         while len(new_temp) < internal_population_size:
  53.                 chromosome = ['_']*10
  54.                 i = 0
  55.                 while i < len(letters):
  56.                         digit = rand_digit()
  57.                         if chromosome[digit] != '_':
  58.                                 continue
  59.                         if digit == 0 and isFirstLetter(letters[i]):
  60.                                 if (i == 9) and len(letters) == 10:
  61.                                         while True:
  62.                                                 j = rand_digit_2()
  63.                                                 chromosome[0],chromosome[j] = chromosome[j], chromosome[0]
  64.                                                 if chromosome[j] == '_':
  65.                                                         chromosome[j] = letters[i]
  66.                                                 if not isFirstLetter(chromosome[0]):
  67.                                                         i += 1
  68.                                                         break
  69.                                 else:
  70.                                         continue
  71.                         else:
  72.                                 chromosome[digit] = letters[i]
  73.                                 i += 1
  74.                 f = fitness(chromosome)
  75.                 i = 0
  76.                 while (i < len(new_temp)):
  77.                         if new_temp[i][1] >= f:
  78.                                 new_temp.insert(i,(chromosome,f))
  79.                                 break
  80.                         else:
  81.                                 i += 1
  82.                 else:
  83.                         new_temp.insert(i,(chromosome,f))
  84.         return new_temp[:]
  85.  
  86. def mutate(population):
  87.         new_temp = []
  88.         for chromosome_old in population:
  89.                 chromosome = chromosome_old[0][:]
  90.                 while True:
  91.                         i, j = rand_digit(), rand_digit()
  92.                         if i == j:
  93.                                 continue
  94.                         if (chromosome[i] == '_') and (chromosome[j] == '_'):
  95.                                 continue
  96.                         if (isFirstLetter(chromosome[j]) and (i == 0)):
  97.                                 continue
  98.                         chromosome[i],chromosome[j] = chromosome[j],chromosome[i]
  99.                         break
  100.                 f = fitness(chromosome)
  101.                 i = 0
  102.                 while (i < len(new_temp)):
  103.                         if new_temp[i][1] >= f:
  104.                                 new_temp.insert(i,(chromosome,f))
  105.                                 break
  106.                         else:
  107.                                 i += 1
  108.                 else:
  109.                         new_temp.insert(i,(chromosome,f))
  110.         return new_temp
  111.  
  112. def generator(population,n):
  113.         global all_populations
  114.         global coordinator_signal
  115.         global generator_signals
  116.         if not len(population):
  117.                 population = rand_population()
  118.         else:
  119.                 population = mutate(population)
  120.         for i in xrange(n):
  121.                 generator_signals[i].wait()
  122.         all_populations.append(population)
  123.         #time.sleep(2)
  124.         print all_populations
  125.         generator_signals[n].set()
  126.         coordinator_signal.wait()
  127.         generator_signals[n].clear()
  128.  
  129. def coordinator():
  130.         global all_populations
  131.         global coordinator_signal
  132.         global generator_signals
  133.         new_population = []
  134.         iteration_count = 0
  135.         while True:
  136.                 generator_threads = []
  137.                 iteration_count += 1
  138.                 for i in xrange(nThreads):
  139.                         generator_threads.append(threading.Thread(target=generator,args=(new_population,i)))
  140.                         print "Generator Call", iteration_count
  141.                 for i in generator_threads:
  142.                         i.start()
  143.                 for i in generator_signals:
  144.                         i.wait()
  145.                 coordinator_signal.clear()
  146.                 new_population = takeBest()
  147.                 if new_population[0][1] == 0:
  148.                         print new_population[0][0]
  149.                         break
  150.                 print "Best Fitness =", new_population[0][1]
  151.                 all_populations = []
  152.                 coordinator_signal.set()
  153.  
  154. coordinator_signal = threading.Event()
  155. generator_signals = []
  156. all_populations = []
  157. for i in xrange(nThreads):
  158.         generator_signals.append(threading.Event())
  159. coordinator_thread = threading.Thread(target=coordinator)
  160. coordinator_thread.start()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top