import numpy as np
from numpy.linalg import matrix_power

#vos fonctions ICI


#programme principal

M1 = np.array(
    [
    [0,1,1,0,0,0,0],
    [1,0,0,1,1,0,0],
    [1,0,0,1,0,1,0],
    [0,1,1,0,1,0,1],
    [0,1,0,1,0,0,1],
    [0,0,1,0,0,0,1],
    [0,0,0,1,1,1,0]
    ]
    )

M2 = np.array(
    [
    [0,1,1,0,0,0,0],
    [0,0,0,1,1,0,0],
    [0,0,0,1,0,1,0],
    [0,1,0,0,1,0,1],
    [0,0,0,0,0,0,0],
    [0,0,1,0,0,0,1],
    [0,0,0,1,1,0,1]
    ]
    )
#on pourrait simplement définir M1 et M2 comme des listes de listes, mais
#le passage par des np.array facilite le calcul de puissances de matrices

laby = {
    0:[1,10],1:[0,11],2:[3,12],3:[2,4],4:[3,5,14],
    5:[4,6],6:[5,7],7:[6,8],8:[7,9],9:[8,19],
    10:[0,20],11:[1,21],12:[13,2],13:[12,23],14:[4,15],
    15:[14,16],16:[15,26],17:[27],18:[19,28],19:[9,18],
    20:[10],21:[11,31],22:[23,32],23:[22,13],24:[25],
    25:[24,26],26:[25,16,36],27:[17,28],28:[27,38],29:[39],
    30:[31,40],31:[30,32],32:[31,33,22],33:[32,34],34:[35,44],
    35:[34],36:[37,26],37:[36,47],38:[39,28],39:[38,29],
    40:[41,30,50],41:[40,42],42:[41,52],43:[53],44:[34],
    45:[46,55],46:[45,47],47:[46,37],48:[49,58],49:[48,59],
    50:[51,60],51:[50,61],52:[42],53:[54,43],54:[53,55],
    55:[54,45],56:[66],57:[58,67],58:[57,48],59:[49,69],
    60:[50],61:[51,62],62:[61,63,72],63:[62,73],64:[65,74],
    65:[64,75],66:[56,76],67:[68,57,77],68:[67,78],69:[59,79],
    70:[71,80],71:[70,81],72:[62,82],73:[63,83],74:[64],
    75:[65,85],76:[66,86],77:[67,87],78:[68,88],79:[69,89],
    80:[70,90],81:[82,71],82:[81,72],83:[84,73],84:[83,94],
    85:[86,75,95],86:[85,76,96],87:[77],88:[78,98],89:[79,99],
    90:[91,80],91:[90,101],92:[93],93:[92,103],94:[95,84],
    95:[94,85,105],96:[97,86],97:[96,98],98:[97,88],99:[89,109],
    100:[110],101:[91,111],102:[103,112],103:[102,93],104:[105,114],
    105:[104,95],106:[107,116],107:[106,117],108:[109,118],109:[108,99],
    110:[111,100],111:[110,101],112:[113,102],113:[112,114],114:[113,115,104],
    115:[114,116],116:[115,106],117:[107],118:[119,108],119:[118]}
#dictionnaire d'adjacence du labyrinthe


def nombre_chemins(M,i,j,a):
    return matrix_power(M,a)[i,j]


def dic_adjacence(M,noms=False):
    if not(noms):
        d={}
        for i in range(len(M)):
            L=[]
            for j in range(len(M[i])):
                if M[i][j]==1:
                    L.append(j)
                d[i]=L
    else:
        d={}
        for i in range(len(M)):
            L=[]
            for j in range(len(M[i])):
                if M[i][j]==1:
                    L.append(chr(65+j))
                d[chr(i+65)]=L
    return d
            
            
        
def plus_court_chemin(D,départ,arrivée):
    #initialisation
    pères={}
    visités={}
    for x in D:
        pères[x]=None
        visités[x]=False
    attente=[]
    
    #début
    attente.append(départ)
    visités[départ]=True
    fini=False
    
    ## parcours
    while attente!= []  and fini==False:
        X=attente.pop(0)
        for v in D[X]:
            
            if not(visités[v]):
                attente.append(v)
                visités[v]=True
                pères[v]=X
            if v==arrivée:
                fini =True
    
        
    ## reconstitution chemins
    chemin =[]

    if fini:
        sommet =arrivée
        chemin.append(sommet)
        while pères[sommet]!=None:
            sommet=pères[sommet]
            chemin.append(sommet)
    
    
    chemin.reverse()    
    return chemin


# parcours en profondeur récursif


def parcours_prof(départ,arrivée,dico):
    resultats=[]
    def parcours_prof_rec(sommet_courant,dico,visités):
        if sommet_courant==arrivée:
            resultats.append(visités)
        else:
            for v in dico[sommet_courant]:
                if v not in visités:
                    parcours_prof_rec(v, dico, visités+[v])
    
    parcours_prof_rec(départ, dico, [])
    return resultats