import sys
import numpy as np

# from fonctions_de_test import batterie_tests

def pretty_print(n):
    s = str(n)
    m = len(s) // 3
    k = len(s) % 3
    r = ""
    for i in range(m-1,-1,-1):
        r = s[k+3*i:k+3*(i+1)] + ' ' + r
    if k != 0:
        r = s[:k] + ' ' + r
    return r
    

if len(sys.argv) >= 2:
    u0 = int(sys.argv[1])
else:
    u0 = 42

print("u0 = ", u0)
print()

"""
Une position du jeu de taquin sera représentée par une matrice 3x3 codée
sous forme d'une liste de 3 listes (une liste par ligne).
"""

"""
Les deux fonctions ci-dessous servent à afficher joliment
une position du jeu de taquin. print_ligne est une fonction
auxilaire pour print_taquin. print_taquin est la fonction
à utiliser.
"""

def print_ligne(a, b, c):
    l = ""
    l += u'\u2551 ' + (str(a) if a != 0 else '*') + ' '
    l += u'\u2551 ' + (str(b) if b != 0 else '*') + ' '
    l += u'\u2551 ' + (str(c) if c != 0 else '*') + ' '
    l += u'\u2551'
    print(l)

"""
Cette fonction prend en arguments une position de jeu de taquin
et l'affiche joliment à l'écran.
"""
def print_taquin(t):
    bord_haut = u'\u2554' + (u'\u2550' * 3 + u'\u2566') * 2 + u'\u2550' * 3 + u'\u2557'
    bord_bas = u'\u255A' + (u'\u2550' * 3 + u'\u2569') * 2 + u'\u2550' * 3 + u'\u255D'
    bord_int = u'\u2560' + (u'\u2550' * 3 + u'\u256C') * 2 + u'\u2550' * 3 + u'\u2563'
    print(bord_haut)
    print_ligne(t[0][0], t[0][1], t[0][2])
    print(bord_int)
    print_ligne(t[1][0], t[1][1], t[1][2])
    print(bord_int)
    print_ligne(t[2][0], t[2][1], t[2][2])
    print(bord_bas)


