import random

def mélanger(cases,n):
    """ paramètres :
          o cases : liste de listes de int ; les listes des tuiles
          o n : int ; nombre de coups à appliquer
        La onction mélange cases en effectuant n coups aléatoires
        valeur renvoyée : liste nouvelle liste des tuiles
    """
    # 3 lignes pour copier cases dans res
    res = [[]]*len(cases)
    for i in range(len(res)):
        res[i] = [ x for x in cases[i]]
    # ensuite n coups aléatoires
    for _ in range(n):
        lc = candidats(res)
        res = échange_zéro(res, random.choice(lc))
    return (res)

def victoire(cases):
    """ Renvoir True si et seulement si les cases sont rangées dans l'ordre """
    return cases == gen_cases(len(cases),len(cases[0])) # on compare au plateau initial

def gen_cases (l,c):
    """ Génère une liste de listes de tuiles de l lignes et c colonnes """
    res = [[]]*l # une liste de listes vides
    for i in range(len(res)):# pour chaque ligne ...
        res[i] = [x for x in range (i*c,((i+1)*c))] # ... on crée une liste contenant les bons entiers consécutifs
    return res

def trouve_zéro(cases):
    """ renvoie les coordonnées (ligne,colonne) de 0 dans cases """
    for i in range (len(cases)):
        for j in range (len(cases[i])):
            if cases[i][j] == 0:   # dès qu'on trouve zéro on renvoie ses coordonnées
                return (i,j)
    # pas d'autre return : la foction est incorrecte si le plateau ne contient pas zéro
            
def échange_zéro(cases, arr):
    """ renvoie la liste des tuiles où on a échangé la tuile 0 avec la tuile de coordonnées arr : (int,int) """
    x,y = arr
    u,v = trouve_zéro(cases)
    res = gen_cases(len(cases),len(cases[0])) # pour initialiser une liste de listes de la bonne taille
    for i in range (len(cases)):
        for j in range (len(cases[x])):
            if (i,j) != (u,v) and (i,j) != (x,y) :  # si la case n'est ni zéro ni la case à éhanger, on copie sans rien faire
                res[i][j] = cases[i][j]
    res[u][v] = cases[x][y] # on remplace zéro par la nouvelle valeur
    res[x][y] = 0 # on remplace la nouvelle valeur par zéro
    return res

def candidats(cases):
    """ renvoie la liste des doublets de coordonnées de tuiles que l'on peut dépacer sur le 0 """
    res = []
    x,y=trouve_zéro(cases)
    for i in range (len(cases)):
        for j in range (len(cases[i])):
            if (abs(x-i)+abs(y-j))==1: # un peu de maths
                res = res +  [(i,j)]
    return res

if __name__ == '__main__':
    """ divers tests qui sont effectués si le module n'est pas utilisé dans un autre programme """
    pass