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 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.
Citer : Posté le 29/12/2023 14:00 | #
Merci beaucoup pour vos conseils
J'ai une question : maintenant que j'ai l'image du puzzle, je n'ai pas besoin de le reconstituer si ? Je donne juste les solutions aux problèmes pour que ma résolution soit correcte ?
Citer : Posté le 29/12/2023 14:26 | #
Oui puisque le puzzle est public tu gagnes dès que tu as toutes les solutions.
Citer : Posté le 29/12/2023 15:27 | #
j'ai une petite question: pour gagner la 90+E, il fallait résoudre le puzzle et le
machinprobleme du four?Citer : Posté le 29/12/2023 15:28 | #
Il faut résoudre tous les problèmes pour pouvoir décoder les pièces
Citer : Posté le 29/12/2023 15:29 | #
le probleme du mur, c'est le four?
Citer : Posté le 29/12/2023 15:32 | #
Le problème du mur c'est celui du 18/12. Je ne sais pas ce que tu entends par "le four", y'a des fours partout... x)
Citer : Posté le 29/12/2023 15:36 | #
Citer : Posté le 29/12/2023 18:28 | #
Traceback (most recent call last):
File "C:\Users\admin\PycharmProjects\test\puzzle avent.py", line 123, in <module>
assert i0.width == 210 and i0.height == 47
AssertionError
j'ai eu cette erreur quand j'ai lancé le script
Citer : Posté le 29/12/2023 18:30 | #
Hmm tu as un fichier du nom Avent2023_Dec*r.png qui n'est pas une image de taille 210x47. Toutes les images que j'ai fournies sont de cette taille. Peut-être que tu as une image qui s'est glissée dans le dossier mais qui n'est pas une paquet de pièces ?
Citer : Posté le 29/12/2023 18:31 | # |
Fichier joint
j'ai mis cette image:
Citer : Posté le 29/12/2023 18:37 | #
Il faut que tu télécharges l'originale en faisant clic droit dessus.
Citer : Posté le 30/12/2023 11:41 | #
Pour le dernier problème, combien de combinaisons différentes y'a t il ? Juste pour être sur que mon programme fonctionne correctement pour l'instant
Citer : Posté le 30/12/2023 11:55 | #
Si tu élimines les positions où un élément dépasse les bornes de l'espace de 9x8 et celles où le deuxième four/coffre arrive avant le premier four/coffre, il en reste 1092.
Citer : Posté le 30/12/2023 11:57 | #
Arrive avant le deuxième four/coffre : c'est à dire ? Je n'ai pas du tout compris l'idée...
Citer : Posté le 30/12/2023 12:00 | #
Les deux fours sont interchangeables, et les deux coffres aussi (si tu les positionnes avant de choisir leur orientation). Ce qui serait bien pour éviter les doublons c'est de ne pas avoir à la fois [four_a, coffre_a, four_b, coffre_b] et [four_b, coffre_a, four_a, coffre_b] parce que tu sais déjà que ce sera le même circuit optimal et le même nombre total de plaques.
Une façon très facile de faire ça est que tu ne testes que les configurations [four_a, coffre_a, four_b, coffre_b] pour lesquelles four_a < four_b, comme ça tu sais que si tu en trouves une alors l'autre (où tu échanges four_a et four_b) ne sera pas considérée.
C'est une optimisation importante pour ce problème parce que la simulation de 1000 minutes est déjà lente donc si en plus tu es obligé de la faire 10'000 fois tu risques de ne pas t'en sortir. Éviter le travail en double est important si tu veux avoir une solution en temps raisonnable.
Citer : Posté le 30/12/2023 12:10 | #
Mais le problème c'est que je ne peux pas faire ça pour les coffres vu qu'ils ont une orientation qui peut être différente, non?
Et les valeurs four_a et four_b elles représentent quoi ? leur positions ? mais dans ce cas là c'est des tuples, on peut comrarer des tuples comme ça ?
Citer : Posté le 30/12/2023 12:14 | #
Les valeurs four_a et four_b représentent en effet les tuples (x, y) ici. Tu peux les comparer comme ça oui, ça te donne l'ordre lexicographique :
(x, y) < (x', y') := (x < x') ou (x = x' et y < y')
Mais à la limite peu importe comment c'est défini, tout ce qui compte c'est que ça les compare dans un certain "ordre" et donc tu sais que si la comparaison est vraie dans un sens elle sera pas vraie dans l'autre.
Pour les coffres, l'astuce c'est que dans tes boucles tu peux d'abord itérer sur les positions des coffres, éliminer les positions redondantes avec coffre_a < coffre_b, et ensuite tu choisis l'orientation.
Citer : Posté le 30/12/2023 12:20 | #
Mais imaginons que j'ai un four à la position (0,0) (je considere que le coin en haut à gauche est le point de départ de chaque outil), si j'ai mon coffre a qui est en shape 1, je peux le placer à la position (4,3) car il a un espace vide qui ne gène pas le . du four. Alors que si mon coffre est en shape 2 la je ne peux pas le placer à la possition (4,3) car le # ne peut pas se mettre avec le . Donc comment gérer ce genre de cas si j'itere d'abord sur le positions et que après je change les shapes ? Ou alors je revérifie à chaque fois que je change la shape si mon positionnement est valide... Je ne sais pas...
Citer : Posté le 30/12/2023 12:30 | #
Yup, tu vérifies à chaque fois. La technique de base c'est : j'énumère toutes les positions "raisonnables" (ie. où ça dépasse pas des bornes de 9x8 et en esquivant les doublons), ensuite je teste chaque position en détail pour savoir s'il y a une collision, et si y'a pas de collision je fais la simulation complète.
Citer : Posté le 30/12/2023 14:53 | #
Tu me dis :
Mais à la limite peu importe comment c'est défini, tout ce qui compte c'est que ça les compare dans un certain "ordre" et donc tu sais que si la comparaison est vraie dans un sens elle sera pas vraie dans l'autre.
Mais tu dis aussi dans l'énoncé que la solution est hors de toute symétrie. Mais du coup si je fait f1>f2 pour la comparaison est que dans la solution f2>f1, mon algorithme ne testera jamais la solution. Je fait quoi ?