# -*- coding: utf-8 -*-
"""
Created on Sun Feb 13 15:44:39 2022
8850
@author: nicolas.rincon
"""



import pandas as pd

# Procedimiento para importar los datos
Data=pd.read_csv('TSP38.txt',sep=' ',header=0)
# Variable global M: Matrix de distancias de tamaño numero de ubicaciones * numero de ubicaciones
# para acceder a un valor de la Matriz M[posi][posj]
M=[]
for i in range (Data.shape[0]):
    L=[]
    for j in range(Data.shape[0]):
        CXI=Data.at[i,'CX']
        CYI=Data.at[i,'CY']
        CXJ=Data.at[j,'CX']
        CYJ=Data.at[j,'CY']
        D=(((CXI-CXJ)**2)+((CYI-CYJ)**2))**0.5
        L.append(D)
    M.append(L)
#print(M[0])

# Funcion para generar una solucion con la heuristica del vecino mas cercano
# la solucion se representa en un vector 
# explicacion de la heuristica en el video correspondiente
# el parametro de entrada es la ciudad inicio
def HVM(ciudad):
    c=ciudad
    S=[]
    n=Data.shape[0]
    #El vector Aubicado se emplea para controlar que ubicaciones ya se encuentran dentro de la solucion
    AUbicado=[]
    for iH in range(n):
        AUbicado.append(0)
    AUbicado[c]=1
    S.append(c)
    for j in range(n-1):
        ACiudadesEvaluar=[]
        ADistanciasEvaluar=[]
        for iH in range(n):
            if AUbicado[iH]==0:
                ACiudadesEvaluar.append(iH)
                ADistanciasEvaluar.append(M[c][iH])
        #Se genera un DataFrame para ordenar y econtrar la ciudad no visitada mas cercana
        # esto se podria reemplazar por un funcion propian o un metodo de numpy pero numpy no hace parte del contenido
        # del webinar        
        DataCiudadesCercanas=pd.DataFrame({'CiudadesEvaluar':ACiudadesEvaluar,'DistanciasEvaluar':ADistanciasEvaluar})
        DataCiudadesCercanas.sort_values(by='DistanciasEvaluar',ascending=True,inplace=True)
        DataCiudadesCercanas.reset_index(drop='True',inplace=True)
        c=DataCiudadesCercanas.at[0,'CiudadesEvaluar']
        S.append(c)
        AUbicado[c]=1
    S.append(ciudad)
    return S
AR=HVM(0)
print('Se imprime la solución y su Funcion Objetivo')
print(AR)

# Procedimiento para calcular la Funcion Objetivo recibiendo como parametro
# una solcucion en representacion vectorial
def CalculoFOTSP(S):
    DistanciaRuta=0
    Saux=S
    for i in range(1,len(Saux)):
        DistanciaRuta=DistanciaRuta+M[Saux[i-1]][Saux[i]]
    DistanciaRuta=DistanciaRuta+M[0][Saux[i]]
    return DistanciaRuta
FO=CalculoFOTSP(AR)
print(FO)


#El codigo en comnentario permite correr la heuristica
#del vecino mas cercano iniciando en cada ciudad 
"""
for i in range(Data.shape[0]):
    Solucion=HVM(i)
    print(i,CalculoFOTSP(Solucion))
"""

#La mejor solucion con esta heusitica se encuentra iniciando en la ciudad 6
AR=HVM(6)
FO=CalculoFOTSP(AR)

import matplotlib.pyplot as plt
AR=HVM(6)
print(AR)
FO=CalculoFOTSP(AR)
print('FO',FO)
ACXR=[]
ACYR=[]
for i in range(len(AR)):
    ACXR.append(Data.at[AR[i],'CX'])
    ACYR.append(Data.at[AR[i],'CY'])
plt.plot(ACYR,ACXR, color='darkgreen',marker='o')
plt.show()    
#"""