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

def eucli(P1, P2):
    """
    Renvoie la distance euclidienne entre P1 et P2
    """
    x1, y1 = P1
    x2, y2 = P2
    return np.sqrt((x2-x1)**2 + (y1-y2)**2)

def matrice_distances(villes):
    """
    Renvoie la matrice des distances de villes.
    """
    n = len(villes)
    M = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            M[i, j] = eucli(villes[i], villes[j])
    return M


def plus_proche_voisin(M, vu, i):
    """
    Renvoie l'indice de la ville non-vue la plus
    proche de la ville i.
    M est la matrice des distances, et vu est un
    tableau de booléens indiquant, pour chaque ville,
    si elle a été vue ou non.
    """
    j_min = -1   # ville la plus proche
    d_min = None # distance minimale
    n = len(M)
    for j in range(n):
        if not vu[j]:
            if j_min == -1 or M[i, j] < d_min:
                j_min = j
                d_min = M[i, j]
    return j_min


def voyageur_glouton(villes):
    """
    Renvoie un itinéraire visitant chaque ville de `villes`
    selon un algorithme glouton. Le résultat est un couple
    (chemin, d), où chemin est une liste d'indices donnant
    les différentes villes à visiter, et d la distance totale
    (en prenant en compte le coût de retour à la ville initiale).
    """
    M = matrice_distances(villes)
    i = 0
    n = len(villes)
    vu = [False for j in range(n)]
    vu[0] = True
    chemin = [0]
    d = 0
    for j in range(n-1):
        actuel = chemin[-1]
        prochain = plus_proche_voisin(M, vu, actuel)
        d += M[actuel, prochain]
        chemin.append(prochain)
        vu[prochain] = True
    # pour finir, on revient en 0
    d += M[chemin[-1], 0]
    return chemin, d


def gen_pts(n):
    """
    Renvoie une liste de n points aléatoires dans le carré unité.
    """
    return [(random.random(), random.random()) for k in range(n)]


def plot_points(pts, chemin, d, color, x_offset):
    """
    Affiche les points pts, ainsi que le chemin  `chemin`,
    et affiche la distance totale parcourue.
    Paramètres:
    - pts est une liste de points du plan
    - chemin est une liste d'indices de pts formant un chemin
    - d est la distance totale de chemin
    - color donne la couleur à utiliser pour le chemin
    - x_offset dit où afficher le chemin sur le graphique.
    """
    # afficher les points
    for i, (x, y) in enumerate(pts):
        plt.plot([x+x_offset], [y], 'ro')
        plt.text(x+x_offset, y, f"{i}")

    # afficher la distance
    plt.text(x_offset, -0.1, f"Total: {int(100*d)/100}")
    plt.xlim(-0.2, 1.2+x_offset)
    plt.ylim(-0.2, 1.2+x_offset)

    # afficher le chemin
    n = len(chemin)
    for i in range(len(chemin)):
        j1 = chemin[i]
        j2 = chemin[(i+1)%n] # modulo pour boucler sur 0
        x1, y1 = pts[j1]
        x2, y2 = pts[j2]
        plt.plot([x1+x_offset, x2+x_offset], [y1, y2], f"{color}-")

    plt.show()

def chemin_random(pts):
    """
    Renvoie une permutation aléatoire de [0, ..., n-1],
    où n est la longueur de pts.
    """
    n = len(pts)
    L = list(range(n))
    random.shuffle(L) # mélange aléatoirement L
    d = eucli(pts[L[-1]], pts[L[0]]) # distance du dernier segment
    for i in range(n-1):
        d += eucli(pts[L[i]], pts[L[i+1]])
    return L, d


# test: comparer le chemin de l'algorithme glouton et un chemin
# totalement aléatoire.
pts = gen_pts(10)
chemin, d = voyageur_glouton(pts)
plot_points(pts, chemin, d, 'r', 0)
chemin, d = chemin_random(pts)
plot_points(pts, chemin, d, 'g', 1)