import math
import random
import copy
import time


def dist(first_point, second_point):

    return math.sqrt((second_point[0] - first_point[0]) ** 2 + (second_point[1] - first_point[1]) ** 2)


def readFile():
    lst1 = []
    with open("cityData.txt") as file:
        for line in file:
            firstMatrix = []
            x1, y1, z1 = line.split()
            firstMatrix.append(float(x1))
            firstMatrix.append(float(y1))
            firstMatrix.append(z1)
            lst1.append(firstMatrix)
    return lst1


def get_distance(aList):

    result = sum([dist(x[:-1], y[:-1]) for x, y in zip(aList, aList[1:])])
    result += dist(aList[-1][:-1],aList[0][:-1])
    return result


def acceptanceProbability(energy, newEnergy, temperature):
    if newEnergy < energy:
        return 1.0
    else:
        return math.exp((energy-newEnergy)/temperature)


def neighbor_generator(alist, index1, index2):
            copy_list = copy.deepcopy(alist)
            copy_list[index1],copy_list[index2]= copy_list[index2],copy_list[index1]
            return copy_list


def simmulated_annealing(cityPaths,startTemp, cooling_rate):
    old_path = random.sample(cityPaths,len(cityPaths))


    old_cost = get_distance(old_path)
    print("starting path is"+str(old_path))
    print("starting cost is "+str(old_cost))
    best = []


    counter = 0
    while startTemp>1:
        # i = 1
        # #print(startTemp)
        # while i<=100:

        rando_list = random.sample(range(0,14), 2)
        new_path = neighbor_generator(old_path,rando_list[0],rando_list[1])
        new_cost = get_distance(new_path)
        probs = acceptanceProbability(old_cost, new_cost, startTemp)
        if new_cost < old_cost:
            old_cost = new_cost
            old_path = new_path
            if old_cost not in best and (len(best) < 50):
                best.append(old_cost)
        else:
            if probs > random.random():
                old_cost = new_cost
                old_path = new_path



        startTemp *= 1-cooling_rate



    print("the best path is "+ str(old_path))
    print("the trip cost is "+str(old_cost))



if __name__ == '__main__':
    cityPaths = readFile()
    simmulated_annealing(cityPaths,10000,0.003)