######################################
# GESTION DES LABYRINTHES
######################################

def dessinerTableau(tab):
    """
    permet de dessiner le labyrinthe passe en parametre
    - les cases avec un 1 sont des murs => '#'
    - les cases avec un 0 sont des espaces vides => ' '
    """

    for j in range(0,len(tab[0])):
        for i in range(0,len(tab)):
            if (tab[i][j]==1):
                print('#', end=' ')
            else:
                print(' ', end=' ')
        print()

###################

def transpose(laby):
    """
    permet d'inverser lignes et colonnes d'un labyrinthe
    (utile pour la creation simple)
    """
    # nouveau laby
    laby2=[]
    for i in range(0,len(laby[0])):
        ligne=[]
        for j in range(0,len(laby)):
            ligne+=[0]
        laby2+=[ligne]

    # transposition
    for i in range(0,len(laby[0])):
        for j in range(0,len(laby)):
            laby2[i][j]=laby[j][i]

    return laby2


###################

def getLabyrintheDefaut():
    """
    construit et retourne un labyrinthe par defaut a parcourir
    (de taille 8x8)
    """

    # labyrinthe vide
    laby = []
    laby +=[[1,1,1,1,1,1,1,1]]
    laby +=[[1,0,0,1,0,0,0,1]]
    laby +=[[1,0,0,1,0,1,0,1]]
    laby +=[[1,0,1,1,1,1,0,1]]
    laby +=[[1,0,0,0,0,0,0,1]]
    laby +=[[1,1,0,1,1,0,1,1]]
    laby +=[[1,0,0,0,0,0,0,1]]
    laby +=[[1,1,1,1,1,1,1,1]]

    # nouveau laby
    return transpose(laby)

def getDepartDefaut():
    return (4,6)


###################

def getLabyrintheMoyen():
    """
    construit et retourne un labyrinthe par defaut
    (de taille 10x10)
    """
    laby = []
    laby +=[[1,1,1,1,1,1,1,1,1,1]]
    laby +=[[1,0,0,0,0,0,0,0,0,1]]
    laby +=[[1,1,0,1,1,0,1,1,0,1]]
    laby +=[[1,0,0,0,0,0,0,0,0,1]]
    laby +=[[1,0,1,0,0,1,0,1,0,1]]
    laby +=[[1,0,1,0,1,1,0,1,0,1]]
    laby +=[[1,0,0,0,0,0,0,0,0,1]]
    laby +=[[1,0,1,1,0,1,1,0,1,1]]
    laby +=[[1,0,0,0,0,0,0,0,0,1]]
    laby +=[[1,1,1,1,1,1,1,1,1,1]]

    # nouveau laby
    return transpose(laby)

def getDepartMoyen():
    return (6,8)

###################

def getLabyrintheGrand():
    """
    construit et retourne un labyrinthe par defaut a parcourir
    (de taille 15x15)
    """
    laby = []
    laby +=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
    laby +=[[1,0,0,0,0,0,0,0,0,0,1,0,0,0,1]]
    laby +=[[1,0,1,1,1,1,1,0,1,0,1,0,1,1,1]]
    laby +=[[1,0,0,1,0,1,0,0,1,0,1,0,0,0,1]]
    laby +=[[1,0,0,0,0,0,0,0,1,0,0,0,1,0,1]]
    laby +=[[1,1,0,1,1,0,1,0,1,1,0,1,1,0,1]]
    laby +=[[1,0,0,0,0,0,1,0,0,0,0,1,0,0,1]]
    laby +=[[1,0,1,1,1,1,1,1,1,1,1,1,1,0,1]]
    laby +=[[1,0,1,0,0,1,0,0,0,0,0,0,1,0,1]]
    laby +=[[1,0,1,0,0,0,0,1,1,1,1,0,1,0,1]]
    laby +=[[1,0,1,0,0,1,0,1,0,0,0,0,1,0,1]]
    laby +=[[1,0,1,0,0,1,0,1,0,0,0,0,1,0,1]]
    laby +=[[1,0,1,1,0,1,1,1,1,1,1,1,1,0,1]]
    laby +=[[1,0,0,0,0,0,0,0,0,0,0,0,0,0,1]]
    laby +=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]

    # nouveau laby
    return transpose(laby)

