## I.A.1)
# a)
def generer_PI(n, cmax):
    pts = []
    while(len(pts) != n):
        x = random.randrange(0, cmax)
        y = random.randrange(0, cmax)
        if [x, y] not in pts:
            pts.append([x, y])
    return np.array(pts)

# b)
"""
n <= cmax^2
n >= 0
cmax > 0
"""
## I.A.2)
def calculer_distances(PI):
    pts = []
    xr, yr = position_robot()
    n = len(PI)
    for i in range(n):
        pts.append([PI[i][0], PI[i][1]])
    pts.append([xr, yr])

    dst = np.zeros((n+1, n+1))
    for i in range(n+1):
        for j in range(n+1):
            dst[i, j] = math.sqrt( (pts[i][0] - pts[j][0])**2 + (pts[i][1] - pts[j][1])**2)
    return dst

## I.B.1)
"""
Répertorie le nombre de points dans la photo ayant chaque niveau d'intensité
n est le plus petit niveau d'intensité
b est le plus grand niveau d'intensité
h est un tableau de taille b-n+1 tel que h[i] est le nb de points
de la photo d'intensité n+i
"""
## I.B.2)
def selectionner_PI(photo, imin, imax):
    pts = []
    (n, m) = photo.shape
    for x in range(n):
        for y in range(m):
            if imin <= photo[x, y] <= imax:
                pts.append([x, y])
    return np.array(pts)


## II.A.1)
def longueur_chemin(chemin, d):
    n = len(d)-1
    longueur_tot = d[n, chemin[0]]
    for i in range(len(chemin)-1):
        longueur_tot += d[chemin[i], chemin[i+1]]
    return longueur_tot


## II.A.2)
def normaliser_chemin(chemin, n):
    copie = []
    vu = [False for i in range(n)]
    # vu[i] = True quand on a vu l'élément i
    for i in range(len(chemin)):
        if chemin[i] < n:
            if not vu[chemin[i]]:
                vu[chemin[i]] = i
                copie.append(chemin[i])
    for j in range(n):
        if not vu[j]:
            copie.append(j)
    return copie

## II.B.1)

"""
n choix pour le 1er point, n-1 pour le 2eme, n-2 pour le 3eme, etc..
au total, n! chemins possible
"""

## II.B.2)
"""
20! > 10^18. Même en traitant un chemin par nanoseconde, cela prendrait
10^9 secondes, soit environ 31 ans
"""

## II.C.1)

def plus_proche_voisin(d):
    n = len(d)-1
    L = [n]
    vu = [False for i in range(n)]
    for i in range(len(d)):
        # recherche de l'indice du plus proche
        # du dernier point (i.e. de L[-1]
        i_min = -1
        for j in range(len(d[i])):
            if (i_min == -1 or d[L[-1], j] < d[L[-1], i_min]) and not vu[j]:
                i_min = j
        L.append(i_min)
    return L[1:]

## II.C.2)
"""
plus_proche_voisin: O(n^2)

calculer_distance: O(n^2)
"""

## II.C.3)

"""
Le point (0, 4500) convient: l'algorithme du plus proche voisin
va choisir les points dans l'ordre (0, 3000), (0,0), (0,7000) pour
une longueur totale de 11500, alors que l'ordre (0, 7000), (0,3000), (0, 0)
donne une longueur totale de 9500
"""

## III.A)

def creer_population(m, d):
    p = [] # population
    n = len(d)-1
    for k in range(m):
        # générer un chemin aléatoire
        c = list(range(n))
        random.shuffle(c)
        p.append((longueur_chemin(c, d), c))

## III.B)

def reduire(p):
    p.sort()
    del p[len(p)//2:]

## III.C.1)

def muter_chemin(c):
    i = random.randrange(0, len(c))
    j = random.randrange(0, len(c))
    c[i], c[j] = c[j], c[i]

## III.C.2)
"""
Il ne faut pas oublier que les individus de la population
ne sont pas des chemins mais des couples (longueur, chemin)
"""
def muter_proba(p, proba, d):
    n = len(p)
    for i in range(n):
        if random.random() < proba: # s'exécute avec une probabilité proba
            (l, c) = p[i]
            muter_chemin(c)
            l = longueur_chemin(c, d)
            p[i] = (l, c)

## III.D.1)

def croiser(c1, c2):
    n = len(c1)
    c = c1[:n//2] + c2[n//2:]
    return c

def nouvelle_generation(p, d):
    n = len(p)
    for i in range(n):
        c = croiser(p[i], p[(i+1)%n])
        p.append((longueur_chemin(c, d), c))

## III.E.1)

def algo_genetique(PI, m, proba, g):
    d = calculer_distances(PI)
    p = creer_population(m, d)
    for k in range(g):
        reduire(p)
        nouvelle_generation(p, d)
        muter_proba(p, proba, d)
    p.sort()
    return p[0]

## III.E.2)

"""
Rien ne garantit que le croisement de deux chemins est meilleur
que les deux, ou que la mutation d'un chemin l'améliore nécessairement.
Ainsi, rien n'empêche de perdre en efficacité d'une génération à la
suivante, car avec une probabilité non nulle, tous les individus subissent
une mutation.
Pour éviter cela, on peut imaginer garder le ou les meilleurs individus
et les empêcher de muter.
"""

## III.E.3)
"""
On peut imaginer les conditions d'arrêt suivantes, en plus du nombre
de génération:
1) fixer limite de temps réel de calcul
2) s'arrêter dès que le meilleur individu d'une génération est
   trop proche du meilleur individu de la génération précédente
3) s'arrêter si l'on trouve une solution en dessous d'un certain seuil

La condition 1) illustre le fait que l'algorithme étudié
servira pour un robot devant faire des analyses: le temps réservé au
calcul doit être acceptable du point de vue de la mission du robot.

La condition 2) permet de s'arrêter lorsque l'algorithme semble stagner,
ce qui peut rentabiliser le temps de calcul, qui sera alors utilisé pour
trouver une solution acceptable mais pas pour optimiser cette solution
dans les détails. Cette condition pourrait permettre de calculer
plus d'itinéraires, mais qui risqueraient d'être de qualité légèrement
inférieure

La condition 3) pourrait être utilisée si l'on dispose de certaines limites
physiques contraignant le robot. Par exemple, si celui-ci ne peut pas parcourir
plus de X kilomètres sans revenir à sa base, il est inutile de calculer des
chemins de plus de X kilomètres.
"""