Coverage for src/ensae_teaching_cs/special/puzzle_2.py: 90%

243 statements  

« prev     ^ index     » next       coverage.py v7.1.0, created at 2023-01-27 05:44 +0100

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""" 

7 

8import time 

9import os 

10from textwrap import dedent 

11from pyquickhelper.loghelper import fLOG 

12from ..helpers.pygame_helper import wait_event, empty_main_loop 

13 

14 

15class Puzzle2Bord: 

16 """ 

17 Définition d'un bord ou côté d'une pièce, il possède deux couleurs. 

18 """ 

19 

20 def __init__(self, definition): 

21 """ 

22 :param definition: chaîne de caractères 

23 

24 *definition* est une chaîne de 2 caractères qui définit un bord, exemple : 

25 

26 * ``RG`` for rouge vert (red, green) 

27 

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) 

37 

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) 

44 

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]) 

52 

53 

54class Puzzle2Piece: 

55 """ 

56 Définition d'une pièce du puzzle, celle-ci inclut : 

57 

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 

67 

68 Pour l'affichage, on ajoute deux informations : 

69 

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 """ 

74 

75 def __init__(self, name, definition, position, numero): 

76 """ 

77 On définit la pièce: 

78 

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 

85 

86 A partir de ces informations, on construit : 

87 

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 = [] 

95 

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])) 

99 

100 self.orientation = 0 

101 self.position = position 

102 self.numero = numero 

103 

104 def load_image(self, pygame): 

105 """ 

106 Charge l'image pour une simulation graphique. 

107 

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))) 

115 

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 

132 

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 à : 

137 

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] 

147 

148 

149class Puzzle2: 

150 """ 

151 Définition d'une classe puzzle, elle contient simplement 

152 une liste de 9 pièces dont les positions sont: 

153 

154 :: 

155 

156 5 

157 6 1 2 

158 4 3 7 

159 8 

160 

161 et les orientations choisies dans l'ensemble ``{ 0, 90, 180, 270 }`` 

162 

163 Voir :ref:`l-puzzle_2`. 

164 """ 

165 

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 : 

170 

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 : 

174 

175 :: 

176 

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") 

188 

189 with open(os.path.join(dir_, "definition_puzzle_2.txt"), "r") as f: 

190 bo = f.readlines() 

191 

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) 

201 

202 def load_images(self, pygame): 

203 """ 

204 Charge les images pour une simulation graphique. 

205 

206 :param pygame: module :epkg:`pygame` 

207 """ 

208 for p in self.piece: 

209 p.load_image(pygame) 

210 

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 

226 

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. 

231 

232 :return: `tuple(x,y)` 

233 

234 :: 

235 

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) 

253 

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] 

263 

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 

272 

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. 

278 

279 :: 

280 

281 5 

282 6 1 2 

283 4 3 7 

284 8 

285 

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}.") 

308 

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 

318 

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 

350 

351 b1 = piece.bord_angle(a1) 

352 b2 = p.bord_angle(a2, a) 

353 return b1.compatible(b2) 

354 

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 

376 

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). 

382 

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 

388 

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 

396 

397 self.essai += 1 

398 

399 if self.nb_position == len(self.piece): 

400 time.sleep(0.2) 

401 return None 

402 

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) 

408 

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()) 

414 

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: 

420 

421 p.position = pos 

422 angle = self.angle_possible(p) 

423 

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 

428 

429 if pygame is not None: 

430 pygame.time.wait(delay) 

431 

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 

439 

440 p.position = 0 

441 

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) 

450 

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 

455 

456 

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 

470 

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 

483 

484 pygame.display.flip() 

485 

486 

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) 

499 

500 

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 

507 

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 

517 

518 La simulation ressemble à ceci : 

519 

520 .. raw:: html 

521 

522 <video autoplay="" controls="" loop="" height="500"> 

523 <source src="http://www.xavierdupre.fr/enseignement/complements/puzzle_2.mp4" type="video/mp4" /> 

524 </video> 

525 

526 Pour lancer la simulation : 

527 

528 :: 

529 

530 from ensae_teaching_cs.special.puzzle_2 import pygame_simulation 

531 import pygame 

532 pygame_simulation(pygame) 

533 

534 Voir :ref:`l-puzzle_girafe`. 

535 """ 

536 # initialisation du module pygame 

537 pygame.init() 

538 screen = pygame.display.set_mode(size, flags) 

539 

540 # on définit le puzzle 

541 p = Puzzle2() 

542 p.load_images(pygame) 

543 

544 # on affiche le puzzle avec print (format texte) 

545 fLOG("\n" + str(p)) 

546 

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) 

551 

552 # on rafraîchit l'écran pour que le puzzle apparaissent 

553 pygame.display.flip() 

554 

555 images = [] if folder is not None else None 

556 

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) 

561 

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()) 

567 

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) 

575 

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)