import random


## Exercice 1: Tri rapide
"""
Dans les commentaires de documentation, T[a..b]
signifie "le sous-tableau constitué des cases de T
entre a et b inclus". C'est ce que l'on noterait T[a:b+1]
en code Python.
"""


def partition(T, a, b):
    """
    Partitionne T[a..b] selon T[a]. Renvoie un indice k tel que:
    - T[k] contient l'ancienne valeur de T[a]
    - T[a..k-1] contient les éléments <= à T[k]
    - T[k+1..b] contient les éléments > T[k]
    """
    assert(a <= b)
    assert(0 <= a)
    assert(b < len(T))
    i = a + 1
    s = b
    while i <= s:
        if T[i] <= T[a]:
            i += 1
        else:
            T[i], T[s] = T[s], T[i]
            s -= 1
    T[a], T[i-1] = T[i-1], T[a]
    return i-1

"""
Q2)
s-i+1 est une quantité entière car a et b sont des entiers, et que
les seules opérations subies par i et s sont +1 et -1.
De plus, à chaque tour de boucle:
- soit s baisse de 1
- soit i augmente de 1
Dans tous les cas, s-i+1 baisse d'exactement 1 à chaque tour, et
en particulier est strictement décroissant.
Enfin, s-i+1 est positif, car par condition de boucle, s-i+1 >= 1 au début
de chaque passage, donc s-i+1 >= 0 en fin de passage.

Q3)
La valeur initiale de s-i+1 majore le nombre de tours de boucles total,
or cette valeur est b-(a+1)+1 = b-a. L'algorithme est en O(b-a).

Q4) Notons P(k) la propriété à montrer.
- Initialisation (k=0):
s_0 = b.
Donc, [|s_k+1, b|] est un intervalle vide: P(0) est trivialement vraie.

- Hérédité: Soit k entier quelconque tel que P(k).
  + Si T[i] <= T[a], alors s_(k+1) = s_k, et T_(k+1) = T_k,
    donc P(k+1) est vraie puisque P(k) l'est par HR.
  + Sinon, s_(k+1) = s_k - 1, et T_(k+1) est identique à T_k,
    mais les cases i_k et s_k ont été échangées.
    Or, T_k[i_k] > T[a], donc T_(k+1)[s_(k+1)] > T_(k+1)[a].
    Comme, de plus,  pour j dans [|s_k + 1, b|], T_k[j] > T_k[a] par HR,
    on en déduit que pour j dans [|s_(k+1) + 1, b|], T_(k+1)[j] > T_(k+1)[a],
    soit précisément P(k+1)

Q5)
On peut proposer l'invariant symétrique sur i:
    Pour j dans [|a+1, i_k-1|], T_k[j] <= T_k[a]
Cet invariant traduit que la partie gauche du tableau contient bien
les éléments inférieurs au pivot.

En supposant que l'on a montré ce second invariant, on peut en déduire
la correction de l'algorithme comme suit:
En sortie de boucle, i = s+1, donc les intervalles
[|a+1, i-1|] et [|s+1, b|] couvrent exactement tout [|a, b|].
Autrement dit, tous les éléments ont été mis dans une des deux parties.
De plus, la case T[i-1] est dans la partie des éléments inférieurs au pivot,
on peut bien l'échanger avec T[a] sans problème, cela positionne le pivot
exactement entre les deux parties, et son nouvel indice est i-1.
"""


def tri_rapide(T, a, b):
    """
    Trie T[a..b] dans l'ordre croissant.
    """
    n = len(T)
    if a >= b:
        return
    k = partition(T, a, b)
    tri_rapide(T, a, k-1)
    tri_rapide(T, k+1, b)

def est_trie(T):
    n = len(T)
    for i in range(n-1):
        if T[i] > T[i+1]:
            return False
    return True

def test_tri():
    L = [5, 3, 9, 2, 7, 5, 8, 3]
    tri_rapide(L, 0, 7)
    assert est_trie(L)



## Exercice 2: Marche aléatoire

G_0 = [
    [0, 1, 4, 4, 4, 4, 2],
    [6, 2, 2, 0, 4, 5, 2],
    [6, 3, 2, 2, 3, 5, 4],
    [6, 2, 4, 5, 1, 6, 5],
    [0, 5, 4, 6, 5, 5, 5],
    [0, 3, 3, 0, 0, 4, 4],
    [0, 1, 2, 0, 0, 3, 2]
]