""" QUESTION 1 """
def taquin_résolu():
    return [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

""" QUESTION 2 """
def place_vide(t):
    for i in range(3):
        for j in range(3):
            if t[i][j] == 0:
                return (i, j)
    return None # ce cas n'est pas censé arrivé sur une grille de taquin valide...

""" QUESTION 3 """

"""
Tente de réaliser un déplacement dans le jeu de taquin.
La direction donnée est la direction prise par la tuile
qui se déplace. La fonction retourne 0 si le déplacement
est possible et 1 sinon. Si le déplacement est possible
le taquin est modifié en conséquence sinon il n'est pas
changé.
"""
def déplacement(taquin, direction):
    assert direction in ['N', 'E', 'S', 'W']
    p = place_vide(taquin)
    assert p is not None
    (i, j) = p
    if direction == 'N' and i != 2:
        taquin[i][j] = taquin[i+1][j]
        taquin[i+1][j] = 0
        return 1
    elif direction == 'E' and j != 0:
        taquin[i][j] = taquin[i][j-1]
        taquin[i][j-1] = 0
        return 1
    elif direction == 'S' and i != 0:
        taquin[i][j] = taquin[i-1][j]
        taquin[i-1][j] = 0
        return 1
    elif direction == 'W' and j != 2:
        taquin[i][j] = taquin[i][j+1]
        taquin[i][j+1] = 0
        return 1
    else:
        return 0

""" QUESTION 4 """
u = np.zeros(100000, dtype = "int")
u[0] = u0
K = 2**30 - 3
for n in range(1, 100000):
    u[n] = (u[n-1] * 1022) % K

print("QUESTION 4")
print("a/ ", pretty_print(u[10]))
print("b/ ", pretty_print(u[500]))
print("c/ ", pretty_print(u[10000]))
print()

""" QUESTION 5 """
def D(k, l):
    res = []
    for i in range(l):
        if u[i + k] % 4 == 0:
            res.append('N')
        elif u[i + k] % 4 == 1:
            res.append('E')
        elif u[i + k] % 4 == 2:
            res.append('S')
        else:
            res.append('W')
    return res

print("QUESTION 5")
print("a/ ", ''.join(D(0, 5)))
print("b/ ", ''.join(D(50, 5)))
print("c/ ", ''.join(D(140, 5)))
print()

""" QUESTION 6 """
def déplacement_liste(taquin, l):
    n = len(l)
    déplacements = 0
    for k in range(n):
        déplacements += déplacement(taquin, l[k])
    return déplacements

print("QUESTION 6")
print("a/ ", déplacement_liste(taquin_résolu(), D(50, 1000)))
print("b/ ", déplacement_liste(taquin_résolu(), D(3500, 1000)))
print("c/ ", déplacement_liste(taquin_résolu(), D(7100, 1000)))
print()

""" QUESTION 7 """
def T(k):
    taquin = taquin_résolu()
    déplacement_liste(taquin, D(k, 1000))
    return taquin

print("QUESTION 7")
print("a/")
print_taquin(T(700))
t = T(50)
print("b/ ", t[0][0] + t[0][1] + t[0][2])
print("c/ ", place_vide(T(200)))
print()

""" QUESTION 8 """

"""
Cettte fonction prend une position de taquin et retourne
un entier unique qui code cette position.
"""
def configuration(taquin):
    c = 0
    puissance = 1
    for i in range(3):
        for j in range(3):
            c += taquin[i][j] * puissance
            puissance = puissance * 10
    return c

print("QUESTION 8")
print("a/ ", pretty_print(configuration(taquin_résolu())))
print("b/ ", pretty_print(configuration(T(50))))
print("c/ ", pretty_print(configuration(T(200))))
print()

"""
Cette fonction est la réciproque de la fonction précédente.
Elle reconstruit une position de tauqin a partir de son
codage.
"""
def decode(configuration):
    res = [[0] * 3, [0] * 3, [0] * 3]
    reste = configuration
    for i in range(3):
        for j in range(3):
            res[i][j] = reste % 10
            reste = reste // 10
    return res

"""
Cette fonction prend en argument le numero d'une position de taquin et retourne
les numéros des positions voisines dans l'ordre N E S W.
"""
def voisins(c):
    v = []
    for d in ["N", "E", "S", "W"]:
            t = decode(c)
            e = déplacement(t, d)
            if e == 1: # Si le déplacement est possible
                v.append(configuration(t))
    return v

print("QUESTION 9")
print("a/ [", ', '.join(pretty_print(v) for v in voisins(configuration(taquin_résolu()))), ']')
print("b/ [", ', '.join(pretty_print(v) for v in voisins(configuration(T(50)))), ']')
print("c/ ", len(voisins(789120345)))
print()


# """ QUESTION 10 """

from collections import deque

def parcours_largeur(c0):
    c_résolu = configuration(taquin_résolu())
    file = deque() # Nouvelle file vide
    file.append(c0) # push
    précédent = {c0 : -1}
    while len(file) != 0:
        x = file.popleft() #pop
        for y in voisins(x):
            if not(y in précédent):
                file.append(y)
                précédent[y] = x
        if x == c_résolu:
            break
    return précédent

print("QUESTION 10")
p = parcours_largeur(configuration(T(50)))
print("a/ ", pretty_print(len(p)))
p = parcours_largeur(configuration(T(120)))
print("b/ ", pretty_print(len(p)))
print("c/ ", pretty_print(p[configuration(taquin_résolu())]))
print()

""" QUESTION 11 """
def reconstruire_solution(c0, prec):
    sommet_final = configuration(taquin_résolu())
    sommet_depart = c0
    chemin = [sommet_final]
    sommet = sommet_final
    while (sommet != sommet_depart):
        sommet = prec[sommet]
        chemin.append(sommet)
    chemin.reverse()
    return chemin 

print("QUESTION 11")
c0 = configuration(T(50))
prec = parcours_largeur(c0)
chemin = reconstruire_solution(c0, prec)
print("a/ il faudra", len(chemin) - 1, "déplacements")
for c in chemin:
    print_taquin(decode(c))

c0 = configuration(T(120))
prec = parcours_largeur(c0)
chemin = reconstruire_solution(c0, prec)
print("b/ il faudra", len(chemin) - 1, "déplacements")
for c in chemin:
    print_taquin(decode(c))

c0 = configuration(T(100))
prec = parcours_largeur(c0)
chemin = reconstruire_solution(c0, prec)
print("c/ il faudra", len(chemin) - 1, "déplacements")

c0 = configuration(T(200))
prec = parcours_largeur(c0)
chemin = reconstruire_solution(c0, prec)
print("d/ il faudra", len(chemin) - 1, "déplacements")