cryptarithms.py

F,S,R = "JUNE","JULY", "APRIL"

internal_population_size = 500
nThreads = 30
nBests = 100

import threading, random, sys, time

letters = list(set(F+S+R))
rand_digit = lambda : random.choice(range(10))
rand_digit_2 = lambda : random.choice(range(1,10))

isFirstLetter = lambda x: (F[0] == x) or (S[0] == x) or (R[0] == x)

def fitness(chromosome):
    f = int(reduce(lambda a,b: a+b, [str(chromosome.index(i)) for i in F]))
    s = int(reduce(lambda a,b: a+b, [str(chromosome.index(i)) for i in S]))
    r = int(reduce(lambda a,b: a+b, [str(chromosome.index(i)) for i in R]))
    return abs(f + s - r)

def takeBest(n=nBests):
    global all_populations
    global coordinator_signal
    global generator_signals
    bests = []
    while len(bests) < n:
        heads = [i[0][1] for i in all_populations]
        i = heads.index(min(heads))
        bests.append(all_populations[i].pop(0))
    others = [j for i in all_populations for j in i]
    random.shuffle(others)
    others = others[:(internal_population_size - n)]
    new_temp = []
    for other in others:
        f = other[1]
        if new_temp == []:
            new_temp.append(other)
            continue
        i = 0
        while (i < len(new_temp)):
            if new_temp[i][1] >= f:
                new_temp.insert(i,other)
                break
            else:
                i += 1
        else:
            new_temp.insert(i,other)
    return bests+new_temp

def rand_population():
    new_temp = []
    while len(new_temp) < internal_population_size:
        chromosome = ['_']*10
        i = 0
        while i < len(letters):
            digit = rand_digit()
            if chromosome[digit] != '_':
                continue
            if digit == 0 and isFirstLetter(letters[i]):
                if (i == 9) and len(letters) == 10:
                    while True:
                        j = rand_digit_2()
                        chromosome[0],chromosome[j] = chromosome[j], chromosome[0]
                        if chromosome[j] == '_':
                            chromosome[j] = letters[i]
                        if not isFirstLetter(chromosome[0]):
                            i += 1
                            break
                else:
                    continue
            else:
                chromosome[digit] = letters[i]
                i += 1
        f = fitness(chromosome)
        i = 0
        while (i < len(new_temp)):
            if new_temp[i][1] >= f:
                new_temp.insert(i,(chromosome,f))
                break
            else:
                i += 1
        else:
            new_temp.insert(i,(chromosome,f))
    return new_temp[:]

def mutate(population):
    new_temp = []
    for chromosome_old in population:
        chromosome = chromosome_old[0][:]
        while True:
            i, j = rand_digit(), rand_digit()
            if i == j:
                continue
            if (chromosome[i] == '_') and (chromosome[j] == '_'):
                continue
            if (isFirstLetter(chromosome[j]) and (i == 0)):
                continue
            chromosome[i],chromosome[j] = chromosome[j],chromosome[i]
            break
        f = fitness(chromosome)
        i = 0
        while (i < len(new_temp)):
            if new_temp[i][1] >= f:
                new_temp.insert(i,(chromosome,f))
                break
            else:
                i += 1
        else:
            new_temp.insert(i,(chromosome,f))
    return new_temp

def generator(population,n):
    global all_populations
    global coordinator_signal
    global generator_signals
    if not len(population):
        population = rand_population()
    else:
        population = mutate(population)
    for i in xrange(n):
        generator_signals[i].wait()
    all_populations.append(population)
    #time.sleep(2)
    print all_populations
    generator_signals[n].set()
    coordinator_signal.wait()
    generator_signals[n].clear()

def coordinator():
    global all_populations
    global coordinator_signal
    global generator_signals
    new_population = []
    iteration_count = 0
    while True:
        generator_threads = []
        iteration_count += 1
        for i in xrange(nThreads):
            generator_threads.append(threading.Thread(target=generator,args=(new_population,i)))
            print "Generator Call", iteration_count
        for i in generator_threads:
            i.start()
        for i in generator_signals:
            i.wait()
        coordinator_signal.clear()
        new_population = takeBest()
        if new_population[0][1] == 0:
            print new_population[0][0]
            break
        print "Best Fitness =", new_population[0][1]
        all_populations = []
        coordinator_signal.set()

coordinator_signal = threading.Event()
generator_signals = []
all_populations = []
for i in xrange(nThreads):
    generator_signals.append(threading.Event())
coordinator_thread = threading.Thread(target=coordinator)
coordinator_thread.start()