#!/usr/bin/python3
# Markov Chain Monte Carlo with the simulated annealing for the music band problem

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm
import matplotlib.colors as colors

############################
### DATA (DO NOT MODIFY) ###
############################
cities = [ 'Paris', 'Lyon', 'Toulouse', 'Nice', 'Nantes', 'Montpellier', 'Strasbourg', 'Bordeaux', 'Lille', 'Le Havre', 'Clermont-Ferrand', 'Limoges', 'Orléans' ]

longitudes = [ "2°21'07''", "4°49'56''", "1°26'38''", "7°16'17''", "-1°33'10''", "3°52'38''", "7°45'08''", "-0°34'46''", "3°03'48''", "0°06'00''", "3°04'56''", "1°15'00''", "1°54'32''" ] # longitudes are counted negative if west, and positive if east.

latitudes = [ "48°51'24''", "45°45'28''", "43°36'16''", "43°41'45''", "47°13'05''", "43°36'43''", "48°34'24''", "44°50'16''", "50°38'14''", "49°29'24''", "45°46'33''", "45°51'00''", "47°54'09''" ]

###############################################################################
### FUNCTION TO EXTRACT LONGITUDES AND LATITUDES IN RADIANS (DO NOT MODIFY) ###
###############################################################################
def extract_coordinates(coord):
    """
    Input:
    coord: list of strings of longitudes or latitudes (degrees, minutes, seconds)
    
    Return:
    coord_val: values of the coordinates in rad
    """
    coord_val = [ ]
    for l in coord:
        l1 = l.partition("'")[0]
        l2 = l.partition("'")[-1]
        degrees = float(l1.partition("°")[0])
        minutes = float(l1.partition("°")[-1])
        seconds = float(l2.partition("''")[0])
        if l1[0] == '-':
            minutes = - minutes
            seconds = - seconds
        coord_val.append(( degrees + minutes / 60. + seconds / 3600. ) * np.pi / 180.)
    return coord_val

#################################################
### CONVERTED DATA IN RADIANS (DO NOT MODIFY) ###
#################################################
longitudes_rad = extract_coordinates(longitudes)
latitudes_rad = extract_coordinates(latitudes)

#################################################
### FUNCTIONS TO PLOT THE MAP (DO NOT MODIFY) ###
#################################################
def planisphere(long, lat):
    """
    Inputs:
    long: longitude of a city
    lat: latitude of a city
    
    Return:
    coordinates of its Mercator projection on the plane (to build a map)
    """
    return 50. / np.pi * long, 50. / np.pi * np.log(np.tan(np.pi / 4. + lat / 2.))
    
def road_trip(path):
    """
    Input:
    path: order in which cities are visited
    
    Return:
    plot of the cities with the paths
    """
    xcoord = [ ]
    ycoord = [ ]
    for i in range(len(cities)):
        x, y = planisphere(longitudes_rad[i], latitudes_rad[i])
        xcoord.append(x)
        ycoord.append(y)
    fig, ax = plt.subplots()
    ax.scatter(xcoord, ycoord, c = 'k')
    norm = colors.Normalize(vmin = 0, vmax = len(cities))
    cmap = cm.rainbow
    for i, txt in enumerate(cities):
        ax.annotate(cities[i], (xcoord[i], ycoord[i]))
        ax.plot([ xcoord[path[i]], xcoord[path[( i + 1 ) % len(cities)]] ], [ ycoord[path[i]], ycoord[path[( i + 1 ) % len(cities)]] ], c = cmap(norm(i)))
    sm = cm.ScalarMappable(cmap = cmap, norm = norm)
    sm.set_array([])
    cbar = plt.colorbar(sm, ax=ax)
    cbar.set_label('Path number')
    plt.xlabel('x')
    plt.ylabel('y')
    plt.show()
    
#####################################
### OPTIMIZATION (TO BE MODIFIED) ###
#####################################