import random

from tsp import TSP

random.seed(1)


def hill_climb_with_k_opt(tsp, tour, k):
    fails_before_quit = 1000

    fails = 0
    sol = tour
    score = tsp.score(tour)
    while fails < fails_before_quit:
        new_sol = tsp.k_opt(sol, k)
        new_score = tsp.score(new_sol)

        if new_score < score:
            sol = new_sol
            score = new_score
            fails = 0
        else:
            fails += 1
    return sol, score


tsp = TSP.from_file("tsp50.txt")
best_score = None
gen = 0

while True:
    gen += 1
    sol = tsp.random_grasp_tour(0.2)
    sol, score = hill_climb_with_k_opt(tsp, sol, 2)
    if best_score is None or score < best_score:
        best_score = score
        print(f"Gen {gen} - new best score {best_score}")