# Copyright Big-O Coding

secret_string_S = "Big-O Coding {le@rn a1g0ri7ths vv1th 3xp3rt5}"
secret_string_length = len(secret_string_S)

def count_correct_characters(user_string):
    assert len(user_string) == secret_string_length
    count = 0
    for i in range(len(user_string)):
        if user_string[i] == secret_string_S[i]:
            count += 1

    return count

def check_answer(user_string):
    assert len(user_string) == secret_string_length

    correct_count = count_correct_characters(user_string)

    if correct_count == secret_string_length:
        return True
    
    return False

import random
characters_set = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP"\
"QRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}" # Các ký tự hợp lệ

population = 100 # Số lượng cá thể trong một thế hệ
carried_over_rate = 0.1 # Tỉ lệ cá thể có chỉ số khỏe mạnh được cao được mang trực tiếp sang thế hệ sau
parent_portion = 0.5 # Tỉ lệ cá thể được lựa chọn để kết hợp với nhau
mutation_rate = 0.05 # Tỉ lệ đột biến

def initialize_generation():
    first_generation = []
    for i in range(population):
        string = ""
        for j in range(secret_string_length):
            # Thêm một ký tự ngẫu nhiên trong 
            # characters_set vào chuỗi hiện tại
            string += random.sample(characters_set, 1)[0]
        
        # Tìm chỉ số khỏe mạnh của chuỗi
        fitness_score = count_correct_characters(string)

        # Thêm cá thể vào trong thế hệ hiện tại
        first_generation.append((string, fitness_score))
        
    return first_generation

def perform_selection(first_str, second_str):
    assert len(first_str) == len(second_str)

    L = len(first_str)
    result = ""

    # Kết hợp hai chuỗi với nhau
    for i in range(L):
        choice = random.randint(0, 1)
        result += first_str[i] if choice else second_str[i]

    # Thực hiện đột biến
    for i in range(L):
        choice = random.random()
        if choice < mutation_rate:
            result = result[:i] + random.sample(characters_set, 1)[0] + result[i+1:]

    # Tìm chỉ số khỏe mạnh của chuỗi
    fitness_score = count_correct_characters(result)

    return (result, fitness_score)

def solve():
    generation_id = 0
    next_generation = initialize_generation()
    current_generation = []

    while True:
        generation_id += 1
        current_generation = next_generation
        next_generation = []

        # Sắp xếp các cá thể theo chỉ số khỏe mạnh giảm dần
        current_generation.sort(key=lambda tup: -tup[1])

        # In cá thể tốt nhất của từng thế hệ
        best = current_generation[0]
        # Khắc phục tràn stdout trên ideone
        if generation_id > 300:
	        print(f"Generation {generation_id}")
	        print(f"Best string: {best[0]}")
	        print(f"Fitness score: {best[1]}")
	        print("--------------------------")
        if best[1] == secret_string_length:
            break

        # Chọn 10% cá thể có chỉ số khỏe mạnh cao nhất
        # để mang sang thể hệ sau
        carried_over_idx = int(population * carried_over_rate)
        next_generation += current_generation[:carried_over_idx]

        # Chọn 50% cá thể có chỉ số khỏe mạnh cao nhất
        # để kết hợp với nhau
        parent_idx = int(population * parent_portion)
        parent_group = current_generation[:parent_idx]

        while len(next_generation) < population:
            # Chọn ngẫu nhiên hai cá thể
            first, second = random.sample(parent_group, 2)

            new_child = perform_selection(first[0], second[0])

            next_generation.append(new_child)

solve()