Coverage for src/ensae_teaching_cs/special/puzzle_girafe.py: 95%
238 statements
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
1# -*- coding: utf-8 -*-
2"""
3@file
4@brief Fonctions, classes pour résoudre un puzzle à 9 pièces disposé en carré 3x3. Voir :ref:`l-puzzle_girafe`.
5"""
7import time
8import os
9from pyquickhelper.loghelper import fLOG
10from ..helpers.pygame_helper import wait_event, empty_main_loop
13class PuzzleGirafeBord:
14 """
15 Définition d'un bord ou côté d'une pièce, il possède :
17 - partie : une partie de la girafe (haut ou bas)
18 - une couleur : la couleur de cette partie, (orange, violet, bleu clair, bleu foncé)
19 """
21 def __init__(self, definition):
22 """
23 @param definition chaîne de caractères
25 *definition* est une chaîne de 2 caractères qui définit un bord, exemple :
27 * ``HO`` pour haut orange
28 * ``BB`` pour bas bleu
29 * ``BV`` pour bas violet
30 * ``HM`` pour haut mauve
31 """
33 if definition[0] == "H":
34 self.partie = "haut"
35 elif definition[0] == "B":
36 self.partie = "bas"
37 else:
38 self.partie = definition + "###"
40 if definition[1] == "O":
41 self.couleur = "orange"
42 elif definition[1] == "B":
43 self.couleur = "bleu clair"
44 elif definition[1] == "M":
45 self.couleur = "violet"
46 elif definition[1] == "V":
47 self.couleur = "bleu fonce"
48 else:
49 self.couleur = definition + "##"
51 def __str__(self):
52 """
53 Cette méthode est appelée lorsqu'on exécute l'instruction print
54 avec un objet de type @see cl PuzzleGirafeBord.
55 """
56 return self.partie + " " + self.couleur
58 def compatible(self, bord):
59 """
60 dit si deux bords sont compatibles, c'est à dire
61 de la même couleur et de partie différente
62 """
63 return self.couleur == bord.couleur and self.partie != bord.partie
66class PuzzleGirafePiece:
67 """
68 Définition d'une pièce du puzzle, celle-ci inclut :
70 - **bord** : cette liste contient quatre objets de type Bord, cette liste ne changera plus
71 - **position** : c'est la position de la pièce dans le puzzle, ce qui nous intéresse,
72 c'est la position finale de la pièce dans le puzzle, cette information
73 va donc bouger au fur et à mesure que nous allons essayer de
74 résoudre le puzzle
75 - **orientation** : de même que pour la position, une pièce peut être tournée sans changer de
76 position, c'est le résultat final qui nous intèresse
78 pour l'affichage, on ajoute deux informations :
80 - **name** : le nom de l'image de la pièce
81 - **image** : c'est la représentation de l'image dans la mèmoire de
82 l'ordinateur pour le module pygame
83 """
85 def __init__(self, name, definition, position, numero):
86 """
87 on définit la pièce
89 @param name nom de l'image représentant la pièce
90 @param definition chaîne de 8 caractères, c'est une suite de 4 x 2 caractères définissant
91 chaque bord, voir la classe bord pour leur signification
92 @param position c'est la position initiale de la pièce, on suppose que
93 l'orientation est nulle pour commencer
94 @param numero numéro de la pièce
96 à partir de ces informations, on construit :
98 - **image** : c'est la représentation en mémoire de l'image de la pièce
99 - **bord** : c'est une liste qui définit les 4 bords de la pièce
100 - **orientation** : c'est l'orientation de la pièce, au début de la résolution, elle est nulle
101 """
102 self.name = name
103 self.bord = []
105 for i in range(0, 4):
106 self.bord.append(PuzzleGirafeBord(definition[i * 2:i * 2 + 2]))
108 self.orientation = 0
109 self.position = position
110 self.numero = numero
112 def load_image(self, pygame):
113 """
114 charge l'image pour une simulation graphique
116 @param pygame module :epkg:`pygame`
117 """
118 image = pygame.image.load(self.name)
119 self.image = pygame.transform.scale(image, (250, 250))
120 s = self.image.get_size()
121 self.image_petite = pygame.transform.scale(
122 self.image, (int(s[0] * 0.7), int(s[1] * 0.7)))
124 def __str__(self):
125 """
126 définition ce qu'on doit afficher lorsqu'on exécute
127 l'instruction print avec un objet de type @see cl PuzzleGirafePiece.
128 """
129 s = str(self.position) + " : "
130 for b in self.bord:
131 s += str(b) + " - "
132 s += " orientation " + str(self.orientation)
133 s += " numero " + str(self.numero)
134 return s
136 def bord_angle(self, angle, orientation=None):
137 """
138 retourne le bord connaissant l'orientation de la pièce,
139 le bord demandé est celui correspondant à :
141 - 0 bord droit
142 - 90 bord haut
143 - 180 bord gauche
144 - 270 bord bas
145 """
146 if orientation is None:
147 return self.bord_angle(angle, self.orientation)
148 else:
149 dif = (angle - orientation + 360) % 360 // 90
150 return self.bord[dif]
152 def voisin_possible(self, p, a):
153 """
154 détermine si la pièce *self* peut être voisine avec la pièce *p* tournée de l'angle *a*
155 """
156 d = p.position - self.position
157 if abs(d) == 1 and (p.position - 1) // 3 == (self.position - 1) // 3:
158 # voisin en x
159 if d == 1:
160 a1 = 0
161 a2 = a1 + 180
162 else:
163 a1 = 180
164 a2 = 0
165 elif abs(d) == 3:
166 # voisin en y
167 if d == 1:
168 a1 = 90
169 a2 = 270
170 else:
171 a1 = 270
172 a2 = 90
173 else:
174 # pas voisin
175 return False
177 b1 = self.bord_angle(a1)
178 b2 = p.bord_angle(a2, a)
179 return b1.compatible(b2)
182class PuzzleGirafe:
183 """
184 définition d'une classe puzzle, elle contient simplement
185 une liste de 9 pièces dont les positions sont ::
187 1 2 3
188 4 5 6
189 7 8 9
191 et les orientations choisies dans l'ensemble *{ 0,90,180,270 }*
193 Voir :ref:`l-puzzle_girafe`.
194 """
196 def __init__(self):
197 """
198 on définit le puzzle à partir des informations contenues
199 dans le répertoire *data* de ce module qui doit contenir :
201 - 9 images appelées ``piece1.png``, ..., ``piece0.png``
202 - un fichier ``definition_puzzle_girafe.txt`` contenant la définition de
203 chacun des 4 bords de chacune des 9 pièces::
205 HOBBBVHM
206 HOBBBVHM
207 HBBMBVHO
208 HMBBBVHB
209 BMBOHBHV
210 HVBMBOHM
211 BMBVHBHO
212 HVHMBBBO
213 BMHOHVBB
214 """
215 dir_ = os.path.abspath(os.path.dirname(__file__))
216 dir_ = os.path.join(dir_, "data")
218 with open(os.path.join(dir_, "definition_puzzle_girafe.txt"), "r") as f:
219 bo = f.readlines()
221 # on définit chaque pièce
222 self.piece = []
223 for i in range(1, 10):
224 name = os.path.join(dir_, "piece%d.png" % i)
225 d = bo[i - 1]
226 p = PuzzleGirafePiece(name, d, 0, i)
227 self.piece.append(p)
229 def load_images(self, pygame):
230 """
231 charge les images pour une simulation graphique
233 @param pygame module :epkg:`pygame`
234 """
235 for p in self.piece:
236 p.load_image(pygame)
238 def __str__(self):
239 """
240 ce qu'on doit afficher lorsqu'on exécute
241 l'instruction print avec un objet de type @see cl PuzzleGirafe.
242 """
243 s = """1 2 3
244 4 5 6
245 7 8 9
246 """.replace(" ", "")
247 for p in self.piece:
248 s += str(p) + "\n"
249 return s
251 def pixel(self, position):
252 """
253 retourne en fonction de la position (1 à 9) de la pièce sa position sur l'écran,
254 soit deux coordonnées
256 @return tuple *(x,y)*
257 """
258 p = position - 1
259 ligne = p // 3
260 colonne = p % 3
261 return (colonne * 250, ligne * 250)
263 def meilleure_piece(self, free, pos):
264 """
265 retourne la prochaine pièce à placer sur le puzzle,
266 dans un premier temps, on peut prend la première qui vient,
267 ensuite, on peut essayer un choix plus judicieux
268 """
269 if len(free) == 0:
270 return None
271 else:
272 return free[0]
274 def piece_position(self, pi):
275 """
276 recherche la piece associée à la position pi
277 """
278 for p in self.piece:
279 if p.position == pi:
280 return p
281 return None
283 def ensemble_voisin(self, i):
284 """
285 retourne les positions voisins de la position i
286 """
287 i -= 1
288 res = []
289 for x in [-1, 0, 1]:
290 for y in [-1, 0, 1]:
291 if abs(x) == abs(y):
292 continue
293 if x == -1 and i % 3 == 0:
294 continue
295 if x == 1 and i % 3 == 2:
296 continue
297 if y == -1 and i // 3 == 0:
298 continue
299 if y == 1 and i // 3 == 2:
300 continue
301 j = i + x + y * 3
302 if j in range(0, 9):
303 res.append(j)
304 return [j + 1 for j in res]
306 def nb_place(self):
307 """
308 retourne le nombre de places vides
309 """
310 i = 0
311 for p in self.piece:
312 if p.position == 0:
313 i += 1
314 return i
316 def angle_possible(self, p, display=False):
317 """
318 retourne l'ensemble des angles possibles pour une pièce donnée
319 """
320 voisin = self.ensemble_voisin(p.position)
321 if display:
322 print("voisin = ", voisin)
323 res = []
324 for a in [0, 90, 180, 270]:
325 r = True
326 for v in voisin:
327 piece = self.piece_position(v)
328 if piece is not None:
329 r = r and piece.voisin_possible(p, a)
330 if r:
331 res.append(a)
332 return res
334 def solution(self, pos=1, screen=None, pygame=None, images=None, delay=200):
335 """
336 Résoud le puzzle de façon récursive : on pose une pièce puis on résoud
337 le puzzle restant (une pièce en moins, une case en moins).
339 @param pos niveau de récursivité
340 @param screen image pygame
341 @param pygame module pygame
342 @param images stores images in this list if not None
343 @param delay delay between two tries
345 L'affichage *pygame* est optionnel.
346 """
347 if pos == 1:
348 for p in self.piece:
349 p.position = 0
350 self.nb_position = 0
351 self.essai = 0
353 self.essai += 1
355 if self.nb_position == len(self.piece):
356 time.sleep(0.2)
357 return None
359 # le tableau free mémorise l'ensemble des pièces non encore placées
360 free = []
361 for p in self.piece:
362 if p.position == 0:
363 free.append(p)
365 if screen is not None and pygame is not None and images is not None:
366 empty_main_loop(pygame)
367 display_puzzle_girafe(self, screen, True, pygame=pygame)
368 pygame.display.flip()
369 images.append(screen.copy())
371 p = self.meilleure_piece(free, pos)
372 # si p == None, on n'étudie pas les solutions avec les pièces placées
373 # avant aux positions 1 à pos --> on n'entrera pas dans la boucle
374 # suivante
375 while p is not None:
377 p.position = pos
378 angle = self.angle_possible(p)
380 # p est la pièce choisie, pour cette pièce
381 # on passe en revue toutes les orientations
382 for a in angle:
383 p.orientation = a
385 if pygame is not None:
386 pygame.time.wait(delay)
388 if self.nb_place() == 0:
389 return True
390 else:
391 r = self.solution(pos + 1, screen=screen,
392 pygame=pygame, images=images, delay=delay)
393 if r:
394 return True
396 p.position = 0
398 # on réactualise le tableau free qui aura été modifié par
399 # l'appel à self.solution et on enlève le choix précédemment
400 # testé
401 free2 = free
402 free = []
403 for f in free2:
404 if f.numero != p.numero:
405 free.append(f)
407 # on passe au choix suivant avec free contenant les pièces
408 # placées et les pièces essayées
409 p = self.meilleure_piece(free, pos)
410 return None
413def display_puzzle_girafe(self, screen, petite=False, pygame=None):
414 """
415 affiche les pièces sur l'écran,
416 en plus petit pour celles qui ne sont pas encore placées
417 """
418 screen.fill((0, 0, 0))
419 free = [0 for i in self.piece]
420 for p in self.piece:
421 if p.position > 0:
422 p.darker = False
423 display_puzzle_girafe_piece(
424 p, screen, self.pixel(p.position), pygame=pygame)
425 free[p.position - 1] = 1
427 if petite:
428 em = []
429 for i in range(0, len(free)):
430 if free[i] == 0:
431 em.append(i + 1)
432 i = 0
433 for p in self.piece:
434 if p.position == 0:
435 p.darker = True
436 display_puzzle_girafe_piece(
437 p, screen, self.pixel(em[i]), pygame)
438 i += 1
440 pygame.display.flip()
443def display_puzzle_girafe_piece(self, screen, position, pygame):
444 """
445 affiche la pièce en tenant compte de sa position et de son orientation
446 """
447 if "darker" in self.__dict__ and self.darker:
448 position = (position[0] + 20, position[1] + 20)
449 image = pygame.transform.rotate(self.image_petite, self.orientation)
450 screen.blit(image, position)
451 else:
452 image = pygame.transform.rotate(self.image, self.orientation)
453 screen.blit(image, position)
456def pygame_simulation(pygame, first_click=False, folder=None,
457 size=(750, 750), fLOG=fLOG, delay=200,
458 flags=0):
459 """
460 Simulation graphique.
461 Illuste la résolution du puzzle
463 @param pygame module pygame
464 @param first_click attend la pression d'un clic de souris avant de commencer
465 @param folder répertoire où stocker les images de la simulation
466 @param size taille de l'écran
467 @param delay delay between two tries
468 @param flags see `pygame.display.set_mode <https://www.pygame.org/docs/ref/display.html#pygame.display.set_mode>`_
469 @param fLOG logging function
470 @return @see cl PuzzleGirafe
472 La simulation ressemble à ceci :
474 .. raw:: html
476 <video autoplay="" controls="" loop="" height="500">
477 <source src="http://www.xavierdupre.fr/enseignement/complements/puzzle_girafe.mp4" type="video/mp4" />
478 </video>
480 Pour lancer la simulation::
482 from ensae_teaching_cs.special.puzzle_girafe import pygame_simulation
483 import pygame
484 pygame_simulation(pygame)
486 Voir :ref:`l-puzzle_girafe`.
487 """
488 # initialisation du module pygame
489 pygame.init()
490 screen = pygame.display.set_mode(size, flags)
492 # on définit le puzzle
493 p = PuzzleGirafe()
494 p.load_images(pygame)
496 # on affiche le puzzle avec print (format texte)
497 fLOG("\n" + str(p))
499 # on affiche le puzzle à l'écran
500 display_puzzle_girafe(p, screen, petite=True, pygame=pygame)
501 if first_click:
502 wait_event(pygame)
504 # on rafraîchit l'écran pour que le puzzle apparaissent
505 pygame.display.flip()
507 images = [] if folder is not None else None
509 # on trouve la solution
510 r = p.solution(screen=screen, pygame=pygame, images=images, delay=delay)
511 fLOG("résolution ", r)
512 fLOG("nombre d'appels à la méthode solution ", p.essai)
514 if images is not None:
515 empty_main_loop(pygame)
516 display_puzzle_girafe(p, screen, True, pygame=pygame)
517 pygame.display.flip()
518 images.append(screen.copy())
520 if folder is not None:
521 fLOG("saving images")
522 for it, screen in enumerate(images):
523 if it % 10 == 0:
524 fLOG("saving image:", it)
525 image = os.path.join(folder, "image_%04d.png" % it)
526 pygame.image.save(screen, image)
528 # on attend la pression d'un clic de souris avant de terminer le programme
529 display_puzzle_girafe(p, screen, petite=True, pygame=pygame)
530 if first_click:
531 wait_event(pygame)