Coverage for src/ensae_teaching_cs/special/puzzle

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

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)

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

243 statements