Coverage for src/ensae_teaching_cs/special/puzzle_2.py: 90%
243 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 à 8 pièces
5disposé de façon non conventionnelle. Voir :ref:`l-puzzle_2`.
6"""
8import time
9import os
10from textwrap import dedent
11from pyquickhelper.loghelper import fLOG
12from ..helpers.pygame_helper import wait_event, empty_main_loop
15class Puzzle2Bord:
16 """
17 Définition d'un bord ou côté d'une pièce, il possède deux couleurs.
18 """
20 def __init__(self, definition):
21 """
22 :param definition: chaîne de caractères
24 *definition* est une chaîne de 2 caractères qui définit un bord, exemple :
26 * ``RG`` for rouge vert (red, green)
28 Les quatre couleurs sont R (red, rouge), Y (yellow, jaune),
29 G (green, vert), B (blue, bleu).
30 """
31 if len(definition) != 2:
32 raise ValueError(f"Deux couleurs attendues pas {definition!r}.")
33 for i in range(2):
34 if definition[i] not in 'RYGB':
35 raise ValueError(f"Couleurs inattendues: {definition!r}.")
36 self.couleur = tuple(definition)
38 def __str__(self):
39 """
40 Cette méthode est appelée lorsqu'on exécute l'instruction print
41 avec un objet de type @see cl Puzzle2Bord.
42 """
43 return "".join(self.couleur)
45 def compatible(self, bord):
46 """
47 Dit si deux bords sont compatibles, ils ont les mêmes
48 couleurs mais inversées.
49 """
50 return (self.couleur[0] == bord.couleur[1] and
51 self.couleur[1] == bord.couleur[0])
54class Puzzle2Piece:
55 """
56 Définition d'une pièce du puzzle, celle-ci inclut :
58 - **bord** : cette liste contient quatre objets de type Bord,
59 cette liste ne changera plus
60 - **position** : c'est la position de la pièce dans le puzzle,
61 ce qui nous intéresse, c'est la position finale de la pièce
62 dans le puzzle, cette information va donc bouger au fur et
63 à mesure que nous allons essayer de résoudre le puzzle
64 - **orientation** : de même que pour la position, une pièce peut
65 être tournée sans changer de position, c'est le résultat final
66 qui nous intèresse
68 Pour l'affichage, on ajoute deux informations :
70 - **name** : le nom de l'image de la pièce
71 - **image** : c'est la représentation de l'image dans la mèmoire de
72 l'ordinateur pour le module pygame
73 """
75 def __init__(self, name, definition, position, numero):
76 """
77 On définit la pièce:
79 :param name: nom de l'image représentant la pièce
80 :param definition: chaîne de 4 caractères indiquant les quatre couleurs
81 au quatre angles
82 :param position: c'est la position initiale de la pièce,
83 on suppose que l'orientation est nulle pour commencer
84 :param numero: numéro de la pièce
86 A partir de ces informations, on construit :
88 - **image** : c'est la représentation en mémoire de l'image de la pièce
89 - **bord** : c'est une liste qui définit les 4 bords de la pièce
90 - **orientation** : c'est l'orientation de la pièce, au début de
91 la résolution, elle est nulle
92 """
93 self.name = name
94 self.bord = []
96 for i in range(0, 3):
97 self.bord.append(Puzzle2Bord(definition[i:i + 2]))
98 self.bord.append(Puzzle2Bord(definition[-1] + definition[0]))
100 self.orientation = 0
101 self.position = position
102 self.numero = numero
104 def load_image(self, pygame):
105 """
106 Charge l'image pour une simulation graphique.
108 :param pygame: module :epkg:`pygame`
109 """
110 image = pygame.image.load(self.name)
111 self.image = pygame.transform.scale(image, (150, 150))
112 s = self.image.get_size()
113 self.image_petite = pygame.transform.scale(
114 self.image, (int(s[0] * 0.7), int(s[1] * 0.7)))
116 def __str__(self):
117 """
118 Définition ce qu'on doit afficher lorsqu'on exécute
119 l'instruction print avec un objet de type
120 @see cl Puzzle2Piece.
121 """
122 s = str(self.position) + " : "
123 s += "-".join("".join(self.bord_angle(a * 90, 0).couleur)
124 for a in range(0, 4))
125 s += " :: "
126 s += "-".join("".join(self.bord_angle(a * 90, self.orientation).couleur)
127 for a in range(0, 4))
128 s += " or=%d" % self.orientation
129 s += " numero=%d" % self.numero
130 s += " pos=%d" % self.position
131 return s
133 def bord_angle(self, angle, orientation=None):
134 """
135 Retourne le bord connaissant l'orientation de la pièce,
136 le bord demandé est celui correspondant à :
138 - 0 bord droit
139 - 90 bord haut
140 - 180 bord gauche
141 - 270 bord bas
142 """
143 if orientation is None:
144 return self.bord_angle(angle, self.orientation)
145 dif = (angle - orientation + 360) % 360 // 90
146 return self.bord[dif]
149class Puzzle2:
150 """
151 Définition d'une classe puzzle, elle contient simplement
152 une liste de 9 pièces dont les positions sont:
154 ::
156 5
157 6 1 2
158 4 3 7
159 8
161 et les orientations choisies dans l'ensemble ``{ 0, 90, 180, 270 }``
163 Voir :ref:`l-puzzle_2`.
164 """
166 def __init__(self):
167 """
168 On définit le puzzle à partir des informations contenues
169 dans le répertoire *data* de ce module qui doit contenir :
171 - 8 images appelées ``piece21.png``, ..., ``piece28.png``
172 - un fichier ``definition_puzzle_girafe.txt`` contenant la définition de
173 chacun des 4 bords de chacune des 9 pièces :
175 ::
177 GBYR
178 BRYG
179 BGYR
180 YRGB
181 YBRG
182 BGYR
183 BYGR
184 RYBG
185 """
186 dir_ = os.path.abspath(os.path.dirname(__file__))
187 dir_ = os.path.join(dir_, "data")
189 with open(os.path.join(dir_, "definition_puzzle_2.txt"), "r") as f:
190 bo = f.readlines()
192 # on définit chaque pièce
193 self.piece = []
194 for i in range(1, 9):
195 name = os.path.join(dir_, "piece2%d.png" % i)
196 d = bo[i - 1].strip(" \n\r")
197 d = d[1:] + d[0]
198 p = Puzzle2Piece(name, d, 0, i)
199 self.piece.append(p)
200 print(p)
202 def load_images(self, pygame):
203 """
204 Charge les images pour une simulation graphique.
206 :param pygame: module :epkg:`pygame`
207 """
208 for p in self.piece:
209 p.load_image(pygame)
211 def __str__(self):
212 """
213 Ce qu'on doit afficher lorsqu'on exécute
214 l'instruction print avec un objet de type
215 @see cl Puzzle2.
216 """
217 s = dedent("""
218 5
219 6 1 2
220 4 3 7
221 8
222 """).strip("\n\r") + "\n"
223 for p in self.piece:
224 s += str(p) + "\n"
225 return s
227 def pixel(self, position):
228 """
229 Retourne en fonction de la position (1 à 8) de la
230 pièce sa position sur l'écran, soit deux coordonnées.
232 :return: `tuple(x,y)`
234 ::
236 5
237 6 1 2
238 4 3 7
239 8
240 """
241 positions = {
242 1: (1, 1),
243 2: (1, 2),
244 3: (2, 2),
245 4: (2, 1),
246 5: (0, 1),
247 6: (1, 0),
248 7: (2, 3),
249 8: (3, 2)
250 }
251 ligne, colonne = positions[position]
252 return (colonne * 150, ligne * 150)
254 def meilleure_piece(self, free, pos):
255 """
256 Retourne la prochaine pièce à placer sur le puzzle,
257 dans un premier temps, on peut prend la première qui vient,
258 ensuite, on peut essayer un choix plus judicieux.
259 """
260 if len(free) == 0:
261 return None
262 return free[0]
264 def piece_position(self, pi):
265 """
266 Recherche la piece associée à la position pi.
267 """
268 for p in self.piece:
269 if p.position == pi:
270 return p
271 return None
273 def ensemble_voisin(self, i):
274 """
275 Retourne les positions voisins de la position i.
276 Retourne toujours quatre voisins, 0 si la case
277 est hors-jeu.
279 ::
281 5
282 6 1 2
283 4 3 7
284 8
286 ::
287 1
288 0 3
289 2
290 """
291 if i == 1:
292 return [6, 5, 4, 2]
293 if i == 2:
294 return [1, 0, 3, 0]
295 if i == 3:
296 return [4, 2, 8, 7]
297 if i == 4:
298 return [0, 1, 0, 3]
299 if i == 5:
300 return [0, 0, 1, 0]
301 if i == 6:
302 return [0, 0, 0, 1]
303 if i == 7:
304 return [3, 0, 0, 0]
305 if i == 8:
306 return [0, 3, 0, 0]
307 raise ValueError(f"Unexpected position {i!r}.")
309 def nb_place(self):
310 """
311 Retourne le nombre de places vides.
312 """
313 i = 0
314 for p in self.piece:
315 if p.position == 0:
316 i += 1
317 return i
319 def voisin_possible(self, piece, p, a):
320 """
321 Détermine si la pièce *self* peut être voisine
322 avec la pièce *p* tournée de l'angle *a*.
323 """
324 v1 = self.ensemble_voisin(piece.position)
325 if p.position not in set(v1):
326 return False
327 v2 = self.ensemble_voisin(p.position)
328 if piece.position not in set(v2):
329 return False
330 d = p.position - piece.position
331 if abs(d) == 1 and (p.position - 1) // 3 == (piece.position - 1) // 3:
332 # voisin en x
333 if d == 1:
334 a1 = 0
335 a2 = a1 + 180
336 else:
337 a1 = 180
338 a2 = 0
339 elif abs(d) == 3:
340 # voisin en y
341 if d == 1:
342 a1 = 90
343 a2 = 270
344 else:
345 a1 = 270
346 a2 = 90
347 else:
348 # pas voisin
349 return False
351 b1 = piece.bord_angle(a1)
352 b2 = p.bord_angle(a2, a)
353 return b1.compatible(b2)
355 def angle_possible(self, p, display=False):
356 """
357 Retourne l'ensemble des angles possibles
358 pour une pièce donnée.
359 """
360 voisin = self.ensemble_voisin(p.position)
361 if display:
362 print("voisin = ", voisin)
363 res = []
364 for a in [0, 90, 180, 270]:
365 r = True
366 for v in voisin:
367 if v == 0:
368 continue
369 piece = self.piece_position(v)
370 if piece is not None:
371 t = self.voisin_possible(piece, p, a)
372 r = r and t
373 if r:
374 res.append(a)
375 return res
377 def solution(self, pos=1, screen=None, pygame=None, images=None, delay=200):
378 """
379 Résoud le puzzle de façon récursive : on pose une
380 pièce puis on résoud le puzzle restant
381 (une pièce en moins, une case en moins).
383 :param pos: niveau de récursivité
384 :param screen: image pygame
385 :param pygame: module pygame
386 :param images: stores images in this list if not None
387 :param delay: delay between two tries
389 L'affichage :epkg:`pygame` est optionnel.
390 """
391 if pos == 1:
392 for p in self.piece:
393 p.position = 0
394 self.nb_position = 0
395 self.essai = 0
397 self.essai += 1
399 if self.nb_position == len(self.piece):
400 time.sleep(0.2)
401 return None
403 # le tableau free mémorise l'ensemble des pièces non encore placées
404 free = []
405 for p in self.piece:
406 if p.position == 0:
407 free.append(p)
409 if screen is not None and pygame is not None and images is not None:
410 empty_main_loop(pygame, lambda: str(self))
411 display_puzzle_2(self, screen, True, pygame=pygame)
412 pygame.display.flip()
413 images.append(screen.copy())
415 p = self.meilleure_piece(free, pos)
416 # si p == None, on n'étudie pas les solutions avec les pièces placées
417 # avant aux positions 1 à pos --> on n'entrera pas dans la boucle
418 # suivante
419 while p is not None:
421 p.position = pos
422 angle = self.angle_possible(p)
424 # p est la pièce choisie, pour cette pièce
425 # on passe en revue toutes les orientations
426 for a in angle:
427 p.orientation = a
429 if pygame is not None:
430 pygame.time.wait(delay)
432 if self.nb_place() == 0:
433 return True
434 else:
435 r = self.solution(pos + 1, screen=screen,
436 pygame=pygame, images=images, delay=delay)
437 if r:
438 return True
440 p.position = 0
442 # on réactualise le tableau free qui aura été modifié par
443 # l'appel à self.solution et on enlève le choix précédemment
444 # testé
445 free2 = free
446 free = []
447 for f in free2:
448 if f.numero != p.numero:
449 free.append(f)
451 # on passe au choix suivant avec free contenant les pièces
452 # placées et les pièces essayées
453 p = self.meilleure_piece(free, pos)
454 return None
457def display_puzzle_2(self, screen, petite=False, pygame=None):
458 """
459 Affiche les pièces sur l'écran,
460 en plus petit pour celles qui ne sont pas encore placées.
461 """
462 screen.fill((0, 0, 0))
463 free = [0 for i in self.piece]
464 for p in self.piece:
465 if p.position > 0:
466 p.darker = False
467 display_puzzle_2_piece(
468 p, screen, self.pixel(p.position), pygame=pygame)
469 free[p.position - 1] = 1
471 if petite:
472 em = []
473 for i in range(0, len(free)):
474 if free[i] == 0:
475 em.append(i + 1)
476 i = 0
477 for p in self.piece:
478 if p.position == 0:
479 p.darker = True
480 display_puzzle_2_piece(
481 p, screen, self.pixel(em[i]), pygame)
482 i += 1
484 pygame.display.flip()
487def display_puzzle_2_piece(self, screen, position, pygame):
488 """
489 Affiche la pièce en tenant compte de sa position
490 et de son orientation.
491 """
492 if "darker" in self.__dict__ and self.darker:
493 position = (position[0] + 120, position[1] + 120)
494 image = pygame.transform.rotate(self.image_petite, self.orientation)
495 screen.blit(image, position)
496 else:
497 image = pygame.transform.rotate(self.image, self.orientation)
498 screen.blit(image, position)
501def pygame_simulation(pygame, first_click=False, folder=None,
502 size=(700, 700), fLOG=fLOG, delay=200,
503 flags=0):
504 """
505 Simulation graphique.
506 Illuste la résolution du puzzle
508 :param pygame: module pygame
509 :param first_click: attend la pression d'un clic de souris avant de commencer
510 :param folder: répertoire où stocker les images de la simulation
511 :param size: taille de l'écran
512 :param delay: delay between two tries
513 :param flags: see `pygame.display.set_mode
514 <https://www.pygame.org/docs/ref/display.html#pygame.display.set_mode>`_
515 :param fLOG: logging function
516 :return: @see cl Puzzle2
518 La simulation ressemble à ceci :
520 .. raw:: html
522 <video autoplay="" controls="" loop="" height="500">
523 <source src="http://www.xavierdupre.fr/enseignement/complements/puzzle_2.mp4" type="video/mp4" />
524 </video>
526 Pour lancer la simulation :
528 ::
530 from ensae_teaching_cs.special.puzzle_2 import pygame_simulation
531 import pygame
532 pygame_simulation(pygame)
534 Voir :ref:`l-puzzle_girafe`.
535 """
536 # initialisation du module pygame
537 pygame.init()
538 screen = pygame.display.set_mode(size, flags)
540 # on définit le puzzle
541 p = Puzzle2()
542 p.load_images(pygame)
544 # on affiche le puzzle avec print (format texte)
545 fLOG("\n" + str(p))
547 # on affiche le puzzle à l'écran
548 display_puzzle_2(p, screen, petite=True, pygame=pygame)
549 if first_click:
550 wait_event(pygame)
552 # on rafraîchit l'écran pour que le puzzle apparaissent
553 pygame.display.flip()
555 images = [] if folder is not None else None
557 # on trouve la solution
558 r = p.solution(screen=screen, pygame=pygame, images=images, delay=delay)
559 fLOG("résolution ", r)
560 fLOG("nombre d'appels à la méthode solution ", p.essai)
562 if images is not None:
563 empty_main_loop(pygame)
564 display_puzzle_2(p, screen, True, pygame=pygame)
565 pygame.display.flip()
566 images.append(screen.copy())
568 if folder is not None:
569 fLOG("saving images")
570 for it, screen in enumerate(images):
571 if it % 10 == 0:
572 fLOG("saving image:", it)
573 image = os.path.join(folder, "image_%04d.png" % it)
574 pygame.image.save(screen, image)
576 # on attend la pression d'un clic de souris avant de terminer le programme
577 display_puzzle_2(p, screen, petite=True, pygame=pygame)
578 if first_click:
579 wait_event(pygame)