| Hosted by CoCalc | Download
Kernel: SageMath 8.7

Graphes et outils logiques Projet Python - Les labyrinthes

Jean ARBACHE - DL Math-Info Groupe A2

Questions n'ont pas été faits

B0(partielement fait) - B3 - B5'


*B0 -> J'ai réussi à extraire de laby les informations important (les endroits où dit s'il y a des mures ou non) dans la fonction 'decompress' et du coup j'ai enlevé tous les 0 et 1 qui se répetent toujours s'il y avait des mures ou non. Mais pour le decompresser il fait un erreur(Il y a des explicationsencore dans le code )

*B3 -> L'idée pour moi est clair mais j'ai preferé de faire autre fonction pour avancer

*B5' -> j'ai comris ce q'il fait mais j'ai pas eu le temps de coder je vais vous donner un exemple ,qui peut être vrai si j'ai bien compris, c'est toujours mieux que rien

le chemin: [(5, 9), (3, 9), (1, 9), (1, 7), (3, 7), (3, 5), (5, 5)] devient: [(5, 9), (1, 9), (1, 7), (3, 7), (3, 5), (5, 5)] parce que (5, 9), (3, 9), (1, 9) est un coridor donc le debut de coridor point vers la fin et pas besoin de pointer vers chaque tuile cela va être plus efficace quand le laby est plus grand le chemin: [(1, 1), (3, 1), (5, 1), (5, 3), (5, 5)] devient: [(1, 1), (5, 1), (5, 3), (5, 5)] parce que ( [(1, 1), (3, 1), (5, 1) est un coridor


Petite remarque:

Quand il y a une ameliartion demandée les fonctions écrites sont directements la versions ameliorées je n'ai pas gardé les anciennes, du coup il y aura pas deux fonctions une avant l'ameliartion et une après l'ameliartion il y aura juste la fonction ameliorée. Donc il y a une fonction affiche qui est déja ameliorée et une algorithme union-find qui est déja optimisée et une fonction résout qui resout les deux types de labyrinthe et quand c'est imparfait elle trouve le plus court chemin


Difficultés rencontrés

Juste le début j'ai pris plein du temps à comprendre ce qu'on doit faire et puis la fonction affiche amilioré m'a pris le plus de temps avec la fonction compress aussi

#pour l'affichage import sys write = sys.stdout.write
VARIABLES GLOBLAES
#Dimension de laby lrg=5 lr=5 ht=3
#Ensemble de laby pour aider a coder #une tuile l=[[1,1,1], [1,0,1], [1,1,1]] #laby de l'enoncé l2=[[1,1,1,1,1,1,1,1,1,1,1], [1,0,0,0,1,0,0,0,0,0,1], [1,1,1,0,1,0,1,1,1,0,1], [1,0,1,0,0,0,0,0,1,0,1], [1,0,1,1,1,1,1,0,1,1,1], [1,0,0,0,0,0,0,0,0,0,1], [1,1,1,1,1,0,1,1,1,1,1]] #laby n'importe quoi l3=[[1,1,1,1,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1,1,1,1]]
Fonction d'affichage ameliorer
def affiche(l2): for y in range(len(l2)): for x in range(len(l2[y])): if(((y%2)!=0) and ((x%2)!=0)): write(' ') elif(((y%2)==0) and ((x%2)==0)): if( (x-1)>0 and (x+2)<len(l2[y]) and ( (l2[y][x-1]==1) and ((l2[y][x+1]==1)) )): if( ( (y-1)>0 and l2[y-1][x]==1 ) or ( (y+2)<len(l2) and l2[y+1][x]==1 ) ): write('+') else: write('-') elif( (y-1)>0 and (y+2)<len(l2) and ( (l2[y-1][x]==1) and ((l2[y+1][x]==1)) ) ): if( ( (x-1)>0 and l2[y][x-1]==1 ) or ( (x+2)<len(l2[y]) and l2[y][x+1]==1 ) ): write('+') else: write('|') else: write('+') elif (((y%2)!=0) and ((x%2)==0)): if l2[y][x]==1: write('|') else: write(' ') elif (((y%2)==0) and ((x%2)!=0)): if l2[y][x]==1: write('--') else: write(' ') print('')
affiche(l2)
+-----+--------+ | | | +--+ + +--+ | | | | | | +-----+ +--+ | | +-----+ +-----+
Explication de compression

L'idée principale de compression c'est d'enlever tous les 0,1 qui sont répétés et qui ne donnent aucun renseginment partilculaires sur le labirainthes (par exemples les coins qui sont oujours des 1 et les milieu de chaque case 'les tuile' qui sont toujours 0)

fonction compress --> réussi elle retourne juste les informations sur les murs

fonction decompress --> pas réussi totalement

le but et de compresser le labyrinth et dans le fonction affiche le décompressé avant l'afficher


def compress(l2): l=[] for y in range(1,len(l2)-1): ll=[] for x in range(1,len(l2[y])-1): if( y%2==0 and x%2!=0) or (x%2==0 and y%2!=0): ll.append(l2[y][x]) l.append(ll) return l
compress(l2)
[[0, 1, 0, 0], [1, 0, 0, 1, 0], [1, 0, 0, 1], [0, 1, 1, 0, 1], [0, 0, 0, 0]]
def decompress(lc): ht= (len(lc)+1)/2 lr = max(len(lc[1]), len(lc[0])) l=[] for y in range( ( ht )*2 + 1 ): ll=[] for x in range( ( lr )*2 + 1 ): if(x==0 or y==0 or x==( lr )*2 or y==( ht )*2): #or ((y)%2==0 and x%2==0) ): ll.append(1) elif(x%2!=0 and y%2!=0): ll.append(0) else: ll.append(1) l.append(ll) for y in range(1, ( ht )*2): for x in range(1, ( lr )*2): if( y%2==0 and x%2!=0): l[x][y]=lc[int(y/2)][int(x/2)] if((x%2==0 and y%2!=0)): l[x][y]=lc[int(y/2)][int((x-2)/2)] return l
#cette fonction devrait afficher l2 l'orginal mais elle plante #decompress(compress(l2))
#transdormer la representation binaire à la linaire def encode(h,l,y,x): if((y*l+x<h*l) and y<h and x<l): return y*l+x else: return -1
#transdormer la representation lineare à la binaire def decode(h,l,v): x=v%l y=(v-v%l)/l if(x<0 or y<0 or x>=l and y>=h): return -1 return (y,x)
#teste de deux fonction encode & decode def testEn_De_Code(): for y in range(ht): for x in range(lrg): if (y,x) != decode(ht,lrg,encode(ht,lrg,y,x)) or encode(ht,lrg,y,x) ==-1: print("Erreur") print("Bon")
testEn_De_Code()
Bon
""AlGORITHME QUICK-FIND""

C'est le même principe de l'ameliartion Compression des chemins que vous avez proposé mais c'est son nom sur le refrence où je le trouver sur Internet (Algorithms, 4th Edition by Robert Sedgewick) http://www.albertstam.com/Algorithms.pdf

J'ai choisit cette amelioration pour ces raisons:
1- Cet Algo est plus adapté pour la fonction genere parce que le nombre d'appele de fonction find est toujours superieur ou égal à nbr d'appel de union. Du coup cela sera plus efficace de faire un find plus rapid
2- Dans cette Version on a toujours des arbres de hauteur maximal 1 parce que les sommets pointent directement vers le racine
3- Find est de complixité constante O(1)
4-La seul point négatif c'est union qui est de complixité linéaire O(n)
#initialisation de fôret def init(n): return range(n)
#return le racine def find(t,v): return t[v]
#test si deux éléments sont connectée <=> dans même arbre <=> ayant le même racine <=> il y a un chemin entre les deux def connected(t,v1,v2): return t[v1]==t[v2]
#ensemble d'equivalence d'un sommet <=> ensemble des éléments connctées <=> les sommets vers le quel il existe un chemin de sommet donné v def ensConx(t,v): ensConx=[] for i in range(len(t)): if find(t,v) == find(t,i) : ensConx.append(i) return ensConx
#Connecter deux sommets en regroupent leur ensemble d'equivlenc <=> fusionner les deux arbres contenat v1 v2 def union(t,v1,v2): if(t[v1]!=t[v2]): r1= t[v1] r2= t[v2] for i in range(len(t)): if(t[i]==r1): t[i]=r2 else: print("Already connected elements 'A cercle is created'") print(v1,v2)
#return True si le graphe est connexe, False sinon def estConnex(t): for i in range(1,len(t)): if(t[i]!=t[i-1]): return False return True
import random
#return ensemble de voisins alèatoire de sommet en y, x sans ordre c.a.d chaque fois ensemble different def Unvoisins(ht,lr, y,x): l=[] if(y>0): l.append(encode(ht,lr,y-1,x)) if(x>0): l.append(encode(ht,lr,y,x-1)) if(y<(ht-1)): l.append( encode(ht,lr,y+1,x)) if(x<(lr-1)): l.append( encode(ht,lr,y,x+1)) shuffle(l) return l
le technique utilsé pour savoir si la fonction "uninion" fait un cercle c'est de savoir si le graphe est connexe c.a.d si elle est connexe elle va forcement connecter deux elements qui sont déja connéctée donc dans plus part de cas on va tomber sur un cercle
#Genere un labyrinthe parfait def genere(ht,lr,ys,xs): l=[] n= ht*lr t = init(n) psl= range(n) shuffle(psl) possible_choises = set(psl) for y in range(2*ht+1): ll=[] for x in range(2*lr+1): if (((y%2)!=0) and ((x%2)!=0)): ll.append(0) else: ll.append(1) l.append(ll) while(not estConnex(t)): shuffle(psl) c1 = psl[0] #choix aléatoire (y1,x1)= decode(ht,lr,c1) ensVoisins=Unvoisins(ht,lr, y1,x1) c2 = ensVoisins[0] (y2,x2) = decode(ht,lr,c2) if not(connected(t,c1,c2)): union(t,c1,c2) if y1==y2: l[2*y1+1][x1+x2+1]=0 elif x1==x2: l[y1+y2+1][2*x1+1]=0 l[2*ys+2][2*xs+1]=0 return l
laby=genere(3,5,2,2)
affiche(laby)
+-----+--------+ | | | | +--+--+--+ | | | | +--+ +--+--+ | | | +-----+ +-----+
Cette fonction fait un laby pas parfait qui contient 'cr' cycles

En plus elle affiche les lieu où les cercles ont étés crées

def genereImparfait(ht,lr,ys,xs,cr): l=[] n= ht*lr t = init(n) psl= range(n) shuffle(psl) possible_choises = set(psl) for y in range(2*ht+1): ll=[] for x in range(2*lr+1): if (((y%2)!=0) and ((x%2)!=0)): ll.append(0) else: ll.append(1) l.append(ll) while(not estConnex(t) or cr>0 ): shuffle(psl) c1 = psl[0] #choix aléatoire (y1,x1)= decode(ht,lr,c1) ensVoisins=Unvoisins(ht,lr, y1,x1) c2 = ensVoisins[0] (y2,x2) = decode(ht,lr,c2) if not(connected(t,c1,c2)): union(t,c1,c2) if y1==y2: l[2*y1+1][x1+x2+1]=0 elif x1==x2: l[y1+y2+1][2*x1+1]=0 elif (connected(t,c1,c2)) and cr>0 and ((x1!=x2 and y1==y2 and l[2*y1+1][x1+x2+1]!=0 ) or (x1==x2 and y1!=y2 and l[y1+y2+1][2*x1+1]!=0)) : union(t,c1,c2) cr-=1 if y1==y2: l[2*y1+1][x1+x2+1]=0 elif x1==x2: l[y1+y2+1][2*x1+1]=0 l[2*ys+2][2*xs+1]=0 return l
#Ici elle va afficher les coordonnées où la cercle a été construit labyIm=genereImparfait(3,5,2,2,2) affiche(labyIm)
Already connected elements 'A cercle is created' (1, 6) Already connected elements 'A cercle is created' (10, 11) +--------+-----+ | | | +--+ + + + | | | | | + + +--+ | | | | | +-----+ +--+--+

RESOLUTION

#Fonction qui renvoie les coordonées (y,x) voisin dans la labyrinthe def UnvoisinsXY(ht,lr, y,x): y = (y-1)/2 x = (x-1)/2 l=[] if(y>0): l.append(((y-1)*2+1,x*2+1)) if(x>0): l.append((y*2+1,(x-1)*2+1)) if(y<(ht-1)): l.append(((y+1)*2+1,x*2+1)) if(x<(lr-1)): l.append((y*2+1,(x+1)*2+1)) return l
UnvoisinsXY(ht,lr, 5,5)
[(3, 5), (5, 3), (5, 7)]
La fonction de resoudre le labyrithe

elle crée un dictionnaire dont les clés sont les cases de labyrinthe et chaque clé point vers le tuile suivant pour arrivé à la sortie Si le labyrinthe n'est pas parfait elle trouve le plus court chemin aussi. Du coup elle fonctionne pour les deux labyrinth

def resout(laby): #coordonnées de sortie (sy,sx) = (5,5) #creer un dictionnaire ht=int(len(laby)/2) lr=int(len(laby[0])/2) dic= {} for y in range(2*ht+1): for x in range(2*lr+1): if (((y%2)!=0) and ((x%2)!=0)): dic[(y,x)]= None #creer les chemins lst=[(sy,sx)] while len(lst)>0: nxtl = [] for i in lst: (y,x)=i voisinsXY =UnvoisinsXY(ht,lr, y,x) for v in voisinsXY: (yv,xv) = v if (v!=(sy,sx)) and (dic[v])==None: if y==yv and laby[y][(x+xv)/2]==0: dic[v]=(i) nxtl.append(v) elif x==xv and laby[(y+yv)/2][x]==0: dic[v]=(i) nxtl.append(v) lst= nxtl return dic
(resout(laby))
{(1, 1): (3, 1), (1, 3): (1, 1), (1, 5): (1, 7), (1, 7): (1, 9), (1, 9): (3, 9), (3, 1): (3, 3), (3, 3): (5, 3), (3, 5): (3, 3), (3, 7): (3, 9), (3, 9): (5, 9), (5, 1): (5, 3), (5, 3): (5, 5), (5, 5): None, (5, 7): (5, 5), (5, 9): (5, 7)}
#cette fonction construit le chemin de (y,x) vert la sortie (sy,sx) #Le chemin commence par le sommet(tuile) de coordonnées (y,x) jusqu'à la sortie (sy,sx) et contenant les sommets parcourus def reconstruit_chemin(plan, y,x): l=[(y,x)] while plan[(y,x)]!=None: l.append(plan[(y,x)]) (y,x)= plan[(y,x)] return l

ces deux fonction resumeParfait et resumeImparfait resument tous ce que j'ai fait avant donc elle genere un laby parfait et un autre imparfait et resoudre les deux laby par afficher les chemins de chauque tuile vers la sortie et quand le laby est imparfait elle fait le plus court chemin Ces deux fonction n'a rien avoir la question B6'

def resumeParfait(): print("Bienvenue dans mon labyrinthe parfait") laby=genere(3,5,2,2) affiche(laby) plan = resout(laby) for y in range(ht): for x in range(lr): print"Le chemin de tuile", (2*y+1,2*x+1), " est ", reconstruit_chemin(plan,2*y+1,2*x+1) return
resumeParfait()
Bienvenue dans mon labyrinthe parfait +-----+--------+ | | | | + + +--+ | | | | | | +--+--+--+ | | | | +-----+ +-----+ Le chemin de tuile (1, 1) est [(1, 1), (1, 3), (3, 3), (3, 5), (1, 5), (1, 7), (1, 9), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (1, 3) est [(1, 3), (3, 3), (3, 5), (1, 5), (1, 7), (1, 9), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (1, 5) est [(1, 5), (1, 7), (1, 9), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (1, 7) est [(1, 7), (1, 9), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (1, 9) est [(1, 9), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (3, 1) est [(3, 1), (1, 1), (1, 3), (3, 3), (3, 5), (1, 5), (1, 7), (1, 9), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (3, 3) est [(3, 3), (3, 5), (1, 5), (1, 7), (1, 9), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (3, 5) est [(3, 5), (1, 5), (1, 7), (1, 9), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (3, 7) est [(3, 7), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (3, 9) est [(3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (5, 1) est [(5, 1), (3, 1), (1, 1), (1, 3), (3, 3), (3, 5), (1, 5), (1, 7), (1, 9), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (5, 3) est [(5, 3), (5, 1), (3, 1), (1, 1), (1, 3), (3, 3), (3, 5), (1, 5), (1, 7), (1, 9), (3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (5, 5) est [(5, 5)] Le chemin de tuile (5, 7) est [(5, 7), (5, 5)] Le chemin de tuile (5, 9) est [(5, 9), (5, 7), (5, 5)]
def resumeImparfait(n): print("Bienvenue dans mon labyrinthe imparfait") laby=genereImparfait(3,5,2,2,n) affiche(laby) plan = resout(laby) for y in range(ht): for x in range(lr): print"Le chemin de tuile", (2*y+1,2*x+1), " est ", reconstruit_chemin(plan,2*y+1,2*x+1) return
resumeImparfait(3)
Bienvenue dans mon labyrinthe imparfait Already connected elements 'A cercle is created' (1, 6) Already connected elements 'A cercle is created' (13, 8) Already connected elements 'A cercle is created' (2, 7) +--+-----------+ | | | | | + + + | | | | | | | + +--+ + | | | +-----+ +-----+ Le chemin de tuile (1, 1) est [(1, 1), (3, 1), (5, 1), (5, 3), (5, 5)] Le chemin de tuile (1, 3) est [(1, 3), (3, 3), (5, 3), (5, 5)] Le chemin de tuile (1, 5) est [(1, 5), (1, 3), (3, 3), (5, 3), (5, 5)] Le chemin de tuile (1, 7) est [(1, 7), (3, 7), (5, 7), (5, 5)] Le chemin de tuile (1, 9) est [(1, 9), (1, 7), (3, 7), (5, 7), (5, 5)] Le chemin de tuile (3, 1) est [(3, 1), (5, 1), (5, 3), (5, 5)] Le chemin de tuile (3, 3) est [(3, 3), (5, 3), (5, 5)] Le chemin de tuile (3, 5) est [(3, 5), (3, 3), (5, 3), (5, 5)] Le chemin de tuile (3, 7) est [(3, 7), (5, 7), (5, 5)] Le chemin de tuile (3, 9) est [(3, 9), (5, 9), (5, 7), (5, 5)] Le chemin de tuile (5, 1) est [(5, 1), (5, 3), (5, 5)] Le chemin de tuile (5, 3) est [(5, 3), (5, 5)] Le chemin de tuile (5, 5) est [(5, 5)] Le chemin de tuile (5, 7) est [(5, 7), (5, 5)] Le chemin de tuile (5, 9) est [(5, 9), (5, 7), (5, 5)]
""" CA n'a rien avoir avec le DM """
"\nCA n'a rien avoir avec le DM\n\n\n\n"
import math inf = float('inf')
t=[[0,inf,-2,inf], [4,0,3,inf], [inf,inf,0,2], [inf,-1,inf,0]]
for i in range(len(t)): print(t[i])
[0, inf, -2, inf] [4, 0, 3, inf] [inf, inf, 0, 2] [inf, -1, inf, 0]
#Floyd warshall
for k in range(4): for i in range(4): for j in range(4): if ( t[i][j]>t[i][k]+t[k][j]): t[i][j] = t[i][k]+t[k][j]
def printTx2(t): for i in range(len(t)): print(t[i])
printTx2(t)
[0, -1, -2, 0] [4, 0, 2, 4] [5, 1, 0, 2] [3, -1, 1, 0]
def FWAlgo( matriceAdj): t = [] t=matriceAdj for k in range(len(t)): for i in range(len(t)): for j in range(len(t)): if ( t[i][j]>t[i][k]+t[k][j]): t[i][j] = t[i][k]+t[k][j] return t
printTx2(FWAlgo(t))
[0, -1, -2, 0] [4, 0, 2, 4] [5, 1, 0, 2] [3, -1, 1, 0]