# Travelling Salesman Problem
import random
import math
import matplotlib.pyplot as plt

cities = {
    "Delhi": (2, 9),
    "Mumbai": (1, 2),
    "Bengaluru": (3, 0),
    "Chennai": (5, 1),
    "Hyderabad": (4, 3),
    "Kolkata": (9, 7),
    "Pune": (2, 3),
    "Ahmedabad": (0, 6),
    "Jaipur": (2, 8),
    "Lucknow": (5, 8)
}

names = list(cities)
size = 50
generations = 100
mutation = 0.15

def distance(a, b):
    x1, y1 = cities[a]
    x2, y2 = cities[b]
    return math.dist((x1, y1), (x2, y2))

def fitness(route):
    return sum(distance(route[i], route[(i+1)%len(route)])
               for i in range(len(route)))

def create():
    return [random.sample(names, len(names)) for _ in range(size)]

def select(pop):
    return min(random.sample(pop, 3), key=fitness)

def crossover(a, b):
    p, q = sorted(random.sample(range(len(a)), 2))
    child = a[p:q] + [x for x in b if x not in a[p:q]]
    return child

def mutate(route):
    a, b = random.sample(range(len(route)), 2)
    route[a], route[b] = route[b], route[a]
    return route

pop = create()
best = min(pop, key=fitness)

for gen in range(generations):
    new = [best.copy()]

    while len(new) < size:
        child = crossover(select(pop), select(pop))

        if random.random() < mutation:
            child = mutate(child)

        new.append(child)

    pop = new
    current = min(pop, key=fitness)

    if fitness(current) < fitness(best):
        best = current.copy()

    if gen % 10 == 0:
        print("Generation:", gen, "Distance:", round(fitness(best), 2))

print("\nBest Route:")
print(" -> ".join(best + [best[0]]))
print("Total Distance:", round(fitness(best), 2))

route = best + [best[0]]
x = [cities[c][0] for c in route]
y = [cities[c][1] for c in route]

plt.plot(x, y, marker="o")
for c in names:
    plt.text(*cities[c], c)

plt.title("Travelling Salesman using GA")
plt.grid()
plt.show()
