Discussion :

[Tomqu]

Bonjour,

J'ai un exo à réaliser en Python mais je suis un peu perdu.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
labyrinth = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
             [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
             [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1],
             [1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
             [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1],
             [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1],
             [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1],
             [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],
             [1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1],
             [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],
             [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1],
             [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
             [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1],
             [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1],
             [1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1],
             [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
             [1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1],
             [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
             [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
             [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
             [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
 
class Labyrinth:
 
    def __init__(self, labyrinth, begin, end):
        self.__labyrinth = labyrinth
        self.__begin = begin
        self.__end = end
        self.__solution = []
 
    def set_solution(self, solution):
        self.__solution = solution
 
    def __str__(self):
        r = ""
        for y, line in enumerate(labyrinth):
            r += "\n"
            for x, c in enumerate(line):
                if c == 1:
                    r += u"\u2588" + u"\u2588"
                elif (x, y) == self.__begin:
                    r += 'b '
                elif (x, y) == self.__end:
                    r += ' e'
                elif (x, y) in self.__solution:
                    r += '::'                    
                else:
                    r += '  '
        return r
 
    def find_solution(self):
        """
        This method must return the shortest solution of the labyrinth.
        It's represented as the list of all the coordinates of the path's cells
        """
        return [(0, 19), (1, 19), (1, 18), (1, 17), (2, 17), (3, 17), (3, 16), (3, 15), (4, 15), (5, 15), (6, 15), (7, 15), (7, 16), (7, 17), (7, 18), (7, 19), (8, 19), (9, 19), (10, 19), (11, 19), (12, 19), (13, 19), (14, 19), (15, 19), (16, 19), (17, 19), (18, 19), (19, 19), (19, 18), (19, 17), (18, 17), (17, 17), (16, 17), (15, 17), (15, 16), (15, 15), (15, 14), (15, 13), (16, 13), (17, 13), (17, 12), (17, 11), (17, 10), (17, 9), (17, 8), (17, 7), (17, 6), (17, 5), (17, 4), (17, 3), (17, 2), (17, 1), (18, 1), (19, 1), (20, 1)]
 
l = Labyrinth(labyrinth, (0, 19), (20, 1))
solution = l.find_solution()
 
l.set_solution(solution)
print(l)

Les 1 représentent les murs et les 0 les endroits où l'on peut passer.
Le but est de remplir la fonction find_solution qui renvoie la liste des coordonnées du plus court chemin pour résoudre le labyrinthe.
Je pense que la façon la plus simple est d'utiliser le BFS mais je ne vois pas comment l'implémenter.

Merci d'avance,

[wiztricks]

Salut,

Je pense que la façon la plus simple est d'utiliser le BFS mais je ne vois pas comment l'implémenter.

C'est un exercice assez connu. Chercher un peu sur Internet avec les mots clefs "python maze graph" devrait récupérer quelques sources d'inspiration.

- W

[Tomqu]

Salut,



C'est un exercice assez connu. Chercher un peu sur Internet avec les mots clefs "python maze graph" devrait récupérer quelques sources d'inspiration.

- W

J'ai commencé par transformer mon labyrinthe en un dictionnaire avec comme clés chaque coordonné et valeur ses voisins.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
dictvoisins=dict()
 
        for y,line in enumerate(labyrinth):
            for x,c in enumerate(line):
                voisins=[]
 
                try:
 
 
                    if labyrinth[x-1][y]==0:
                        if x-1>=0  :
 
                            voisins.append((y,x-1))
                    if labyrinth[x][y-1]==0:
 
                        if y-1>=0:
                            voisins.append((y-1,x))
                    if labyrinth[x+1][y]==0:
                        if x+1<=len(labyrinth):
 
                            voisins.append((y,x+1))
                    if labyrinth[x][y+1]==0:
 
                        if y+1<=len(labyrinth):
                            voisins.append((y+1,x))
 
                except IndexError:
                    continue
 
                dictvoisins[(y,x)]=voisins

Mais lorsque j'exécute, je ne comprends pas pourquoi il ne va pas jusqu'à 20 (mon labyrinthe étant 21*21)
Il s'arrête à 19 donc je n'ai par exemple pas la clé (0,20) ou (20,3)

[wiztricks]

Salut,

Si cachez la misère sous le tapis avec:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
     try:
     ....
     except IndexError:
            continue

çà fait des choses étranges.

Et çà veut surtout dire que vous n'avez pas trop réfléchit à ce que vous vouliez avant de coder.

- W

[Tomqu]

En effet, le IndexError était juste un test, il n'était pas la au départ.
Mon problème est de créer le dictionnaire avec les voisins de chaque sommet (représenté par ses coordonnés).
J'ai surtout du mal avec la gestion des bords.

[wiztricks]

Salut,

J'ai surtout du mal avec la gestion des bords.

Vous pouvez fabriquer une fonction qui retourne la liste des cases voisines pour chaque (i, j), puis vous filtrez les cases "valides", puis vous récupérer les cases accessibles.

Vous pouvez aussi ajouter des des bords (des cases inaccessibles) au tableau, ce qui évite un tas de tests.

C'est plus un problème d'algo. que de code.

- W