# DS 2 MPII 07/05/26

import numpy as np
import matplotlib.pyplot as plt

# Données
points = {
    "M0": (2.5, 5),
    "M1": (1.5, 4),
    "M2": (4, 6),
    "M3": (1, 2),
    "M4": (5, 2.6),
    "M5": (6.5, 4.5),
    "M6": (6, 2.3),
    "M7": (4.5, 7)}

# 1.	Approche exhaustive
# question 1- /1
bareme = {}
bareme['Q1']=1
coords_x = [x for (x, y) in points.values()]
coords_y = [y for (x, y) in points.values()]

# question 2- /2 import 0.5, fct 1.5
bareme['Q2']=2
from numpy import sqrt
def distance(i,j): # à partir des listes
    return sqrt((coords_x[j]-coords_x[i])**2+(coords_y[j]-coords_y[i])**2)

def distance_dict(i,j): # à partie du dictionnaire
    (xi,yi) = points['M'+str(i)]
    (xj,yj) = points['M'+str(j)]
    return sqrt((xj-xi)**2+(yj-yi)**2)

# question 3- /3 init/0.25*2 boucle i/1 boucle j/1 min/0.5
bareme['Q3']=3

def plus_proche():
    dmin = float('inf')
    couple = (0,0)
    for i in range(len(coords_x)):
        for j in range(len(coords_x)):
            if i != j and distance(i,j) < dmin:
                dmin = distance(i,j)
                couple = (i,j)
    return couple

# question 4- /1
bareme['Q4']=1

# on 2 boucles inbriquées parcourues n fois O(n^2)

#2.	Quelques outils pour s’améliorer
def tri(liste):
    n = len(liste)
    for i in range(n):
        pos = i
        while pos > 0 and liste[pos] < liste[pos-1]:
            liste[pos], liste[pos-1] = liste[pos-1], liste[pos]
            pos -= 1
# question 5-/1: tri par insertion /0.5 principe/0.5
bareme['Q5']=1

# c'est un tri par insertion
# principe: on choisit "pos" à placer, on décale les autres éléments de la liste
# jusqu'à ce que "pos" soit à sa place.
# les elements de la liste avant i sont alors triés
# On parcourt et on recommence avec tous les elts de la liste qui deviennent les nouveaux "pos" à placer.

# question 6- /1: O(n^2)/0.5 demo/0.5
bareme['Q6']=1

# boucle for parcourue n fois, boucle while n-i fois
# d'où une complexité quadratique en O(n^2)

# question 7-/3.5:
bareme['Q7']=3.5

# Tri rapide script/2 : condition d'arrêt/0.5 pivot+init/0.5
# recursivité sur D et G/1 combinaison/0.5
# complexité au mieux O(n.log(n)) au pire O(n^2)/0.5*2
# principe:
# 1 choix pivot = 1er element de la liste
# 2 a gauche les plus petits, à droite les plus grand
# 3 on combine G pivot D
# 4 on réitére
def tri_rapide(liste):
    #condition d'arrêt
    if len(liste) ==0:
        return []
    pivot = liste[0]
    D = []
    G = []
    for i in range(1,len(liste)):
        if liste[i] <= pivot:
            G.append(liste[i])
        elif liste[i] > pivot:
            D.append(liste[i])
    return tri_rapide(G) + [pivot] + tri_rapide(D)

# question 8- /1
bareme['Q8']=1

# test sur les coordonneées: coords_x[liste_indice[pos]]
# à la place de la valeur de la liste liste[pos]
def tri_indice(liste_indice):
    n = len(liste_indice)
    for i in range(n):
        pos = i
        while pos > 0 and coords_x[liste_indice[pos]] < coords_x[liste_indice[pos-1]]:
            liste_indice[pos], liste_indice[pos-1] = liste_indice[pos-1], liste_indice[pos]
            pos -= 1

# question 9- /1: 0.5*2
bareme['Q9']=1

# liste_x = [3, 1, 0, 2, 7, 4, 6, 5]
# liste_y = [3, 6, 4, 1, 5, 0, 2, 7]
## non demandé
# pour vérif:
liste_x = [i for i in range(len(coords_x))] #init
tri_indice(liste_x)

def tri_indicey(liste_indice):
    n = len(liste_indice)
    for i in range(n):
        pos = i
        while pos > 0 and coords_y[liste_indice[pos]] < coords_y[liste_indice[pos-1]]:
            liste_indice[pos], liste_indice[pos-1] = liste_indice[pos-1], liste_indice[pos]
            pos -= 1
liste_y = [i for i in range(len(coords_y))] #init
tri_indicey(liste_y)
##

# question 10- /2.5: init/0.5 parcours i,j/0.5*2 test/0.5 return/0.5
bareme['Q10']=2.5

cluster_a = [liste_x, liste_y]
def sous_cluster(cl, x_min, x_max):
    ''' cl = [liste_x, liste_y] '''
    # on cherche imin tel que coords_x[imin]
    liste_xcl = cl[0]
    liste_ycl = cl[1]
    liste_xsscl = []
    liste_ysscl = []
    for i in liste_xcl:
        if coords_x[i] >= x_min and coords_x[i] <= x_max:
            liste_xsscl.append(i)
    for j in liste_ycl:
        if coords_x[j] >= x_min and coords_x[j] <= x_max:
            liste_ysscl.append(j)
    return [liste_xsscl, liste_ysscl]

# question 11-/1.5
bareme['Q11']=1.5

