Le Puzzle de l'Avent 2023
Posté le 01/12/2023 23:05
Bienvenue, cette année encore, dans le Puzzle de l'Avent de Planète Casio. 
Le Puzzle est presque une tradition maintenant, je n'en fais pas toutes les années (
2018,
2019,
2021) mais c'est un des événements que j'apprécie le plus. J'espère que c'est le cas pour vous aussi parce qu'il y a de quoi bien s'amuser !
Aux dernières éditions, on a exploré quelques problèmes d'informatique théorique — avec des graphes, des ensembles, de l'optimisation... cette année on va faire un peu différent : on va prendre un approche un peu plus pratique avec des problèmes que vous pouvez résoudre en
programmant. Parfois vous pourrez calculer la solution de tête, d'autres fois vous pourrez écrire un petit programme Python qui fera le calcul pour vous. On n'aura pas de problème très difficile cette année donc vous devriez vous en sortir même avec des programmes naïfs ou peu optimisés. Seul le tout dernier problème sera un peu dur, pour éviter que ce soit la course au premier connecté le 25 pour finir le puzzle. :3
Le but du jeu est de reconstituer un Puzzle dont les pièces seront données chaque jour. Le puzzle en lui-même est une image en pixel art de 198×112 pixels, juste ce qu'il faut pour tenir à l'écran d'une Graph 90+E. Comme dans la formule précédente, les pièces seront données chaque jour «brouillées» et pourront être débrouillées en calculant (ou faisant calculer à un programme) la solution d'un petit problème mathématico-informatique.
Conformément à la tradition, il y a un prix à gagner pour la première personne à reconstituer le puzzle : une
calculatrice Graph 90+E. Pour ceux d'entre vous qui n'ont pas le plaisir d'en posséder une, je ne peux que la recommander ; pour preuve depuis que j'ai commencé à jouer avec je suis pas revenu aux mono. :P
Ce lot provient de notre partenariat avec
CASIO Éducation.
Plus d'informations sur la Graph 90+E dans sa fiche « Tout sur ta CASIO ! ».
L'autre lot bien sûr c'est que toutes les personnes qui finissent le puzzle se voient attribuer le titre de
Maître du Puzzle.
Comme j'ai encore quelques détails à ajuster, le premier problème sera donné demain avec le premier ensemble de pièces. Préchauffez vos éditeurs d'images et de code Python !
---
Notes du futur :
Le puzzle a été résolu par :
Citer : Posté le 25/12/2023 17:45 | #
Et voici le dernier problème de ce puzzle ! J'espère que vous aurez pris autant de plaisir à le résoudre que moi à le construire.
Comment soumettre sa participation
En vous connectant à votre compte, envoyez-moi un message privé dans lequel vous indiquerez bien :
Il n'est pas nécessaire d'avoir absolument tout juste au pixel près sur le puzzle, surtout vu que l'image est chargée et les détails sont pas toujours faciles à distinguer. Pour éviter tout biais dans mon évaluation, les participations seront considérées valides s'il y a 6 pièces ou moins dont des pixels diffèrent de l'original, et les dates d'envoi des messages privés font foi. J'espère que ces conditions satisfont vos attentes d'équité pour la compétition.
Je contacterai plus tard le ou la gagnant·e pour planifier l'envoi du lot et en particulier demander vos coordonnées postales.
Travail manuel #3
Ce problème est la suite et fin du problème travail manuel du 14/15 Décembre. Dans Travail Manuel #1 et #2, on a cherché un circuit pour déplacer manuellement des plaques de métal entre des fours et coffres pré-positionnés de façon à minimiser le temps perdu durant lequel les fours attendaient qu'on vienne chercher les plaques.
Bien sûr, le positionnement proposé des fours et coffres n'était pas parfait : il suffisait de les rapprocher pour augmenter l'efficacité. Dans ce problème, on cherche à déterminer quel est le positionnement idéal. L'image et le code ci-dessous indiquent l'emprise au sol de chaque four ou coffre.
[" ###",
"#####",
" ##o#",
" ..."]
SHAPE_CHEST_1 = \
[" . ",
".o.",
"###"]
SHAPE_CHEST_2 = \
["###",
".o.",
" . "]
Il n'y a qu'une seule disposition possible pour les fours (SHAPE_FURNACE) mais il y a deux options pour les coffres (SHAPE_CHEST_1 et SHAPE_CHEST_2) selon si on met le tapis roulant au-dessus ou en-dessous. Dans chaque forme, les "#" représentent des cases occupées, le "o" représente le point où on interagit avec le four/coffre (i.e. les coordonnées dans le tableau STATIONS du 14/15 Décembre - c'est un type de case occupée), et les "." représentent des espaces qui doivent rester libres autour du point d'interaction.
On veut placer deux fours et deux coffres dans l'usine de taille 9x8, c'est-à-dire choisir la disposition qui était précédemment donnée sous la forme du tableau STATIONS (pour rappel l'ordre c'est un four, un coffre, un four, un coffre). Un placement est valide si les fours/coffres ne se superposent pas, c'est-à-dire s'il n'y a aucune case qui est utilisée en même temps par deux objets différents (sauf si c'est deux ".").
Une fois les objets placés, on se retrouve dans le formalisme du 14/15 Décembre. En particulier, on imagine qu'on se déplace en ligne droite entre les points d'interactions : on ignorera complètement tous les murs. Votre code pour Travail Manuel #1 et #2 doit être utilisable tel quel.
Votre mission est de déterminer quelles sont la meilleure disposition et la meilleure stratégie de parcours (circuit) de longueur au plus 8 sur 1000 minutes. Vous devez donc trouver toutes les dispositions valides de deux fours et deux coffres, pour chacune d'entre elles faire la résolution du 14/15 Décembre, et retenir la disposition qui maximise le nombre total de plaques collectées.
La solution de ce problème est la séquence formée des chiffres du nombre maximum de plaques collectées, des positions des fours/coffres (x puis y dans l'ordre du tableau STATIONS), et des chiffres du circuit. Par exemple, si les stations optimales sont [(0, 3), (1, 0), (4, 2), (7, 1)], le circuit optimal est [0, 1, 2, 3, 2, 0] et le total est 150, la solution sera 15003104271012320.
Quelques indices pour vous guider :
Bon courage !
Pièces finales du puzzle
Citer : Posté le 25/12/2023 17:52 | #
Jamais j'aurai fini avant les autres… j'ai encore que le premier jour de fait.
Bonne chance aux autres.
Citer : Posté le 25/12/2023 18:02 | #
Pfiou, il est pas facile le final
Citer : Posté le 26/12/2023 09:53 | #
Eeeet léger détail la grille pour le dernier problème est de taille 9x8. Je sais pas comment j'ai pu oublier ça. >_<
Citer : Posté le 26/12/2023 10:05 | #
Forcément ça va limiter les possibilités, sinon on a une infinité de solutions équivalentes par translation 😜
Citer : Posté le 27/12/2023 14:06 | #
N'hésitez pas à me demander par MP si vous approchez. Il y a sans doutes des imperfections dans l'explication.
Citer : Posté le 27/12/2023 15:19 | #
Pour le problème du 21/12, je ne trouve pas les dimensions du four et des tapis roulants
Résoudre le problème sans ces dimensions est possible ?
Citer : Posté le 27/12/2023 22:54 | #
Pour le problème du 21/12, je ne trouve pas les dimensions du four et des tapis roulants
Résoudre le problème sans ces dimensions est possible ?
Si je ne me trompe pas, le four fait 3×3 et les tapis roulants font 2×1 ou 1×2.
Il y a assurément besoin de ces dimensions pour résoudre l'énigme.
Bonne chance !
Citer : Posté le 28/12/2023 10:31 | #
Pour le problème du 21/12, je ne trouve pas les dimensions du four et des tapis roulants
Résoudre le problème sans ces dimensions est possible ?
Je confirme, le four fait 3x3, les tapis roulants font 1x1 chacun (et donc à côté soit 2x1 soit 1x2) et les bras mécaniques font 1x1 chacun.
---
Bon ce n'était qu'une question de temps avant que je me plante vraiment ! Dans le problème du 25 j'ai encodé les pièces en utilisant non pas les coordonnées des stations (i.e. des points d'interaction) mais les coordonnées des coins haut gauche de chaque élément, parce que mon script fonctionne comme ça.
Les images précédentes étaient donc encodées avec le bon total et le bon circuit mais des coordonnées décalées de (-3, -2) pour les fours et (-1, -1) pour les coffres. J'ai ré-encodé les images avec les bonnes coordonnées, et je vous les remets ci-dessous.
Comme la compétition n'est pas encore finie (personne n'a reconstitué le puzzle), je ne voudrais pas que cette erreur impacte négativement votre recherche précédente. Si par un miracle vous aviez décodé les pièces précédentes, ce sera accepté à condition que vous ayez correctement calculé le nombre total de plaques. Si vous avez une solution candidate, vous êtes toujours invité·es à m'envoyer un MP pour valider les détails qui peuvent rester.
Encore désolé pour ce plantage.
Citer : Posté le 28/12/2023 10:40 | #
Du coup tu retiens pas ma proposition ? Ou c’est faux ?
Citer : Posté le 28/12/2023 10:45 | #
Ta proposition n'est pas correcte car le total n'est pas optimal et ta disposition a clairement un four et un coffre en superposition.
Citer : Posté le 28/12/2023 11:52 | #
Eeet finalement deux soumissions valides quasi en même temps !
Maîtres du puzzle (pour l'instant)
On tient donc notre gagnant Afyu, félicitations !
Et du coup j'ai le plaisir de pouvoir vous dévoiler enfin le puzzle complet de cette année.
Toutes les soumissions sont bien sûr encore acceptées, prenez juste soin de m'envoyer votre liste de réponses. Le titre de Maître du puzzle sera décerné à tous les participants qui parviennent au bout, un club encore exclusif avec seulement 8 personnes sur 4 éditions.
Citer : Posté le 28/12/2023 14:47 | #
C'est qui/quoi dans le fond sur la montagne ?
Citer : Posté le 28/12/2023 14:55 | #
Félicitations @Afyu, chapeau @SlyVTT, et bravo également à tous les autres participants !
Citer : Posté le 28/12/2023 15:36 | #
Bravo @Ayfu
Bravo à toi aussi @SlyVtt, pour 10 min c'est dommage
Et enfin : bravo et merci à Lephe' pour ce travail de dingue
Citer : Posté le 29/12/2023 03:42 | #
Salut, pour le problème de "rénitialisation", je trouve une solution avec 9 actions qui n'est pas la bonne. Est ce que j'ai le droit de savoir combien d'actions contient la bonne solution
Citer : Posté le 29/12/2023 08:45 | #
Salut Dimartino,
la solution fait 11 actions.
as tu bien pensé à relancer le four ?
Citer : Posté le 29/12/2023 10:45 | #
C'est qui/quoi dans le fond sur la montagne ?
Ç'a été discuté sur l'autre topic (ici + la réponse), c'est Drakalex007.
Bravo à toi aussi @SlyVtt, pour 10 min c'est dommage
Et enfin : bravo et merci à Lephe' pour ce travail de dingue
Plus je le regarde plus je réalise que c'est pas facile (j'ai peut-être encore visé trop haut !) donc c'est probable que je décerne les titres après le 1er Janvier (eg. jusqu'au 31 Janvier), s'il y a des intéressés.
Merci à toi, c'était beaucoup de l'improvisation ultimement, j'espère que l'an prochain j'aurai plus le temps de préparer. ^^"
Citer : Posté le 29/12/2023 11:25 | #
Salut Dimartino,
la solution fait 11 actions.
as tu bien pensé à relancer le four ?
Merci
Citer : Posté le 29/12/2023 11:32 | #
Ah Bravo !!!
Honnêtement la dernière épreuve est compliqué dans le sens où il faut vraiment "cloisonner" la résolution et faire étape par étape :
1/ pour une configuration donnée de la carte, il faut avoir le code du 14/12 et 15/12 qui fonctionne pour trouver le nombre de plaques et le chemin optimum
2/ il faut trouver toutes les combinaisons possibles pour ensuite les injecter dans la partie 1/
3/ quand on a la solution, bien tout arranger le code pour obtenir la clef qui décode tout
Citer : Posté le 29/12/2023 13:46 | #
[Maintenant c'est bon il ne me reste plus que le 24 !
Courage ! Tu PEUX le faire !
J'ajouterai aux indications données par Slyvtt qu'il faut s'assurer que ton calcul de distance répond bien aux exigences de l'énoncé (en particulier l'arrondi par excès). Ce n'était pas mon cas pour la résolution du problème du 15/12 mais ça n'était pas bloquant non plus, alors que ça l'était pour certaines dispositions du problème du 25/12.