#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 13 16:16:09 2018

@author: yvestalbourdel
"""

import random as rd
import matplotlib.pyplot as plt
import numpy as np

N= 50

#absc=[rd.random() for i in range(N)]
#ordo=[rd.random() for i in range(N)]


#matricedistances=np.zeros((N,N))
#for i in range(N):
 #   for j in range(i):
 #       matricedistances[i][j]=np.sqrt((absc[i]-absc[j])**2+(ordo[i]-ordo[j])**2)
  #      matricedistances[j][i]=matricedistances[i][j]
        
#print(matricedistances)
        
def trajet(seqvoyage,matricedistances):
    longueur=matricedistances[seqvoyage[-1]][seqvoyage[0]]
    for i in range(N-1):
        longueur+=matricedistances[seqvoyage[i]][seqvoyage[i+1]]
    return longueur

def modifseq(seqvoyage):
    global k,l
    doubleseqvoyage=2*seqvoyage
    nouvseqvoyage=2*seqvoyage
    k=rd.randint(0,N-1)
    l=rd.randint(k+3,k+N-1)
    nouvseqvoyage[l]=doubleseqvoyage[k]
    nouvseqvoyage[l-1]=doubleseqvoyage[k+1]
    nouvseqvoyage[k+1]=doubleseqvoyage[l-1]
    nouvseqvoyage[k]=doubleseqvoyage[l]
    nouvseqvoyage=nouvseqvoyage[k:N+k]
    return nouvseqvoyage


essais=1000000         
T=0.07
T0=T 
minlong=100
listelongueurs=[]
temperatures=[T0]                 
coeff=0.999997         
seqvoyageinit=list(range(N))
seqvoyage=seqvoyageinit

for e in range(1,essais):
    newseq=modifseq(seqvoyage)
    newlong=trajet(newseq,matricedistances)
    long=trajet(seqvoyage,matricedistances)               
    ecart=newlong-long
    if (ecart<0):
        minlong=newlong
        seqmin=newseq
    if (ecart<0)or(rd.random()/1000<np.exp(-ecart/T)):
        seqvoyage=newseq
        long=newlong     
    listelongueurs.append(long)
    temperatures.append(T)
    T=T*coeff
    
plt.figure(1)    
plt.plot(listelongueurs)
plt.twinx()
plt.ylabel("Température", color="r")
plt.plot(temperatures, "r-", linewidth=2)
plt.figure(2)
plt.subplot(1,2,1)
x=[absc[seqvoyageinit[i]] for i in range(N)]+[absc[seqvoyage[0]]]
y=[ordo[seqvoyageinit[i]] for i in range(N)]+[ordo[seqvoyage[0]]]
plt.plot(x,y,"r.")
plt.plot(x,y,"k-")
plt.subplot(1,2,2)
x=[absc[seqvoyage[i]] for i in range(N)]+[absc[seqvoyage[0]]]
y=[ordo[seqvoyage[i]] for i in range(N)]+[ordo[seqvoyage[0]]]
plt.plot(x,y,"r.")
plt.plot(x,y,"g-")
plt.show()
print("La séquence retenue",seqvoyage,"a pour longueur",long)
print("La séquence minimale rencontrée",seqmin,"a pour longueur",minlong)