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

# Exercice 1

def kNN(les_points, point_sup, k, dist):
    """Algorithme des k plus proches voisins pour une liste de couples
    (valeur, étiquette), une valeur supplémentaire, la valeur de k
    et une fonction de distance.
    En cas d'égalité du k-ième voisin, le comportement est non spécifié.
    En cas d'égalité parmi les k plus proches voisins, la première occurrence
    est privilégiée (non spécifié si la distance est égale),
    au vu du parcours du dictionnaire. Ceci dépend d'ailleurs de la version.
    """
    distances = [(dist(point[0], point_sup), point[1]) for point in les_points]
    distances.sort()
    etiquettes = {}
    for _, etiq in distances[:k]:
        if etiq in etiquettes:
            etiquettes[etiq] += 1
        else:
            etiquettes[etiq] = 1
    rep = etiq # Initialisation pertinente plutôt que None
    for e in etiquettes: # Moche de réutiliser le nom etiq, mais ça marcherait
        if etiquettes[e] > etiquettes[rep]:
            rep = e
    return rep

# Exercice 2

def disteucl(point1, point2):
    """Calcule la distance euclidienne entre deux points d'un même espace."""
    sommecarres = 0
    for x, y in zip(point1, point2): # oh que c'est beau !
        sommecarres += (x-y) ** 2
    return sommecarres ** .5

def kNN_sur_Rd(les_points, point_sup, k):
    """Algorithme des k plus proches voisins pour des points d'un espace
    de dimension d quelconque muni de la distance euclidienne.
    """
    return kNN(les_points, point_sup, k, disteucl) # Et le tour est joué !

# Exercice 3

def moyenne(ensemble):
    """Calcule le barycentre d'une liste de points.
    """
    total = list(ensemble[0])
    n = len(total)
    for i in range(1, len(ensemble)):
        for j in range(n):
            total[j] += ensemble[i][j]
    return tuple([valeur / len(ensemble) for valeur in total])

def variance(ensemble):
    """Calcule la variance d'une liste de points,
    en tant que somme des carrés des distances entre les points
    et le barycentre de la liste.
    """
    if len(ensemble) < 2:
        return 0
    barycentre = moyenne(ensemble)
    rep = 0
    for point in ensemble:
        rep += disteucl(point, barycentre) ** 2
    return rep

def kmeans(les_points, k, verbeux=False, renvoyer_variance=False):
    """Algorithme des k-moyennes pour une liste de points
    dans un espace de dimension quelconque.
    L'argument supplémentaire verbeux détermine si l'algorithme doit imprimer
    les variances successives.
    L'argument supplémentaire renvoyer_variance détrmine si la variance finale
    doit être renvoyée également."""
    M = random.sample(les_points, k)
    E = [[] for _ in range(k)]
    Mbis = None
    STOP = 1000
    while STOP > 0 and Mbis != M:
        STOP -= 1
        Mbis = M
        E = [[] for _ in range(k)]
        for point in les_points:
            indice = 0
            for i in range(1, k):
                if disteucl(point, M[i]) < disteucl(point, M[indice]):
                    indice = i
            E[indice].append(point)
        M = []
        for liste in E:
            if liste == []: # On va espérer que cela n'arrive pas
                M.append(random.choice(les_points)) # … ni de tomber deux fois sur le même point !
            else:
                M.append(moyenne(liste))
        if verbeux:
            print("Somme des variances : ", sum([variance(liste) for liste in E]))
    if renvoyer_variance:
        return E, sum([variance(liste) for liste in E])
    return E

# Exercice 4

def kNN_rayon(les_points, point_sup, k, dist, r):
    """Algorithme des k plus proches voisins pour une liste de couples
    (valeur, étiquette), une valeur supplémentaire, la valeur de k,
    une fonction de distance et un rayon maximal.
    Au plus k voisins sont pris, aucun n'étant pris au-delà d'un rayon de r.
    Si aucun voisin n'est dans un rayon de r, seul le plus proche compte,
    avec un comportement non spécifié en cas d'égalité.
    En cas d'égalité du k-ième voisin, le comportement est non spécifié.
    En cas d'égalité parmi les k plus proches voisins, la première occurrence
    est privilégiée (non spécifié si la distance est égale),
    au vu du parcours du dictionnaire. Ceci dépend d'ailleurs de la version.
    """
    distances = [(dist(point[0], point_sup), point[1]) for point in les_points]
    distances.sort()
    etiquettes = {}
    nb = 0
    while nb < k:
        dis, etiq = distances[nb]
        if dis > r and nb > 0:
            break # On quitte prématurément la boucle
        if etiq in etiquettes:
            etiquettes[etiq] += 1
        else:
            etiquettes[etiq] = 1
        nb += 1
    rep = etiq # Initialisation pertinente plutôt que None
    for e in etiquettes: # Moche de réutiliser le nom etiq, mais ça marcherait
        if etiquettes[e] > etiquettes[rep]:
            rep = e
    return rep

