from random import choices, randrange, random

# Target Word
targetString = input("Enter Target String: ")

# Gene Pool
genes = input("Enter Jumbled Words: ")

population_size = 30
parents_required = 4
mutation_rate = 0.10

population = []

# Create Initial Population
def createPopulation():

    global population

    for i in range(population_size):

        individual = []

        for j in range(len(targetString)):
            individual.append(genes[randrange(len(genes))])

        population.append(individual)


# Fitness Function
def determineFitness(pop):

    fitness = []

    probability = []

    print("\nPopulation")

    for individual in pop:

        fit = 0

        for i in range(len(targetString)):

            if individual[i] == targetString[i]:
                fit += 1

        fitness.append(fit)

        print("".join(individual), " Fitness =", fit)

    total = sum(fitness)

    if total == 0:
        probability = [1/len(pop)]*len(pop)

    else:
        for f in fitness:
            probability.append(f/total)

    return fitness, probability

# Roulette Wheel Selection
def rouletteSelection(pop):

    fitness, probability = determineFitness(pop)

    parents = choices(pop,
                      weights=probability,
                      k=parents_required)

    print("\nSelected Parents")

    for p in parents:
        print("".join(p))

    return parents


# Crossover
def crossover(parent1,parent2):

    point = randrange(1,len(targetString)-1)

    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]

    return child1,child2

# Mutation
def mutation(child):

    for i in range(len(child)):

        if random() < mutation_rate:

            child[i] = genes[randrange(len(genes))]

    return child


# Best Individual
def best(pop):

    bestIndividual = pop[0]
    bestFitness = -1

    for individual in pop:

        fit = 0

        for i in range(len(targetString)):
            if individual[i] == targetString[i]:
                fit += 1

        if fit > bestFitness:

            bestFitness = fit
            bestIndividual = individual

    return bestIndividual,bestFitness

# Main Genetic Algorithm
createPopulation()

generation = 1

while True:

    print("\n")
    print("="*60)
    print("Generation",generation)
    print("="*60)

    bestIndividual,bestFitness = best(population)

    print("\nBest Chromosome :", "".join(bestIndividual))
    print("Fitness :",bestFitness,"/",len(targetString))

    if bestFitness == len(targetString):

        print("\nTARGET FOUND")
        print("Final Answer =", "".join(bestIndividual))
        break

    parents = rouletteSelection(population)

    newPopulation = []

    # Elitism
    newPopulation.append(bestIndividual)

    while len(newPopulation) < population_size:

        p1 = choices(parents)[0]
        p2 = choices(parents)[0]

        child1,child2 = crossover(p1,p2)

        child1 = mutation(child1)
        child2 = mutation(child2)

        newPopulation.append(child1)

        if len(newPopulation) < population_size:
            newPopulation.append(child2)

    population = newPopulation

    generation += 1
