from random import shuffle, choice

def en_grille(valeurs, n):
    assert len(valeurs) == n * n
    grille = [[0 for j in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            grille[i][j] = valeurs[i * n + j]
    return grille

def aplatir(grille):
    return [k for ligne in grille for k in ligne]

def compte_inversion(valeurs):
    total = 0
    for i in range(len(valeurs)):
        for j in range(len(valeurs)):
            if i < j and valeurs[i] > valeurs[j]:
                total += 1
    return total
# ou
# def compte_inversion(valeurs):
#     total = 0
#     for i in range(len(valeurs)):
#         for j in range(i + 1, len(valeurs)):
#             if valeurs[i] > valeurs[j]:
#                 total += 1
#     return total

assert compte_inversion([1, 2, 3, 4]) == 0
assert compte_inversion([2, 1, 4, 3]) == 2

def distance_tuile_vide(grille, n):
    num_tuile_vide = n * n
    for i in range(n):
        for j in range(n):
            if grille[i][j] == num_tuile_vide:
                return n - 1 - i + n - 1 - j

def est_resoluble(valeurs, n):
    grille = en_grille(valeurs, n)
    inv = compte_inversion(valeurs)
    dis = distance_tuile_vide(grille, n)
    return (inv + dis) % 2 == 0

def creer_graphe(n):
    graphe = {}
    for i in range(n * n):
        voisins = []
        if i % n > 0:
            voisins.append(i - 1)
        if i % n < n - 1:
            voisins.append(i + 1)
        if i // n > 0:
            voisins.append(i - n)
        if i // n < n - 1:
            voisins.append(i + n)
        voisins.sort()
        graphe[i] = voisins
    return graphe

graphe_3_3 = {
    0: [1, 3],
    1: [0, 2, 4],
    2: [1, 5],
    3: [0, 4, 6],
    4: [1, 3, 5, 7],
    5: [2, 4, 8],
    6: [3, 7],
    7: [4, 6, 8],
    8: [5, 7]
}

assert creer_graphe(3) == graphe_3_3

def melange_graphe(nb_dep, n, graphe):
    valeurs = [i + 1 for i in range(n * n)]  # liste aplatie rangée # erreur dans le sujet
    num_tuile_vide = n * n
    actuelle = num_tuile_vide - 1  # position de la tuile vide
    for k in range(nb_dep):
        prochaine = choice(graphe[actuelle])
        valeurs[actuelle] = valeurs[prochaine]
        valeurs[prochaine] = num_tuile_vide
        actuelle = prochaine
    return en_grille(valeurs, n)

rangee = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
melangee = [[14, 16, 15, 12], [5, 3, 7, 1], [2, 10, 9, 4], [15, 11, 6, 8]]
valeurs = [k for k in range(1, 17)]
# ou
# valeurs = [k + 1 for k in range(16)]

assert melangee[2][1] == 10
shuffle(valeurs)

# Question B.6
g6 = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 16, 15, 14]]

assert compte_inversion(aplatir(g6)) == 3
assert distance_tuile_vide(g6, 4) == 2, distance_tuile_vide(g6, 4)
assert not est_resoluble(aplatir(g6), 4)

# Question 11
assert creer_graphe(4)[9] == [5, 8, 10, 13]

# Question 12
assert est_resoluble(aplatir(melange_graphe(10, 3, graphe_3_3)), 3)