# Exercice 5

def kNN_rayonbis(les_points, point_sup, k, dist, r):
    """Algorithme des k plus proches voisins pour une liste de couples
    (valeur, étiquette), une valeur supplémentaire, la valeur de k,
    une fonction de distance et un rayon maximal.
    Au moins k voisins sont pris, tous ceux dans un rayon de r étant pris.
    En cas d'égalité du k-ième voisin, le comportement est non spécifié.
    En cas d'égalité parmi les k plus proches voisins, la première occurrence
    est privilégiée (non spécifié si la distance est égale),
    au vu du parcours du dictionnaire. Ceci dépend d'ailleurs de la version.
    """
    distances = [(dist(point[0], point_sup), point[1]) for point in les_points]
    distances.sort()
    etiquettes = {}
    nb = 0
    eloignement = distances[nb][0]
    while nb < k or eloignement < r: # différence majeure mais pas la seule
        etiq = distances[nb][1]
        if etiq in etiquettes:
            etiquettes[etiq] += 1
        else:
            etiquettes[etiq] = 1
        if nb < len(distances)-1:
            eloignement = distances[nb+1][0]
        else:
            eloignement = r # arrêt pour éviter l'erreur
        nb += 1
    rep = etiq # Initialisation pertinente plutôt que None
    for e in etiquettes: # Moche de réutiliser le nom etiq, mais ça marcherait
        if etiquettes[e] > etiquettes[rep]:
            rep = e
    return rep

# Exercice 6

def engendre_points(nombre):
    """Engendre une liste de points de taille l'argument dont les deux coordonnées
    sont entre -1.5 et 1.5 exclus. Les points sont assortis d'une étiquette 1
    si leur distance à l'origine est inférieure à 1 et 0 sinon."""
    l = []
    for _ in range(nombre):
        x = random.random() * 3 - 1.5
        y = random.random() * 3 - 1.5
        l.append(((x, y), disteucl((x, y), (0, 0)) <= 1)) # oui, trois parenthèses !
    return l

def kNNdisque(nombre_points, k, nombre_experiences):
    """Effectue un test de l'algorithme des k plus proches voisins
    pour des points pris dans le carré ]-1, 1[² avec pour étiquette
    l'appartenance ou non au disque délimité par le cercle trigonométrique.
    L'expérience est répétée autant de fois que le deuxième argument le précise,
    et la fonction retourne la matrice de confusion."""
    les_points = engendre_points(nombre_points)
    matrice = [[0, 0], [0, 0]] # [[pas_dedans_et_correct, dedans_non_detecte], [pas_dedans_erreur, dedans_et_correct]]
    for _ in range(nombre_experiences):
        point_sup = (random.random() * 3 - 1.5, random.random() * 3 - 1.5)
        reponse_obtenue = kNN_sur_Rd(les_points, point_sup, k)
        matrice[reponse_obtenue][disteucl(point_sup, (0, 0)) <= 1] += 1
    return matrice

# Exercice 7

def kNNdessin_n_essais(nombre_points, nombre_essais, k):
    """Effectue un certain nombre de tests de l'algorithme
    des k plus proches voisins pour des points pris dans le carré
    ]-1,5; 1,5[² avec pour étiquette l'appartenance ou non au disque
    délimité par le cercle trigonométrique.
    Le résultat apparaît dans une fenêtre graphique,
    en représentant en bleu le cercle trigonométrique."""
    les_points = engendre_points(nombre_points)
    green = [[], []]
    red = [[], []]
    for i in range(nombre_essais):
        point_sup = (random.random() * 3 - 1.5, random.random() * 3 - 1.5)
        reponse_obtenue = kNN_sur_Rd(les_points, point_sup, k)
        if reponse_obtenue:
            green[0].append(point_sup[0])
            green[1].append(point_sup[1])
        else:
            red[0].append(point_sup[0])
            red[1].append(point_sup[1])
    abscisses = [point[0][0] for point in les_points]
    ordonnees = [point[0][1] for point in les_points]
    angles = np.linspace(0, 2*np.pi, 1000)
    absc_cercle = np.cos(angles)
    ordo_cercle = np.sin(angles)
    plt.plot(absc_cercle, ordo_cercle, "b")
    plt.plot(abscisses, ordonnees, "k.")
    plt.plot(green[0], green[1], "gx")
    plt.plot(red[0], red[1], "rx")
    plt.show()

def kNNdessin(nombre_points, k):
    """Effectue un test de l'algorithme des k plus proches voisins
    pour des points pris dans le carré ]-1,5; 1,5[² avec pour étiquette
    l'appartenance ou non au disque délimité par le cercle trigonométrique.
    Le résultat apparaît dans une fenêtre graphique,
    en représentant en bleu le cercle trigonométrique."""
    kNNdessin_n_essais(nombre_points, 1, k)

