import random
import math


def create_initial_population(population_size, new_list, player):
    population = []
    for _ in range(population_size):
        chromosome = new_list.copy()
        chromosome.remove((player.x+1, player.y+1))
        random.shuffle(chromosome)
        chromosome.insert(0, (player.x+1, player.y+1))
        population.append(chromosome)
    return population


def calculate_distance(node1, node2):
    x1, y1 = node1
    x2, y2 = node2
    distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return distance


def calculate_fitness(individual):
    total_distance = 0
    num_nodes = len(individual)

    for i in range(num_nodes - 1):
        node1 = individual[i]
        node2 = individual[i + 1]
        distance = calculate_distance(node1, node2)

        total_distance += distance

    if total_distance == 0:
        fitness = float('inf')
        return fitness

    fitness = 1 / total_distance
    return fitness


def crossover(parent1, parent2, player):
    child = [(player.x+1, player.y+1)] + [None] * (len(parent1) - 1)
    start_index = random.randint(1, len(parent1) - 1)
    end_index = random.randint(start_index + 1, len(parent1))
    child[start_index:end_index] = parent1[start_index:end_index]
    remaining_nodes = [node for node in parent2 if node not in child]
    child[1:start_index] = remaining_nodes[:start_index - 1]
    child[end_index:] = remaining_nodes[start_index - 1:]
    return child


def mutate(individual, mutation_rate):
    for i in range(1, len(individual)):
        if random.random() < mutation_rate:
            j = random.randint(1, len(individual) - 1)
            individual[i], individual[j] = individual[j], individual[i]
    return individual


def genetic_algorithm(new_list, player):
    max_generations = 200
    population_size = 200
    mutation_rate = 0.1
    population = create_initial_population(population_size, new_list, player)
    best_individual = None
    best_fitness = float('-inf')

    for generation in range(max_generations):
        fitness_values = [calculate_fitness(individual) for individual in population]
        population = [x for _, x in sorted(zip(fitness_values, population), reverse=True)]
        fitness_values.sort(reverse=True)
        best_individuals = population[:10]
        new_population = best_individuals.copy()

        while len(new_population) < population_size:
            parent1, parent2 = random.choices(best_individuals, k=2)
            child = crossover(parent1, parent2, player)
            child = mutate(child, mutation_rate)
            new_population.append(child)

        for individual in best_individuals:
            fitness = calculate_fitness(individual)
            if fitness > best_fitness:
                best_fitness = fitness
                best_individual = individual

        population = new_population[:population_size]

    return best_individual