import random

target = 'methinks it is a weasle'
offsprings = 10
pop_size = 100
mutation_rate = 100

def turn_str(l):
    s=''
    for c in l:
        s+=c
    return s

def abiogenesis():
    return [[' ' for n in range(len(target))] for m in range(pop_size)]

# mutates an individual's string
# [string] -> [string]
def mutate_string(individual):
    l=list(individual)
    gene_position=0
    while gene_position < len(target):
        if random.randint(1,mutation_rate)==1:
            l[gene_position] = random.choice([chr(c+ord('a')) for c in range(26)] + [' '])
        gene_position+=1
    return turn_str(l)

def fitness(individual):
    fitness_amount = 0
    fitness_amount = sum([individual[n] == target[n] for n in range(len(target))])
    return fitness_amount

def best_fit(population):
    fittest_score = [fitness(population[0]) for n in range(offsprings)]
    fittest_individuals = [population[0] for n in range(offsprings)]
    i = 1
    while i < pop_size:
        individual_fitness = fitness(population[i])
        if sum([individual_fitness > n for n in fittest_score]):
            fittest_score.pop()
            fittest_score.insert(0,individual_fitness)
            fittest_individuals.pop()
            fittest_individuals.insert(0, population[i])
        i+=1
    return fittest_individuals

def procreate(fittest_individuals):
    new_population = []
    for m in fittest_individuals:
        for n in range(pop_size/offsprings):
            new_population.append(m)
    return new_population

def teh_main():
    generation=1
    stay_in = True
    population = abiogenesis()
    while stay_in:
        population=map(mutate_string, population)
        fittest=best_fit(population)
        population=procreate(fittest)
        generation+=1
        for n in range(len(fittest)):
            print('fittest: ', fittest[n], 'fitness: ', fitness(fittest[n]))
        if sum([n == target for n in fittest]):
            print generation
            stay_in=False

def try_fitness():
    print(fitness("methinks it is a weasla"))
    print(fitness("                       "))

def try_best_fit():
    population=abiogenesis()
    print(best_fit(population))

def try_procreate():
    l=procreate(['abc','def','ghi'])
    print l

teh_main()

pop_size = 3
mutation_rate = 3

#try_fitness()
#try_best_fit()
#try_procreate()