Le Puzzle de l'Avent 2021
Posté le 01/12/2021 21:09
Salut à tous et bienvenue dans ce nouveau Puzzle de l'Avent ! 
Puzzle fini et résultats : article de Noël. 
Tileset et maps sont disponibles librement s'il y a des intéressés.
La première édition de ce puzzle était une
collection de petites énigmes, tandis que la seconde était faite de
petites curiosités mathématiques et informatiques. Cette année, je vous propose de refaire un tour sur des problèmes classiques d'informatique dans un contexte un peu vidéoludique !
J'ai eu un peu de mal à ajuster la difficulté la dernière fois, promis cette année les problèmes sont tous accessibles. Il y a même deux catégories : pour chaque petit problème je présenterai une version «facile» qui peut être résolue de tête ou avec un papier/crayon, et une version «difficile» qui nécessite un peu plus de réflexion, parfois du code. Il y aura des explications sur la nature des problèmes dans tous les cas, le but étant aussi de vous faire découvrir tout ce qu'on peut faire avec de l'informatique théorique.
Le but du jeu est de reconstituer le Puzzle dont les pièces seront données chaque jour. C'est un véritable puzzle séparé en deux parties. Chaque jour je vous donnerai une partie des pièces «brouillées» accompagnées d'un petit problème d'informatique. La solution du problème vous permettra de débrouiller les pièces et ainsi d'avancer le puzzle. À Noël, le puzzle sera complet !
Le puzzle est un pixel art de 198×112 pixels que j'ai fait pour l'occasion, et est séparé verticalement en deux comme ceci :
Il y a deux prix pour cet événement !
- Pour la reconstitution de la partie facile, une Graph 90+E est à remporter ;
- Pour la reconstitution de la partie difficile, une batterie portable CASIO est à remporter.
Ces lots sont généreusement offerts par
CASIO Éducation.
______
Pour plus d'informations sur la Graph 90+E (une machine magnifique !), regarde sa fiche « Tout sur ta CASIO ! ».
La batterie se charge par USB et fournit l'énergie par micro-USB ; capacité 2200 mAh.
Ah oui, et pendant que j'y pense tous les gens qui finissent (une moitié du) puzzle ont droit au titre de
Maître du Puzzle !
Voilà qui conclut l'exposé des règles pour cette année. On commence dès demain. Il y aura du puzzle, de l'informatique, du storytelling, et même un poil de pixel art et de jeu vidéo. Ne le manquez pas !
Liste des puzzles
Pour décoder les pièces, utilisez le script
decode_pieces.py. Enregistrez les images
Avent2021_Dec*r.png dans un dossier à côté de
decode_pieces.py, puis modifiez le script pour indiquer les solutions dans les tableaux
SOLUTION_EASY et
SOLUTIONS_HARD. Ensuite, lancez le script, et vous aurez les images décodées dans le même dossier.
Fichier joint
Citer : Posté le 03/12/2021 09:46 | #
C'était trop simple oui… 4 min pour trouver
Citer : Posté le 03/12/2021 10:26 | #
Variation difficile : pareil, mais dans un espace 5D
Citer : Posté le 03/12/2021 10:31 | #
AH ! easy… hum… ça ressemble a quoi du coup ?
Citer : Posté le 03/12/2021 11:01 | #
Un espace 5D ? Ça ressemble à ça : https://fr.wikipedia.org/wiki/Yahtzee
La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
Citer : Posté le 03/12/2021 18:52 | #
Explication du problème du 2 Décembre
Le problème d'hier est un problème de couverture d'ensembles. Il n'est pas formulé comme un des grands classiques (Set Cover et Exact Cover sont légèrement différents), mais il est dans la même lignée.
Vous pouvez le formuler comme ceci : étant donné un ensemble de cases à couvrir (les 36 cases praticables) et des sous-ensembles (chaque façon de placer un personnage sur la plateau), utiliser les sous-ensembles pour maximiser la quantité de cases couvertes.
Pour être très rigoureux, les sous-ensembles qui vous sont proposés sont toutes les façons de placer un des personnages sur une des cases. Le plateau faisant 8×8 = 64 cases, vous avez 64 sous-ensembles proposés par personnage, pour un total de 256 sous-ensembles. Vous devez les combiner pour maximiser la couverture des cases praticables, avec la contrainte que vous ne pouvez placer chaque personnage qu'à un seul endroit (si vous utilisez deux sous-ensembles Scarlet c'est de la triche !
J'ai mis en gras le «maximiser» pour montrer que c'est un problème d'optimisation, où on vous demande le résultat. Il existe un autre type de problèmes qu'on appelle des problèmes de décision, où il faut répondre vrai/faux. Un problème de décision similaire à celui d'hier aurait été par exemple «peut-on couvrir au moins 33 cases sur 36 ?». En général un même problème peut se formuler des deux façons, mais vous reconnaîtrez que si y'a que deux options pour décoder les pièces du puzzle ce sera pas un gros challenge.
Défense indépendante
Aujourd'hui je vous propose une variante difficile du problème d'hier, qui est cette fois un vrai problème de couverture. Voici le plateau :
Le ninja peut se clôner à l'infini, mais Alice, Scarlet et Delta non. Combien de personnages peut-on placer sur des cases praticables de la map sans qu'une cellule praticable ne soit couverte deux fois ?
Les personnages peuvent avoir des zones impraticables dans leur portée mais ils doivent se trouver sur des cases praticables. On peut mettre plusieurs personnages sur la même case tant que les portées ne s'intersectent pas. L'eau est impraticable évidemment...
Comme vous aurez probablement besoin de coder pour trouver la solution, voici le tableau écrit en Python.
MAP = \
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0,
0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0,
0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0,
0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0,
0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]
Pièces du puzzle
Ajouté le 03/12/2021 à 23:01 :
J'ai ajouté les pièces. J'étais un peu optimiste sur la taille de la map (c'est NP-complet cette broutille quand même !) donc j'ai réduit un peu, ça vous simplifiera la vie. Pour info mon script Python qui calcule la solution optimale prend 12 secondes... donc ça se fait
Citer : Posté le 04/12/2021 17:35 | #
La patrouille
Malgré tes efforts pour maximiser la surface couverte du champ de bataille, il reste encore pas mal d'options à des attaquants potentiels pour se faufiler entre les défenses. Il suffit d'un jour de mauvaise visibilité pour rater des bataillons, et tu ne doutes pas que l'ennemi en profitera.
Pour prendre ces fourbes par surprises, tu envoies δ faire des rondes dans toutes les cases non couvertes et attaquer les intrus sur son passage. Pour maximiser la protection, δ doit passer sur toutes les cases de forêt une seule fois et se retrouver à la fin de sa ronde à son point de départ, de sorte à pouvoir immédiatement recommencer son tour.
Voici la zone à parcourir :
Le but de ce problème est de trouver un chemin de ronde. Mais la solution ne serait pas un nombre entier, alors en plus de ça je vous demande de trouver le nombre minimal d'étapes pour atteindre Scarlet sur un chemin de ronde.
Il y a bien sûr plusieurs chemins possibles, et tous ne croisent pas Scarlet au même moment. Il faut bien trouver un chemin qui passe par Scarlet le plus tôt possible.
Pièces du puzzle
Indice sur le problème du 3 Décembre
Ce problème s'appelle Maximum Set Packing. Dans ce cas particulier, on peut prouver (en étudiant un peu ce à quoi ressemblent les solutions) que le nombre maximum de personnages qu'on peut caser est facilement trouvable à partir du nombre maximum de ninjas qu'on peut caser en ignorant Scarlet, Alice et δ.
Citer : Posté le 04/12/2021 19:10 | #
J'attends le jeu sur 90+E pour placer les différents personnages et voir le champ d'action
Le puzzle a l'air très beau, j'ai pu réussir les 3 jours pour l'instant. Comme d'habitude tu fais un boulot de malade, bravo !
(Et de toute façon, vous pouvez pas dire le contraire)
MultipliCasio
RDM Calculs
Back Mirror
A Switch To The Top C
Citer : Posté le 05/12/2021 15:08 | #
Explication du problème du 4 Décembre
Le problème d'hier consiste à trouver un chemin qui est un «cycle hamiltonien» ; «cycle» veut dire qu'on revient au point de départ et «hamiltonien» veut dire qu'on passe exactement une fois sur chaque case.
On pourrait croire à première vue que cette histoire de distance avec Scarlet complexifie le problème, parce qu'en principe il faut trouver tous les cycles hamiltoniens pour savoir lequel atteint Scarlet le plus tôt. C'est vrai. Mais pour un problème aussi simple où on cherche à la main, ça guide la résolution en privilégiant une direction, donc c'est plus une aide qu'autre chose
Le problème de déterminer s'il existe un cycle hamiltonien est difficile à lui tout seul, dans le sens où quand la map devient très grande il n'y a pas d'algorithme qui trouve la réponse rapidement. Plus spécifiquement, on le qualifie de «NP-difficile» ; ce que ça veut dire exactement est compliqué mais en gros le temps de calcul augmente exponentiellement avec la taille du graphe (ie. chaque fois qu'on rajoute une case ça démultiplie le temps de calcul !).
Pour le problème d'aujourd'hui j'ai fait l'erreur de vouloir donner le même qu'hier avec une map plus grosse, ce qui est une très mauvaise idée parce que le problème étant NP-difficile je n'arrivais pas à calculer la solution. J'ai changé d'idée du coup.
Tous les chemins mènent à Scarlet
Sur la map ci-dessous (même qu'hier), déterminer combien de chemins différents mènent à Scarlet. On veut des chemins simples, ie. on s'interdit de passer deux fois sur la même case.
Voici un petit code Python formalisant la map ; indice, vous aurez besoin de programmer, la réponse est un nombre à 6 chiffres
MAP = \
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0,
0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0,
0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0,
0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0,
0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0,
0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
INITIAL = 2+5*WIDTH
SCARLET = 10+4*WIDTH
Pièces du puzzle
Citer : Posté le 06/12/2021 20:42 | #
Distribution des rations
Avec les tours de ronde, vous savez maintenant que la région est sécurisée. Pas d'attaque en vue, c'est presque comme si l'armée ennemie était à court de moyens - ou alors elle prépare un gros coup, mais on espère que non.
Pour l'instant, le plan est de maintenir la défense tout en préparant une contre-attaque. Il faut donc laisser des troupes sur places, et gérer correctement la logistique pour qu'elles soient approvisionnées. Vu les moyens disponibles, il ne sera pas possible de tout protéger, mais on peut essayer de s'en approcher le plus possible.
La limitation principale est la nourriture. Un soldat consomme 4 rations de nourriture par semaine (les rations font plusieurs repas évidemment !) et peut défendre 2 cases du plateau. δ consomme 1 ration de nourriture par semaine et défend 1 case ; Alice, Scarlet et Ninja consomment chacun 6 rations par rations et ils défendent 8, 25 et 13 cases respectivement.
δ, Alice, Scarlet et Ninja peuvent rester en défense pour l'instant mais ils seront tous nécessaires à la future contre-attaque ; si on les laisse derrière, il faudra les rapatrier par véhicule le moment venu (chacun un véhicule, pour transporter leurs effets personnels x3).
Notre système d'approvisionnement peut fournir 50 rations de nourriture par semaine et 2 véhicules sont disponibles. Quelle est la surface maximale qu'on peut défendre ?
Pièces du puzzle
Citer : Posté le 07/12/2021 14:02 | #
Juste pour savoir, vous me conseilleriez quoi comme utilitaire pour refaire le puzzle ? (Je suis sous Linux)
À part ça, l'avent est très bien construit je trouve
Citer : Posté le 07/12/2021 14:06 | #
Perso je conseille de charger toutes les pièces dans des calques dans GIMP (Fichier » Ouvrir en tant que calques) et ensuite de les déplacer avec l'outil de déplacement de calque. Bon par contre faut découper les pièces initialement, peut-être qu'on peut faire plus pratique...
Je réalise que j'ai oublié de les faire tourner de façon aléatoire, je suppose que vous grattez ça pour cette année.
Citer : Posté le 07/12/2021 23:08 | #
Explication du problème du 6 Décembre
Le problème d'hier est un programme linéaire, un type de problème abstrait où on a plusieurs variables et on doit maximiser une «fonction linéaire» sous des «contraintes linéaires». En gros, le problème c'est ça :
Maximiser 2×soldats + 1×delta + 8×alice + 25×scarlet + 13×ninja (la surface défendue).
Avec comme contraintes sur le nombre de personnes :
0 ≤ soldats
0 ≤ delta ≤ 1
0 ≤ alice ≤ 1
0 ≤ scarlet ≤ 1
0 ≤ ninja ≤ 1
Comme contrainte sur le nombre de rations par semaine :
4×soldats + 1×delta + 6×alice + 6×scarlet + 6×ninja ≤ 50
Et sur le nombre de véhicules disponibles :
delta + alice + scarlet + ninja ≤ 2
En plus de ça on demande ici que les valeurs soient des entiers (on va pas découper les soldats !), ce qui en fait un problème de programmation linéaire entière. Pour des raisons que je détaille pas trop c'est plus difficile que si les variables sont des nombres réels (intuition : les nombres réels on peut toujours les ajuster très finement pour améliorer le score, mais les nombres entiers on ne peut pas, on est obligés de sauter de 1 en 1).
Logistique de guerre
Aujourd'hui on passe donc à l'échelle supérieure. Les «principautés» se réveillent en constatant que le danger existe et que vous, le gouvernement, ne les avez pas abandonnées. Elles vous fournissent des provisions, des soldats, et des cavaliers. Vous décidez donc de déployer des troupes sur l'ensemble du pays, mais comme les routes sont quasi-inexistantes les véhicules sont abandonnées au profit de chevaux. La situation est donc la suivante :
Et voici ce que fait chaque type d'unité :
Même question qu'hier : quelle est la surface maximale qu'on peut défendre ?
Notez que vous n'êtes pas obligés d'utiliser une méthode de résolution de programme linéaire entier pour ça (c'est beaucoup trop dur !), vous pouvez juste coder les règles et bruteforcer.
Pièces du puzzle
Citer : Posté le 08/12/2021 12:47 | #
Diplomatie de région (1/2)
L'absence de mouvement de l'ennemi est perçu par les dirigeants locaux comme un calme avant la tempête. Ils sont inquiets — ils l'ont toujours été — et voient en vous une organisation centrale peut-être capable de les défendre, ou en tous cas digne d'intérêt. Après des années de gestion indépendante, ils vous pensaient tous incapables de gouverner, mais en repoussant stratégiquement une première attaque vous avez bien défendu vos compétences.
Maintenant est le moment de recueillir, à défaut d'allégeance, leur coopération. Il a été décidé d'envoyer δ et Alice au à la Cité des falaises calcaires, un château surplombant la mer possédant un port en eau profonde, et donc de facto une «principauté» d'influence.
Le chemin est cependant assez ardu, comme vous pouvez le voir sur la carte ci-dessous. Les forêts sont relativement clairsemées donc praticables (de toute façon on n'a pas le choix), par contre les montagnes sont hors de question. Il y aussi beaucoup de marécages à cause des nombreux petits cours d'eau qui sillonnent les montagnes, alimentés par les précipitations du bord de mer.
Il faut à δ et Alice 1 heure pour parcourir une case de plaine, 3 heures pour parcourir une case de forêt, et 4 heures pour parcourir un marécage.
La question est la suivante : après combien de temps pourront-t-elles toute les deux entrer au château ?
Pièces du puzzle
Citer : Posté le 08/12/2021 13:15 | #
C'est vraiment dommage que j'ai pas de temps en ce moment pour le puzzle car tu t'es vraiment arraché Lephé.
Aussi bien l'histoire que les énigmes individuelles sont géniales.
Super !! Et bonne chance aux participants...
PS : pour les "SynchroDonjontistes", ca devrait être facile pour l'épreuve d'aujourd'hui
Citer : Posté le 08/12/2021 18:54 | #
Envoyer δ en mission diplomatique est une très mauvaise idée
Citer : Posté le 08/12/2021 20:24 | #
Envoyer δ en mission diplomatique est une très mauvaise idée
Oups. Euh, c'est pas grave, tout va bien se passer. Elle est avec Alice, qui est très communicat- wait
Citer : Posté le 08/12/2021 20:54 | #
Oups. Euh, c'est pas grave, tout va bien se passer. Elle est avec Alice, qui est très communicat- wait
Comment rater une mission diplomatique en trois étapes avec la mage Alice
*entre timidement dans la salle du trône*
*trébuche et tombe à terre*
*quite la salle en pleurant*
Citer : Posté le 09/12/2021 19:21 | #
Explication du problème du 8 Décembre
PS : pour les "SynchroDonjontistes", ca devrait être facile pour l'épreuve d'aujourd'hui
Comme SlyVTT l'a vite remarqué, le problème d'hier est un problème de plus court chemin, consistant simplement à trouver par quels chemins δ et Alice peuvent atteindre le château le plus vite.
C'est un problème ultra-classique de théorie des graphes, qui a des applications à peu près partout du GPS au routage d'Internet, et tout une variété d'algorithmes qui présentent tous des variations utiles dans différents contextes, parmi lesquels :
On pourrait passer des heures dessus, mais vous pouvez aussi chercher le chemin à la main, sur cet exemple ça va beaucoup plus vite.
Diplomatie de région (2/2)
Aujourd'hui je vous propose une variation de ce problème. La mission diplomatique est limitée, en plus des caractères particuliers de δ et Alice (x3), par la météo : il pleut. La pluie attendrit le sol en plaine, crée de la boue en forêt, et inonde les marécages, ce qui augmente le temps de trajet :
Le chemin est le même qu'hier :
Je vous demande de trouver deux valeurs. La première est la plus petite quantité d'eau (en mm) qui doit tomber pour que ni δ ni Alice ne passe par le col montagneux au centre de la map.
La seconde est l'unique quantité d'eau (en mm) pour laquelle δ et Alice se séparent et ne se retrouvent qu'au château.
La solution du puzzle est la concaténation de ces nombres, par exemple si la première réponse est 35 et la seconde 78 la solution sera 3578.
Pièces du puzzle
Citer : Posté le 10/12/2021 22:36 | #
Union sacrée
Alice et δ ont impressionné le duc des falaises calcaires ; c'est surtout la magie d'Alice qui les a cloués pour être honnête. Malgré leur économie maritime, ils sont très terre-à-terre... et quelques petites démonstrations les ont vite convaincu qu'ils seraient déjà en danger si le gouvernement venait taper à la porte, achevant l'opposition qui n'a pas trouvé mieux que de se moquer des invités trempés par la pluie.
Une coalition est en train de se mettre en place, et le bruit court qu'une «union sacrée» de toutes les principautés pourrait bien se profiler. D'ailleurs ça commence à être mal vu de dire «principauté» puisqu'un sens national commence doucement à renaître. L'opération est un succès, le pays reprend des couleurs !
Mais la coopération des villes et château ne suffit pas ; il faut aussi le support logistique derrière. Et l'état des routes sur tout le territoire est assez désastreux, avec seulement quelques-unes encore en état de fonctionner proprement. Le chemin qui sillonne les montagnes pour atteindre le village au Sud-Est, près de la frontière où a eu lieu la première bataille de cette épopée, est presque impraticable à cause de parties éboulées.
Avec tout ça, les temps de trajet entre les centres de population, les îles et les points stratégiques se comptent souvent en jours !
Un plan d'infrastructure est donc en discussion pour faire la liaison plus rapidement entre toutes les villes. Le but est de réduire le temps de trajet au nombre d'heures indiqué sur le plan suivant.
Bien sûr, toutes ces routes ne peuvent pas être construites ou rénovées en mêmes temps ; une fois les soldats réquisitionnés il ne reste clairement pas assez de main d'oeuvre. Le but est donc de connecter toutes les villes entre elles avec juste un minimum de routes. Comme du coup il faudra parfois faire des détours pour se rendre d'une ville à l'autre, on décide de se concentrer sur les routes les plus rapides.
Parmi tous les choix de routes qui connectent tous les points d'intérêt, trouvez-en un qui minimise la somme des durées. Cette somme est la solution au problème d'aujourd'hui.
Pièces du puzzle
Citer : Posté le 11/12/2021 12:59 | #
est-ce que je peux avoir un recapitulatif
je n'ai pas tout suivi
Citer : Posté le 11/12/2021 13:48 | #
Dans cet événement le but est de reconstituer un puzzle, dont je donne quelques pièces tous les jours (tu peux en voir juste au-dessus de ton message).
Les pièces que je donne sont brouillées, et pour les «dé-brouiller» il faut résoudre des petits problèmes d'informatique. Pour chaque problème la solution est un nombre ; quand tu as la solution tu peux la saisir dans un programme Python (qui est donné dans le post principal) et obtenir les pièces «dé-brouillées».
ll y a deux types de problèmes : des faciles et des difficiles, qui alternent tous les jours. Les pièces des problèmes faciles forment la moitié gauche du puzzle, tandis que les pièces des problèmes difficiles forment la moitié droite. Il y a un prix à gagner pour la première personne qui reconstituera la moitié gauche du puzzle et un autre pour la première qui reconstituera la moitié droite.
C'est plus clair comme ça ?