import random

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
target = "METHINKS IT IS LIKE A WEASEL"

def fitness(child):
    fit = 0

    for a, b in zip(child, target):
        if a == b:
            fit += 1

    return fit

def reproduce(parent):
    child = ""
    for gene in parent:
        child += random.choice(alphabet) if random.randint(1, 50) == 1 \
                                         else gene
    return child

parent = [random.choice(alphabet) for _ in target]

generation = 1
print "%d %s (%d)" % (generation, parent, fitness(parent))

while True:
    child = reproduce(parent)
    generation += 1

    child_fit, parent_fit = fitness(child), fitness(parent)

    if child_fit > parent_fit:
        parent, parent_fit = child, child_fit

    print "%d %s (%d)" % (generation, parent, parent_fit)

    if parent_fit == len(target):
        break

print "Finished! Target reached in %d generations!" % generation