def getDepartGrand():
    return (9,13)

###################

def getLabyrintheTresGrand():
    """
    construit et retourne un labyrinthe par defaut a parcourir
    (de taille 13x18)
    """
    laby = []
    laby +=[[1,1,1,1,1,1,1,1,1,1,1,1,1]]
    laby +=[[1,0,0,0,1,0,0,0,0,0,0,0,1]]
    laby +=[[1,1,1,0,1,0,1,1,0,1,1,0,1]]
    laby +=[[1,0,0,0,0,0,0,0,0,0,0,0,1]]
    laby +=[[1,0,1,0,0,1,0,1,0,0,1,0,1]]
    laby +=[[1,0,1,0,1,1,0,1,0,1,1,0,1]]
    laby +=[[1,0,0,0,0,1,0,0,0,1,0,0,1]]
    laby +=[[1,0,1,1,0,1,1,0,1,1,1,0,1]]
    laby +=[[1,0,0,0,0,0,1,0,0,0,0,0,1]]
    laby +=[[1,1,0,1,1,0,1,1,0,1,1,0,1]]
    laby +=[[1,0,0,1,0,0,0,0,0,1,0,0,1]]
    laby +=[[1,0,1,1,1,1,1,1,1,1,1,0,1]]
    laby +=[[1,0,0,0,0,0,0,0,0,0,0,0,1]]
    laby +=[[1,1,1,0,1,1,1,1,1,1,1,0,1]]
    laby +=[[1,0,0,0,0,0,0,0,0,0,0,0,1]]
    laby +=[[1,0,1,1,1,1,1,0,1,1,0,1,1]]
    laby +=[[1,0,0,0,0,0,0,0,0,0,0,0,1]]
    laby +=[[1,1,1,1,1,1,1,1,1,1,1,1,1]]

    # nouveau laby
    return transpose(laby)

def getDepartTresGrand():
    return (6,16)

###################

def getLabyrinthe(nom):
    """
    donne un labyrinthe en fonction du nom passe en parametre
    """
    # laby par defaut
    if nom == "default" or nom == "Default" :
        return getLabyrintheDefaut()

    if nom == "moyen" or nom == "Moyen" :
        return getLabyrintheMoyen()

    if nom == "grand" or nom == "Grand" :
        return getLabyrintheGrand()

    if nom == "tresgrand" or nom == "tresGrand" or nom == "TresGrand" :
        return getLabyrintheTresGrand()

    print ("**ERROR** Labyrinthe inexistant => par defaut")
    return getLabyrintheDefaut()

def getDepart(nom):
    """
    donne le depart du labyrinthe
    """
    # laby par defaut
    if nom == "default" or nom == "Default" :
        return getDepartDefaut()

    if nom == "moyen" or nom == "Moyen" :
        return getDepartMoyen()

    if nom == "grand" or nom == "Grand" :
        return getDepartGrand()

    if nom == "tresgrand" or nom == "tresGrand" or nom == "TresGrand" :
        return getDepartTresGrand()

    print ("**ERROR** Labyrinthe inexistant => par defaut")
    return getDepartDefaut()


######################################
# CALCUL DES DISTANCES AVEC PARCOURS TABLEAU
# en raisonnant sur les voisins
######################################


def calculLaby_voisin(laby,x,y):
    """
    effectue le calcul des distances en parcourant le tableau
    - strategie consiste à chercher les cases qui ont un voisin interessant
    """
    # faire un nouveau tableau avec 10000
    max = 1000
    tab=[]
    for i in range(len(laby)):
        t=[]
        for j in range(len(laby[0])) :
            t+=[max]
        tab+=[t]
    tab[x][y]=0

    # tant que non fini
    fini = False
    indice = 0

    while (not fini) :
        # remet fini a vrai
        fini = True

        for i in range(len(laby)):
            for j in range(len(laby[0])):
                # si pas mur
                # si pas tagguee
                if (laby[i][j]!=1) and (tab[i][j]==max) :
                    # si proche d'une case taggue de valeur n
                    if (tab[i-1][j]==indice) or (tab[i+1][j]==indice) or (tab[i][j-1]==indice) or (tab[i][j+1]==indice) :
                        # case est de valeur n+1
                        tab[i][j] = indice + 1
                        # fini = false
                        fini = False
        # decale indice
        indice = indice  +1
        dessinerChemin(tab)

    # fin : retourne le tableau
    return tab