def mediane(cl):
    n = len(cl[0]) # nb de points
    return coords_x[cl[0][n//2]]

def mediane2(cl):
    n = len(cl[0]) # nb de points
    if n//2 != n/2: # n impair
       xmedian = coords_x[cl[0][n//2]]
    else: # n pair
       xmedian = (coords_x[cl[0][n//2]]+coords_x[cl[0][n//2-1]])/2
    return xmedian

# question 12- div pour Reg /1
bareme['Q12']=1

# Méthode du type Diviser pour Régner

# question 13- /1 : nom+complexité 2*0.5
bareme['Q13']=1

# les tri fusion ou tri rapide utilisent ce principe
# tri rapide de complexité O(n^2) au pire, O(nlog(n)) au mieux
# tri fusion de complexité O(nlog(n)) au pire/au mieux


# question 14- /1 choix xmin/xmax 0.5*2
bareme['Q14']=1

def gauche(cl):
    '''renvoie le cluster constitué de la moitié des points de cl situés
    le plus à gauche'''
    return sous_cluster(cl, -float('inf'), mediane(cl))




# question 15- /1 choix xmin/xmax 0.5*2
bareme['Q15']=1

def bande_centrale(cl, d0):
    xmin = mediane(cl) - d0
    xmax = mediane(cl) + d0
    return sous_cluster(cl,xmin, xmax)


## Non demandé
# fct fusion utile pour distance_minimale
def fusion (cl, d0):
    n = len(cl[0])
    d_min = d0
    for i in range(n):
        for j in range(1,8):
            if i+j < n and (i != j) and (distance(cl[1][i], cl[1][j]) < d_min):
                d_min = distance(cl[1][i],cl[1][j])
    return d_min

# fct droite utile pour distance_minimale
def droite(cl):
    '''renvoie le cluster constitué de la moitié des points de cl situés
    le plus à droite'''
    return sous_cluster(cl, mediane(cl), float('inf'))
##

# question 16-/3.5
bareme['Q16']=3.5

# cas 2 test et calcul 1 distance 0.25*2
# cas 3 test et calcul de 3 distances 0.25*4
# 2 commentaires 0.5*2

def distance_minimale(cl):
    n = len(cl[0])
    ## A COMPLETER lignes 3 à 11 Etape 1 Cas n=2 et n=3
    if n == 2: # conditon d'arrêt
        return distance(cl[0][0],cl[0][1])
    elif n == 3:
        dmin = distance(cl[0][0],cl[0][1])
        if distance(cl[0][0],cl[0][2]) < dmin:
            dmin = distance(cl[0][0],cl[0][2])
        elif distance(cl[0][1],cl[0][2]) < dmin:
            dmin = distance(cl[0][1],cl[0][2])
        return dmin
    else:

## Etape 2 et Etape 3
        # Etape 2: on sépare gauche(cl) et droite(cl)
        # Etape 3: calcul recursif
        d0 = distance_minimale(gauche(cl))
        dd = distance_minimale(droite(cl))
        if d0 > dd:
            dmin = dd
## Etape 4 et Etape 5
        # Etape 4: on etudie la bande centrale
        # Etape 5: on renvoie la distance min dans G, D ou bande centrale
        bande_c = bande_centrale(cl, dmin)
        return fusion(bande_c, dmin) # dmin, couple de points

# question 17- complexité
bareme['Q17']=1

# cas n=2, n=3 0(1)
# fusion O(n)
# appel récursif on divise la taille du cluster par 2 : 2*C(n/2)
# donc C(n) = 2C(n/2) + O(n)

# on pose n =2^k -> k = log2(n), O(n) = A.n : C(2^k) = 2C(2^k/2) + A.2^k

# appel   n = 2^k :       C(2^k)   = 2C(2^(k-1)) + A.2^k
# appel n/2 = 2^(k-1):  C(2^(k-1)) = 2C(2^(k-2)) + A.2^(k-1)  *2^1
# appel n/4 = 2^(k-2):  C(2^(k-2)) = 2C(2^(k-3)) + A.2^(k-2)  *2^2
# ...
# appel 4 = 2^2:          C(2^2)   = 2C(2^1)     + A.2^2      *2^(k-2)
# appel 2 = 2^1:          C(2^1)   = 2C(2^0)     + A          *2^(k-1)

# somme                   C(2^k)   = 2^k.C(1) + A.[2^k + 2^k +..+2^k]  (k * 2^k)
#                         C(2^k)   = 2^k.C(1) + A.k.2^k
#                           C(n)   = n.C(1)   + A.n.log2(n) = O(n.log2(n))
#                           C(n)   = O(n.log2(n)) ou O(n.log(n))


# bareme
total_points=np.sum(list(bareme.values()))
print(bareme,'total points=', total_points)

#### TRACES sujet
plt.close('all')
fig, ax = plt.subplots()

for label, (x, y) in points.items():
    ax.scatter(x, y, color="black")
    ax.text(x + 0.1, y + 0.1, label)

#ax.axvline(x=5.5, linestyle="--", color="black")

ax.set_xlim(0.5, 7.5)
ax.set_ylim(1, 8)
ax.set_aspect('equal')

# définir des ticks pour que la grille apparaisse
ax.set_xticks(np.arange(0, 8, 1))
ax.set_yticks(np.arange(0, 9, 1))

# activer la grille
ax.grid(True, linestyle=":", linewidth=0.7, alpha=0.7)

# cacher les labels MAIS garder les ticks
ax.tick_params(labelbottom=False, labelleft=False)

plt.show()