import random
import string

# Das Ziel-Genom
TARGET = "METHINKS IT IS LIKE A WEASEL"
# Der Gen-Pool (A-Z + Leerzeichen)
ALPHABET = string.ascii_uppercase + " "
# Parameter für die Evolution
MUTATION_RATE = 0.05  # 5% Chance pro Buchstabe
COPIES = 100         # Anzahl der Nachkommen pro Generation

def generate_random_string(length):
    return "".join(random.choice(ALPHABET) for _ in range(length))

def get_fitness(source):
    """Berechnet, wie viele Zeichen bereits korrekt sind."""
    return sum(1 for s, t in zip(source, TARGET) if s == t)

def mutate(parent):
    """Erzeugt eine Mutation basierend auf der Mutationsrate."""
    res = ""
    for char in parent:
        if random.random() < MUTATION_RATE:
            res += random.choice(ALPHABET)
        else:
            res += char
    return res

def evolve():
    current_best = generate_random_string(len(TARGET))
    generation = 0
    
    while current_best != TARGET:
        generation += 1
        # Erzeuge COPIES Mutationen vom aktuellen Besten
        next_generation = [mutate(current_best) for _ in range(COPIES)]
        
        # Wähle das fitteste Individuum aus der neuen Generation
        current_best = max(next_generation, key=get_fitness)
        
        # Fortschritt ausgeben
        if generation % 10 == 0 or current_best == TARGET:
            print(f"Gen {generation:3}: {current_best} (Fitness: {get_fitness(current_best)})")

if __name__ == "__main__":
    evolve()