# Python versione: 3.***
# Laura GIROMETTI
# 0000791806
# Iscritto: 1 anno di Matematica
# email: laura.girometti@studio.unibo.it
import random
def stack():
    return []
def push(a,p):
    p.append(a)
    return p
def pop(p):
    if not(is_empty(p)):
        a=p[-1]
        del p[-1]
        return a
    return None
def is_empty(p):
    return len(p)==0
def top(p):
    if not(is_empty(p)):
        return p[-1]
    return None
def importafile(file):
    try:              #provo ad aprire il file
      F=open(file,'r')
    except:
      print('Importazione non riuscita')
      return
    linee=[]
    for line in F:      #elimino il ritorno a carrello
        linee.append(line.strip('\n'))
    maze=dict()
    for i in range(1,len(linee),2):   #costruisco un diz. che ad ogni cella fa corrispondere un diz. con presenza di muri e stato
        for j in range(1,len(linee[i]),2):
            maze[i-(i+1)//2,j-(j+1)//2]={'N':linee[i-1][j]=='*','E':linee[i][j+1]=='*','S':linee[i+1][j]=='*','O':linee[i][j-1]=='*','Stato':''}
    if not(benformato(maze)):
        print('Il labirinto non è ben formato')
        return None
    return maze
def benformato(L):
    if len(L)==0:
        return False
    r,c=righe_colonne(L)
    #controllo che L sia una matrice r*c
    if len(L)!=r*c:
        return False
    #controllo che siano presenti tutte le celle
    for i in range(r):
        for j in range(c):
            if (i,j) not in L:
                return False
    #controllo che siano definiti i muri e lo stato della cella
    for key in L:
        if len(L[key])!=5 or type(L[key]['Stato'])!=str:
            return False
        for p in 'NSEO':
            if type(L[key][p])!= bool:
                return False
    #controllo la coerenza dei muri tra celle adiacenti
    for i in range(1,r):
        for j in range(c-1):
           if not(L[i,j]['E']==L[i,j+1]['O']): #controllo muri orizzontali
              return False
           if not(L[i,j]['N']==L[i-1,j]['S']): #controllo muri verticali
              return False
    for i in range(1,r-1):  #controllo muri verticali ultima colonna
        if not(L[i,j]['N']==L[i-1,j]['S']):
            return False
    return True
def righe_colonne(L): #restituisce una tupla con il numero di righe e colonne
    if L=={}:
        return 0,0
    else:
        r,c=max(L.keys())
        return r+1,c+1
def muri(L,c): #se possibile,restituisce un dizionario con la presenza/assenza dei muri
    if c not in L:
        print('La cella non è presente nel labirinto')
        return dict()
    return dict(zip('NESO',(L[c]['N'],L[c]['E'],L[c]['S'],L[c]['O'])))
def uscite(L): #restituisce una lista con le uscite
    r,c=righe_colonne(L)
    l_uscite=[]
    for j in range(c):
        if not(L[0,j]['N']): #aggiungo le uscite nord
            l_uscite.append((0,j))
        if not(L[r-1,j]['S']):  #aggiungo le uscite sud
            l_uscite.append((r-1,j))
    for i in range(r):
        if not(L[i,0]['O']) and (i,0) not in l_uscite: #aggiungo le uscite ovest
            l_uscite.append((i,0))
        if not(L[i,c-1]['E']) and (i,c-1) not in l_uscite: #aggiungo le uscite est
            l_uscite.append((i,c-1))
    return l_uscite
def get_stato(L,c): #restituisce, se possibile, lo stato
    if c not in L:
        print('Cella non presente')
        return
    if type(L[c]['Stato'])==str:
        return L[c]['Stato']
    else:
        print('La cella non ha stato')
        return
def set_stato(L,c,s): #modifica,se possibile lo stato
    if c not in L:
        print('Cella non presente')
        return
    L[c]['Stato']=s
def stampa(L):
    if L=={}:
        print('Il labirinto è vuoto')
        return
    k=risolvi_alla_cieca(L,(0,0))
    r,c=righe_colonne(L)
    for i in range(r):
        for j in range(c):  #stampo la riga con gli eventuali muri a nord
            print('+',end='')
            if L[(i,j)]['N']:
                print('---',end='')
            else:
                print('   ',end='')
        print('+')
        for j in range(c):  #stampo la riga con gli eventuali muri a ovest
            if L[(i,j)]['O']:
                print('|',end='')
            else:
                print(' ',end='')
            if (i,j) in k: #stampo P sulle celle percorso da (0,0) all'uscita
                print(' P ',end='')
            else:
                print('   ',end='')
        if L[(i,c-1)]['E']: #stampo l'eventuale muro a est dell'ultima colonna
            print('|')
        else:
            print()
    for j in range(c): #stampo l'ultima riga mancante
        print('+',end='')
        if L[(r-1,j)]['S']:
                print('---',end='')
        else:
                print('   ',end='')
    print('+')
def collegate(L,c1,c2): #verifica che c1 e c2 siano collegate
    if c1 not in L or c2 not in L:
        print('Celle non presenti')
        return False
    if c2[0]==c1[0]:
        if c1[1]==c2[1]-1: #controllo adiacenza orizzontale
          return not(L[c1]['E'])
        if c1[1]==c2[1]+1:
          return not(L[c1]['O'])
    if c2[1]==c1[1]:
        if c1[0]==c2[0]-1: #controllo adiacenza verticale
          return not(L[c1]['S'])
        if c1[0]==c2[0]+1:
          return not(L[c1]['N'])
    print('Celle non adiacenti')
    return False
def adiacente(L): #restituisce un dizionario con le celle adiacenti ad ogni cella
    adiacenti=dict()
    for i,j in L:
          if not(L[i,j]['N']) and (i-1,j) in L: #se possibile,controlla l'adiacenza a nord
            adiacenti[i,j]=[(i-1,j)]
          if not(L[i,j]['E']) and (i,j+1) in L: #se possibile controlla l'adiacenza a est
            adiacenti[i,j]=adiacenti.get((i,j),[]) + [(i,j+1)]
          if not(L[i,j]['S']) and (i+1,j) in L: #se possibile, controlla l'adiacenza a sud
            adiacenti[i,j]=adiacenti.get((i,j),[])+[(i+1,j)]
          if not(L[i,j]['O']) and (i,j-1) in L: #se possibile, controlla l'adiacenza a ovest
            adiacenti[i,j]=adiacenti.get((i,j),[])+[(i,j-1)]
          if (i,j) not in adiacenti: #non ci sono celle adiacenti
            adiacenti[i,j]=[]
    return adiacenti

def perfetto(L): #verifica che il labirinto sia connesso e non contenga cicli
    if L=={}:
        return False
    S=push((0,0),stack()) #mettiamo sulla pila la prima cella
    adiacenti=adiacente(L)
    while not(is_empty(S)):
        x=pop(S)
        if L[x]['Stato']!='Visitato': #visita la cella x
            L[x]['Stato']='Visitato'
            for w in adiacenti[x]: #mette le celle adiacenti non visitate sulla pila
                if L[w]['Stato']!='Visitato':
                    push(w,S)
        else: #una cella già visitata è sulla pila(c'è un ciclo)
            return False
    for k in L: #verifico che tutte le celle siano state visitate(è connesso)
        if L[k]['Stato']!='Visitato':
            return False
    return True

def risolvi_alla_cieca(L,partenza): #restituisce il percorso dalla partenza all'uscita
    l_uscite=uscite(L)              #come lista di celle
    adiacenti=adiacente(L)
    percorso=[]
    S=stack()
    if partenza not in L:
        print('La cella non è presente')
        return
    push(partenza,S) #metto la partenza sulla pila
    while not(is_empty(S)):
        x=pop(S)
        if get_stato(L,x)!='Visitato': #visito la cella x
            set_stato(L,x,'Visitato')
            percorso.append(x) #la metto nel percorso
            if x in l_uscite: #ho trovato l'uscita
                i=1
                while i<len(percorso): #tolgo le celle non adiacenti nel percorso
                    while percorso[i-1] not in adiacenti[percorso[i]]:
                        del percorso[i-1]
                        i=i-1
                    i+=1
                return percorso
            for cella in adiacenti[x]: #metto sulla pila le celle adiacenti non visitate
                if L[cella]['Stato']!='Visitato':
                    push(cella,S)
    #da partenza non si raggiunge l'uscita
    return []

def aggiungi_uscita(L): #aggiunge un'uscita, se possibile
    r,c=righe_colonne(L)
    celle_bordo=[]
    l_uscite=uscite(L)
    for j in range(c):
        if L[0,j]['N'] and (0,j) not in l_uscite: #aggiungo le celle del bordo con muro a nord
            celle_bordo.append([(0,j),'N'])
        if L[r-1,j]['S'] and (r-1,j) not in l_uscite: #aggiungo le celle del bordo con muro a sud
            celle_bordo.append([(r-1,j),'S'])
    for i in range(r):
        if L[i,0]['O'] and (i,0) not in l_uscite: #aggiungo le celle del bordo con muro a ovest
            celle_bordo.append([(i,0),'O'])
        if L[i,c-1]['E'] and (i,c-1) not in l_uscite: #aggiungo le celle del bordo con muro a est
            celle_bordo.append([(i,c-1),'E'])
    #scelgo la cella e il muro da abbattere
    if celle_bordo!=[]:
       scelta=random.choice(celle_bordo)
       L[scelta[0]][scelta[1]]=False
    else:
        print('Non è possibile aggiungere uscite')
def trova_percorso(L,c1,c2):
    adiacenti=adiacente(L)
    percorso=[]
    S=stack()
    if c1 not in L or c2 not in L:
        print('Una delle celle non è presente')
        return
    push(c1,S) #metto la partenza sulla pila
    while not(is_empty(S)):
        x=pop(S)
        if get_stato(L,x)!='Visitato': #visito la cella x
            set_stato(L,x,'Visitato')
            percorso.append(x) #la metto nel percorso
            if x==c2: #ho trovato l'uscita
                i=1
                while i<len(percorso): #tolgo le celle non adiacenti nel percorso
                    while percorso[i-1] not in adiacenti[percorso[i]]:
                        del percorso[i-1]
                        i=i-1
                    i+=1
                return percorso
            for cella in adiacenti[x]: #metto sulla pila le celle adiacenti non visitate
                if get_stato(L,cella)!='Visitato':
                    push(cella,S)