# Exercice 8

def kNNphoto(lien, nombre_points, k):
    """Effectue un test de l'algorithme des k plus proches voisins
    pour des points pris sur une image binarisée avec pour étiquette
    le fait ou non qu'un pixel soit noir.
    L'image est accessible au lien fourni en premier argument.
    On engendre le nombre de points donné en arguments, en fusionnant
    d'éventuels des points égaux, sachant qu'un point est alors donné
    en tant que couple d'indices dans l'image.
    Le résultat apparaît dans une fenêtre graphique,
    avec les pixels retenus en bleu."""
    img = plt.imread(lien)
    nbl, nbc = img.shape[:2]
    les_points_dict = {}
    for i in range(nombre_points):
        l = random.randint(0, nbl-1)
        c = random.randint(0, nbc-1)
        if (l, c) not in les_points_dict:
            les_points_dict[(l, c)] = (img[l, c, 0] == 0) # même binarisée, cela reste une image donc la dimension de l'objet est 3
    les_points = []
    for point in les_points_dict:
        les_points.append((point, les_points_dict[point]))
    point_sup = (random.randint(0, nbl-1), random.randint(0, nbc-1))
    while point_sup in les_points_dict:
        point_sup = (random.randint(0, nbl-1), random.randint(0, nbc-1))
    reponse_obtenue = kNN_sur_Rd(les_points, point_sup, k)
    if reponse_obtenue:
        coul = "g"
    else:
        coul = "r"
    abscisses = [point[0][1] for point in les_points]
    ordonnees = [point[0][0] for point in les_points]
    plt.imshow(img)
    plt.plot(abscisses, ordonnees, "b.")
    plt.plot([point_sup[1]], [point_sup[0]], coul + "x")
    plt.show()

# Exercice 9

def point_aleatoire(point, rayon):
    """Engendre un point du plan aléatoire
    dans un disque de centre et rayon précisés."""
    theta = random.random() * 2 * np.pi
    r = random.random() * rayon
    return (point[0] + r * np.cos(theta), point[1] + r * np.sin(theta))

def nuage_points(points, taille, rayon):
    """Crée un nuage de points du plan, de taille donnée en arguments,
    tous les points étant à une distance inférieure au rayon précisé
    d'un des points de référence. On renverra une liste par point de référence."""
    n = len(points)
    nuage = [[point_aleatoire(point, rayon)] for point in points] # au moins un par point
    for i in range(taille-n):
        indice = random.randint(0, n-1)
        nuage[indice].append(point_aleatoire(points[indice], rayon))
    return nuage

# Exercice 10

def kmeans_nuage(nuage):
    """Applique l'algorithme des k-moyennes à un nuage de points
    donné en tant que liste de listes de points.
    Le résultat est également représenté sur un graphique
    avec une couleur par groupement créé en raison du paramétrage de plot."""
    points = []
    for zone in nuage:
        points.extend(zone)
    rep = kmeans(points, len(nuage))
    for groupe in rep:
        abscisses = [point[0] for point in groupe]
        ordonnees = [point[1] for point in groupe]
        plt.plot(abscisses, ordonnees, "x")
    plt.show()
    return rep

# Exercice 11

def erreur_kmeans_nuage(points, taille, rayon):
    """Engendre un nuage de points, applique l'algorithme des k-moyennes dessus
    et compte le nombre de points mal placés dans un groupement.
    L'ordre des groupements n'étant pas garanti, il faut y prendre garde."""
    nuage = nuage_points(points, taille, rayon)
    nuage_ensembles = [set(zone) for zone in nuage]
    resultat = kmeans_nuage(nuage)
    erreurs = 0
    for groupe in resultat:
        erreur_mini = taille # initialisation simple
        groupe_ens = set(groupe)
        for ensemble in nuage_ensembles:
            erreur_possible = len(A.difference(B))
            if erreur_possible < erreur_mini:
                erreur_mini = erreur_possible
        erreurs += erreur_mini # en pratique il est possible que l'erreur concerne le même ensemble pour deux groupes
    return erreurs

# Exercice 12

def kmeans_sans_k(nuage, kmax):
    """Applique l'algorithme des k-moyennes sans fournir la valeur de k,
    remplacée par un seuil de la valeur de k à tester.
    La valeur minimisant la variance totale sera alors retenue."""
    points = []
    for zone in nuage:
        points.extend(zone)
    rep, variance = kmeans(points, 1, renvoyer_variance=True)
    for i in range(2, kmax+1):
        rep2, variance2 = kmeans(points, i, renvoyer_variance=True)
        if variance2 < variance:
            rep = rep2
            variance = variance2
    for groupe in rep:
        abscisses = [point[0] for point in groupe]
        ordonnees = [point[1] for point in groupe]
        plt.plot(abscisses, ordonnees, "X")
    plt.show()
    return rep