from random import *

target = input("Enter Target String: ")
genes = input("Enter Gene Pool: ")

size = 30
mutation_rate = 0.1

# Create Population
def create():
    return [[choice(genes) for j in range(len(target))]
            for i in range(size)]

# Fitness
def fitness(x):
    return sum(x[i] == target[i] for i in range(len(target)))

# Crossover
def crossover(p1, p2):
    point = randrange(1, len(target))
    return p1[:point]+p2[point:], p2[:point]+p1[point:]

# Mutation
def mutate(child):
    for i in range(len(child)):
        if random() < mutation_rate:
            child[i] = choice(genes)
    return child

# Genetic Algorithm
pop = create()
generation = 1

while True:
    scores = [fitness(x) for x in pop]
    best = max(range(size), key=lambda i: scores[i])

    print("Generation:", generation,
          "Best:", "".join(pop[best]),
          "Fitness:", scores[best])

    if scores[best] == len(target):
        print("Target Found:", "".join(pop[best]))
        break

    parents = choices(pop, weights=[s+0.01 for s in scores], k=4)
    new = [pop[best]]

    while len(new) < size:
        c1, c2 = crossover(choice(parents), choice(parents))
        new.append(mutate(c1))
        if len(new) < size:
            new.append(mutate(c2))

    pop = new
    generation += 1