#!/usr/bin/python

import random, math, time


matrix = [
    [0,29,82,46,68,52,72,42,51,55,29,74,23,72,46],  
    [29,0,55,46,42,43,43,23,23,31,41,51,11,52,21],  
    [82,55,0,68,46,55,23,43,41,29,79,21,64,31,51],  
    [46,46,68,0,82,15,72,31,62,42,21,51,51,43,64],  
    [68,42,46,82,0,74,23,52,21,46,82,58,46,65,23],  
    [52,43,55,15,74,0,61,23,55,31,33,37,51,29,59],  
    [72,43,23,72,23,61,0,42,23,31,77,37,51,46,33],  
    [42,23,43,31,52,23,42,0,33,15,37,33,33,31,37],  
    [51,23,41,62,21,55,23,33,0,29,62,46,29,51,11],  
    [55,31,29,42,46,31,31,15,29,0,51,21,41,23,37],  
    [29,41,79,21,82,33,77,37,62,51,0,65,42,59,61],  
    [74,51,21,51,58,37,37,33,46,21,65,0,61,11,55],  
    [23,11,64,51,46,51,51,33,29,41,42,61,0,62,23],  
    [72,52,31,43,65,29,46,31,51,23,59,11,62,0,59],  
    [46,21,51,64,23,59,33,37,11,37,61,55,23,59,0] ]


class TSP:
    def __init__(self, distancematrix):
        """distancematrix is a matrix of size N*N, giving the distance between two cities
        A matrix allows us to have different distances from A to B than from B to A, but that wouldn't |make sense.
        Hence we'll use an upper triangular matrix, the rest of the values are undefined and we don't care |about them """
        self.distances = distancematrix
        self.size = len(self.distances[0])

    def totaldistance(self, solution):
        return sum(self.distances[i][j] for i, j in zip(solution, solution[1:]))

    def random_solve(self):
        sol = list(range(self.size))
        random.shuffle(sol)        
        return sol

    def tweak(self, solution):
        """ Swap two random cities """
        solution = solution[::] # create copy
        i, j = random.sample(range(self.size), 2)
        solution[i], solution[j] = solution[j], solution[i]
        return solution


class SA:
    def __init__(self, pb, init_temp, cool_rate):
        self.pb = pb
        self.coolrate = 1 - cool_rate
        self.inittemp = init_temp

    def stillaccept(self, rdist, sdist, t):
        return random.random() < math.exp((rdist - sdist) / t)

    def run(self):
        pb = self.pb
        s = pb.random_solve()
        sdist = pb.totaldistance(s)
        best = s; bestdistance = sdist
        t = self.inittemp
        while t > 1:
            r = pb.tweak(s)
            rdist = pb.totaldistance(r)
            if rdist < sdist or self.stillaccept(rdist, sdist, t):
                s = r; sdist = rdist
            t *= self.coolrate # Cool system
            if rdist < bestdistance:
                best = r; bestdistance = rdist
        return best, bestdistance


exp_temp = 50.
cool_rate = 0.01
tsp = TSP(matrix)
sa = SA(tsp, 10 ** exp_temp, cool_rate)
r = []
for i in range(100):
   s, d = sa.run()
   r.append(d)
print('mean', sum(r) / len(r))
print('min', min(r), 'max', max(r))