def positions_valides(G, i, j):
    """
    Renvoie la liste des cases accessibles depuis G[i][j].
    """
    n = len(G)
    res = [(i, j)]
    for (ii, jj) in [(i, j+1), (i, j-1), (i+1, j), (i-1, j)]:
        if 0 <= ii and ii < n and 0 <= jj and jj < n:
            if abs(G[ii][jj] - G[i][j]) <= 1:
                res.append((ii, jj))
    return res

def chemin_valide(G, ch):
    """
    Renvoie un booléen indiquant si ch est une suite de cases
    valides dans G
    """
    p = len(ch)
    for k in range(p-1):
        (i, j) = ch[k]
        (ii, jj) = ch[k+1]
        if (ii, jj) not in positions_valides(G, i, j):
            return False
    return True

def tests_validite():
    P_2_6 = positions_valides(G_0, 2, 6)
    assert (2, 6) in P_2_6
    assert (3, 6) in P_2_6
    assert (2, 5) in P_2_6
    assert (1, 6) not in P_2_6
    assert (2, 7) not in P_2_6

    # chemin valide: 0, 1, 2, 2, 2, 3, 2
    ch = [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 1), (3, 1)]
    assert chemin_valide(G_0, ch)
    # chemin invalide: 0, 6, 2, 2, 2, 3, 2
    ch = [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (2, 1), (3, 1)]
    assert not chemin_valide(G_0, ch)

def regrouper(positions, g1, g2):
    """
    Fusionne les groupes g1 et g2 en un seul groupe g1_g2
    dans le dictionnaire positions
    Hypothèses:
    - g1, g2 sont des groupes valides distincts du dictionnaire positions
    - g1 et g2 sont à la même position
    """
    assert(g1 in positions)
    assert(g2 in positions)
    assert(g1 != g2)
    assert(positions[g1] == positions[g2])

    pos = positions[g1]
    print(f"Fusion de {g1} et {g2} en {pos}")
    nouveau_g = g1 + "_" + g2
    del positions[g1]
    del positions[g2]
    positions[nouveau_g] = pos


def trouver_fusion(positions):
    """
    Renvoie un couple (g1, g2) de groupes distincts
    dans positions, se trouvant sur la même case.
    Renvoie ("", "") si tous les groupes sont sur
    des positions différentes.
    """
    for g1 in positions:
        for g2 in positions:
            if g1 != g2 and positions[g1] == positions[g2]:
                return (g1, g2)
    return ("", "")


def regrouper_tous(positions):
    """
    Modifie positions, de façon à ce que tous les groupes
    se trouvant sur une même position soient fusionnés.
    En sortie, positions n'a que des groupes isolés.
    """
    g1, g2 = trouver_fusion(positions)
    while (g1, g2) != ("" , ""):
        regrouper(positions, g1, g2)
        g1, g2 = trouver_fusion(positions)

def deplacer_groupe(G, positions, g):
    """
    Déplace aléatoirement le groupe g du dictionnaire positions
    sur la grille G, sur une case valide.
    """
    assert(g in positions)

    (i, j) = positions[g]
    # toutes les positions candidates
    valides = positions_valides(G, i, j)
    # choix de la nouvelle position
    k = len(valides)
    c = random.randint(0, k-1)
    positions[g] = valides[c]

def simuler(G, positions):
    """
    Déplace aléatoirement les groupes de positions dans la grille G,
    en les regroupant lorsqu'ils se rencontrent.
    Renvoie le nombre d'étapes de simulation nécessaires pour qu'il
    n'y ait plus qu'un groupe.
    """
    k = 0
    while len(positions) > 1:
        for g in positions:
            deplacer_groupe(G, positions, g)
        regrouper_tous(positions)
        k += 1
    return k


def test_simulation():
    res = 0
    for i in range(1000):
        positions = {
            "Guillaume": (0, 0),
            "Adeline": (6, 0),
            "Olivier_Maxime": (3, 6),
        }
        res += simuler(G_0, positions)
    print(f"Nombre moyen d'étapes sur 1000 simulations: {res/1000}")