import random
import matplotlib.pyplot as plt

target = "INDIA"
genes = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
size = 20
mutation = 0.1

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

def create():
    return [''.join(random.choices(genes, k=5)) for _ in range(size)]

def select(pop, method):
    if method == "Tournament":
        return max(random.sample(pop, 3), key=fitness)

    if method == "Rank":
        p = sorted(pop, key=fitness)
        return random.choices(p, weights=range(1, size+1))[0]

    if method == "Roulette":
        return random.choices(pop, weights=[fitness(x)+0.01 for x in pop])[0]

    if method == "Truncation":
        p = sorted(pop, key=fitness, reverse=True)[:5]
        return random.choice(p)

def crossover(a, b):
    p = random.randint(1, 4)
    return a[:p] + b[p:]

def mutate(x):
    return ''.join(random.choice(genes) if random.random() < mutation else c for c in x)

methods = ["Tournament", "Rank", "Roulette", "Truncation"]

for method in methods:
    pop = create()
    history = []

    for gen in range(1000):
        pop.sort(key=fitness, reverse=True)
        best = pop[0]
        history.append(fitness(best))

        if fitness(best) == 5:
            break

        new = [best]

        while len(new) < size:
            p1 = select(pop, method)
            p2 = select(pop, method)
            new.append(mutate(crossover(p1, p2)))

        pop = new

    print(method, "Generations:", gen+1, "Best:", best)

    plt.plot(history, label=method)

plt.xlabel("Generation")
plt.ylabel("Fitness")
plt.title("Comparison of Selection Methods")
plt.legend()
plt.show()
