Ces factures qu'on reçoit par courrier...

Publié le par Étienne

Elles sont une source inépuisable de papier brouillon pour coucher les sur papier les idées d'algorithmes, de formules, de schémas ou, parfois, de poèmes qui me passent par la tête :

Cette enveloppe contient une facture
Cette enveloppe, que je me suis bien gardé d'ouvrir avant d'avoir tiré le maximum de l'algorithme que j'y avais inscrit (notez que je réfléchis en couleur !), contenait si ma mémoire est bonne le relevé de compte de la copropriété.

De quoi s'agit-il ? D'un algorithme permettant de déduire l'ensemble des cases sur lesquelles une pièce d'échecs a dû effectuer des captures et de grouper ces captures selon leur ordre d'apparition dans la séquence de coups. Lecteur assidû, si la suite ne t'intéresse pas, je ne t'en tiendrai pas rigueur... sauf Pascal, puisque je l'ai écrit pour toi !

En entrée :
  • Une case de départ et une case d'arrivée;
  • Un graphe orienté représentant les déplacements possibles;
  • La précision, pour chacun de ces déplacements, si une capture est requise pour effectuer ledit déplacement.
Contraintes :
  • Se rendre de la case de départ à la case d'arrivée en utilisant le nombre minimal de captures.
  • Grouper les captures par ordre d'apparition dans les trajets possibles.

Le dessin sur l'enveloppe représente un situation hypothétique où un pion blanc en e2 voudrait se rendre en d8, les cases e4 et d6 étant inacessibles. Trois captures sont requises. La première doit avoir lieu sur les cases d3, d4, f3 ou f4, la deuxième sur c4, c5, c6, e5, e6 ou e7 et la troisième sur d7 ou d8. Ces groupes sont grossièrement délimités par les cercles roses.

Le dessin représente également l'algorithme qui sera utilisé pour déduire les cases :
  1. Construction d'un graphe orienté des trajets possibles à partir de la case de départ en respectant la contrainte de minimalité du nombre de captures. Cette contrainte explique par exemple pourquoi le pion e2, sur le schéma, ne peut se rendre de g4 en f5 car ce déplacement impliquerait trois captures (e2xf3xg4xf5) alors que la case f5 peut être atteinte à l'aide d'une seule capture.
  2. Parcours de ce graphe à l'envers, à partir de la case d'arrivée, en marquant toutes les cases visitées. Sur le schéma, les cases visitées sont marquées par les flèches bleues et les autres par les flèches vertes.
  3. Parcours de toutes les cases visitées afin de lister les captures. Comme on connaît le nombre de captures requises pour chaque case, il est possible de grouper les captures par leur ordre d'apparition dans les trajets.
Un peu plus de 100 lignes de code (grâce à std::priority_queue) et le tour est joué ! C'est l'enveloppe qui sera déçue de se retrouver à la poubelle...

Publié dans Silicium

Pour être informé des derniers articles, inscrivez vous :
Commenter cet article
J
tout cela est fort intéressant... on a en anglais un qualificatif fort adapté pour les personnes qui parviennent comme toi à se passionner pour ce genre de choses totalement incompréhensibles : nerd :-)
(je plaisante bien sûr - je suis même assez fascinée par ta polyvalence... poésie et algorithmes? je suis sûre que c'est assez inédit comme combinaison)
bisous!
julielagirafe
Répondre
Ã
Je me demande lequel de nous deux en ce moment se passione le plus pour des trucs incompréhensibles !!