######################################
# 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
######################################

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


######################################
# 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 = calculLaby(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)