######################################
# CALCUL DES DISTANCES AVEC PARCOURS TABLEAU
######################################


def calculLaby(laby,x,y):
    """
    effectue le calcul des distances en parcourant le tableau
    - strategie consiste à chercher les cases tagguees au bon indice et a modifier leur voisin
    """
    # faire un nouveau tableau avec 10000
    max = 1000
    tab=[]
    for i in range(len(laby)):
        t=[]
        for j in range(len(laby[0])) :
            t+=[max]
        tab+=[t]
    tab[x][y]=0

    # voisins connexite 4
    voisins=[[0,1],[0,-1],[1,0],[-1,0]]

    # voisins connexite 8
    voisins=[[0,1],[0,-1],[1,0],[-1,0],[-1,-1],[-1,1],[1,1],[1,-1]]

    # tant que non fini
    fini = False
    indice = 0

    while (not fini) :
        # remet fini a vrai
        fini = True

        for i in range(len(laby)):
            for j in range(len(laby[0])):
                # si case est taggue avec le bon indice
                if tab[i][j]==indice:
                    # pour chaque voisin
                    for v in voisins:
                        # coordonnes du voisin
                        voisinX=i+v[0]
                        voisinY=j+v[1]
                        # si case est pas un mur
                        # si elle est pas taggue
                        if laby[voisinX][voisinY]!=1 and tab[voisinX][voisinY]==max :
                            # tague
                            tab[voisinX][voisinY] = indice +1
                            # fini est faux
                            fini = False
        # decale indice
        indice = indice  +1
        dessinerChemin(tab)

    # fin : retourne le tableau
    return tab


######################################
# AVEC LISTE OUVERTE
######################################

def calculLabyRapide(laby,x,y):
    """
    effectue le calcul des distances en utilisant une liste ouverte
    - strategie consiste à propager case par case
    - derecursivation appel recursif de propagation (prog dynamique)
    """

    # faire un nouveau tableau avec 10000
    max = 1000
    tab=[]
    for i in range(len(laby)):
        t=[]
        for j in range(len(laby[0])) :
            t+=[max]
        tab+=[t]
    tab[x][y]=0

    # voisins connexite 4
    voisins=[[0,1],[0,-1],[1,0],[-1,0]]

    # ouverte : cases à parcourir
    ouverte = [(x,y)]

    # tant que non fini
    fini = False

    # tant qu'il reste des elements
    while len(ouverte)>0 :
        # get element
        # WARNING : pop(0) si on veut le fonctionnement d'une file
        #           sinon pop() prend en fin de liste
        (i,j) = ouverte.pop(0)
        # pour chaque voisin
        for v in voisins:
            # coordonnes du voisin
            voisinX=i+v[0]
            voisinY=j+v[1]
            # si case est pas un mur
            # si elle est pas taggue
            if laby[voisinX][voisinY]!=1 and tab[voisinX][voisinY]==max :
                # tague la case
                tab[voisinX][voisinY] = tab[i][j]+1
                # ajoute a la liste ouverte
                ouverte.append((voisinX,voisinY))

        # affiche la liste ouverte et le chemin parcouru à chaque iteration
        print(ouverte)
        dessinerChemin(tab)

    # fin retourner tableau
    return tab


######################################
# EN RECURSIF
######################################

def calculLabyRecursif(laby,x,y):
    """
    effectue un calcul de distance en recursif
    """
    # faire un nouveau tableau avec 10000
    max = 1000
    tab=[]
    for i in range(len(laby)):
        t=[]
        for j in range(len(laby[0])) :
            t+=[max]
        tab+=[t]

    # appel recursif propager
    propagerValeur(tab,laby,x,y,0)
    return tab


