import numpy as np
import random
import math

random.seed(100)

class City:

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f"({self.x}, {self.y})"
    
    def __eq__(self, other):
        if isinstance(other, City):
            return self.x == other.x and self.y == other.y
        return False
    
    def __hash__(self) -> int:
        return self.__repr__().__hash__()

def generate_cities(num_cities):
    cities = []
    for _ in range(num_cities):
        cities.append(City(random.randint(0, 10), random.randint(0, 10)))
    return cities
    
def distance(this, that):
    return np.sqrt((this.x - that.x)**2 + (this.y - that.y)**2)
    
def calculate_fitness(route):
    d = 0
    for i in range(len(route)):
        if i + 1 == len(route):
            d += distance(route[i], route[0])
        else:
            d += distance(route[i], route[i + 1])
    return 1 / d

def generate_population(cities, population_size):
    routes = []
    for _ in range(population_size):
        routes.append(random.sample(cities, len(cities)))
    return routes

def tournament_selection(population, tournament_size=3):
    indices = random.sample(range(len(population)), tournament_size)
    fitnesses = [calculate_fitness(population[i]) for i in indices]
    best_index = indices[fitnesses.index(max(fitnesses))]
    return population[best_index]

def mutate(route, mutation_rate=0.1):
    if (random.random() < mutation_rate):
        i1 = random.randint(0, len(route) - 1)
        i2 = random.randint(0, len(route) - 1)
        route[i1], route[i2] = route[i2], route[i1]
    return route

def get_crossing_point(parent1):
    return random.randint(1, len(parent1) - 1)

def crossover(parent1, parent2):
    crossover_point = get_crossing_point(parent1)
    child = parent1[:crossover_point]
    for city in parent2:
        if city not in child:
            child.append(city)
    return child

def next_generation(population, crossover_rate, mutation_rate):

    next_pop = []

    cross = math.floor(len(population) * crossover_rate)
    normal = len(population) - cross

    for _ in range(normal):
        next_pop.append(random.choice(population))

    for _ in range(cross):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        next_pop.append(crossover(parent1, parent2))

    next_pop = [mutate(p, mutation_rate) for p in next_pop]

    return next_pop