def propagerValeur(tab, laby, x, y, indice,max=1000,PRINT=True):
    """
    appel recursif pour propager la valeur
    - si deja une meilleure valeur, rien a faire
    - sinon, tagguer la case et repropager aux voisins
    """

    # si deja taggue plus petit
    if PRINT :
        print ("-> traite "+str(x)+","+str(y)+" valeur: "+str(indice), end=' ')

    if tab[x][y]<indice :
        # LOG
        if PRINT :
            print ("=> deja mieux "+str(tab[x][y]))
        # stop
        return

    if PRINT :
        if (tab[x][y] == max):
            print ("=> nouvelle case")
        else :
            print ("=> amelioration de "+str(tab[x][y]))

    # taggue case
    tab[x][y] = indice
    dessinerChemin(tab)

    # voisins
    voisins=[[0,1],[0,-1],[1,0],[-1,0]]

    # pour chaque voisin
    for v in voisins:
        # voisin
        vx=x+v[0]
        vy=y+v[1]

        # si voisin non mur
        if laby[vx][vy] != 1:
            # appel recursif
            propagerValeur(tab,laby,vx,vy,indice+1)

######################################
# AFFICHAGE DES DISTANCES
######################################

def dessinerChemin(tab):
    """
    permet de dessiner une matrice de distance dans un labyrinthe
    """
    # dessine les lignes
    for j in range(0,len(tab[0])):

        # pour chaque colonnee
        for i in range(0,len(tab)):
            # recupere la valeur calculee
            val=tab[i][j]

            # si c'est 1000, c'est une case non visitee
            if val==1000:
                # affiche vide
                print("   ",end=' ')
            else:
                # affiche la valeur
                print(val,end=' ')
                # ajoute le bon nombre d'espaces en fonction de la taille du nombre
                if val<0:
                    val=-val*10
                if val==0:
                    val=1
                while (val<100):
                    val=val*10
                    print(' ',end='')
        print()

######################################
# CALCUL DU CHEMIN
######################################

def getChemin(distance,depX,depY):
    """
    retourne le chemin a partir d'une matrice de distance
    - depX : abscisse du depart
    - depY : ordoneee du depart
    """
    # valeur maximale
    maxVal=1000

    # on se place au depart
    x=depX
    y=depY
    chemin=[(x,y)]

    # liste des voisins connexite 4
    voisins = [(1,0),(-1,0),(0,1),(0,-1)]

    # tant que 0 est non atteint
    while not distance[x][y] == 0 :
        # cherche plus petite case chez les voisins
        min = maxVal
        voisinMin =()
        # pour chaque voisin
        for voisin in voisins :
            # calcule case voisine
            vx = x + voisin[0]
            vy = y + voisin[1]
            # si meilleure
            if distance[vx][vy] < min :
                min = distance[vx][vy]
                voisinMin = (vx,vy)

        # meilleureVoisin trouve remonte la case
        chemin.append(voisinMin)
        (x,y) = voisinMin

    # fin retourne chemin
    return chemin

######################################
# MAIN
######################################

def main(nameLaby):
    """
    code appele par le __main__
    creer et dessine un Labyrinthe
    """
    # creer un labyrinthe
    laby = getLabyrinthe(nameLaby)
    xDep,yDep = getDepart(nameLaby)

    # affiche le labyrinthe dans la console
    dessinerTableau(laby)

    # consytruire cases
    print("############# RAPIDE ##############")
    tab = calculLabyRapide(laby,1,1)

    # recursif
    print("############# RECURSIF ##############")
    tab = calculLabyRecursif(laby,1,1)

    # recupere chemin
    chemin = getChemin(tab,xDep,yDep)
    print (chemin)


######################################
# lancement du module python
######################################


import sys

if __name__ == "__main__":
    # labyrinthe a afficher
    nameLaby=""

    # si trop d'arguments, exit'
    if len(sys.argv) > 2 :
        print ("**ERROR** un seul argument max")
        print ("")
        print ("USAGE :")
        print ("'laby [name]'")
        print ("- avec name désignant le labyrinthe ('default' ou 'grand')")

    # si pas d'argument, labyrinthe defaut
    if len(sys.argv) == 1 :
        nameLaby = "default"
    # sinon arg 1 doit contenir le nom du labyrinthe
    else :
        nameLaby = sys.argv[1]

    main(nameLaby)