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 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 ?
Citer : Posté le 30/12/2023 16:04 | #
Excellente question. La réponse est que la solution a bien f1 < f2, ce qui était indiqué (mais peut-être d'une façon trop obscure) dans l'énoncé :
Citer : Posté le 30/12/2023 18:05 | #
Ah oui, je n’avais rien compris
Merci beaucoup
Citer : Posté le 30/12/2023 19:35 | #
Et du coup il faut que je le fasse aussi pour les coffres ? Mais du coup c'est aussi c1<c2 ?
Citer : Posté le 30/12/2023 19:41 | #
Oui les 4 stations sont dans l'ordre croissant (ie. f1 < c1 < f2 < c2), ce qui est encore un petit indice en plus.
Citer : Posté le 31/12/2023 10:43 | #
Ok merci c'est sympa
J'aimerai bien réussir à finir avant le nouvel an mais c'est pas gagné...
Citer : Posté le 01/01/2024 16:37 | #
On est bien d'accord que pour la superposition des outils, il y n'a que 8 cas qui déclenchent une erreur :
1) # et #
2) # et o
3) o et #
4) o et o
5) # et .
6) . et #
7) o et .
8) . et o
Je n'en oublie pas ?
Citer : Posté le 01/01/2024 16:38 | #
C'est ça. En termes de superposition o et # sont pareils et ensuite tout est en conflit sauf . avec ..
Citer : Posté le 01/01/2024 16:47 | #
Ok merci beaucoup !
Citer : Posté le 01/01/2024 17:28 | #
Courage Dimartino, tu vas y arriver !!
Citer : Posté le 01/01/2024 17:29 | #
Merci
Citer : Posté le 01/01/2024 17:32 | #
Merci
L'ordre lexicographique concerne les abscisses OU les ordonnées (dans le cas où les abscisses sont égales). Il ne faut pas restreindre à la fois sur les abscisses ET les ordonnées. Sinon tu as un coffre en haut à gauche et un autre en bas à droite et ça exclut les cas où le premier est en bas à gauche et le deuxième en haut à droite.
Je sais pas si c'est clair. Et je ne sais pas si c'est le souci de ton algorithme, mais je me suis fait avoir, alors je sais que ça peut arriver xD
Citer : Posté le 01/01/2024 17:35 | #
Oui les 4 stations sont dans l'ordre croissant (ie. f1 < c1 < f2 < c2), ce qui est encore un petit indice en plus.
C'est de ça que tu parles ? Il ne faut pas que j'écrive ça dans mon code donc ? Juste avec les abscisses ou juste avec les ordonnées ?
Citer : Posté le 01/01/2024 17:46 | #
Dimartino : le 1092 combinaisons c'est en tenant compte que f1 < f2 et c1 < c2, mais sans tenir compte de la contrainte f1 < c1 et f2 < c2. Si j'ajoute ces deux contraintes je n'en trouve que 153.
Citer : Posté le 01/01/2024 18:26 | #
Je me rapproche j'ai 1035 combinaisons possibles en changeant la position de mon return True et en tenant compte de ce que m'ont dit ayfu et Lephe' :
if f1x < f2x and c1x < c2x or f1y < f2y and c1y < c2y
Citer : Posté le 01/01/2024 18:38 | #
Je me rapproche j'ai 1035 combinaisons possibles en changeant la position de mon return True et en tenant compte de ce que m'ont dit ayfu et Lephe' :
if f1x < f2x and c1x < c2x or f1y < f2y and c1y < c2y
Ce serait même :
Citer : Posté le 02/01/2024 13:46 | #
Mais, quand j'utilise ce que tu me donne là je ne trouve plus que 631 solutions. Doit y'avoir un problème dans mon code
Citer : Posté le 02/01/2024 17:25 | #
Mais attendez, chez moi la simulation du 15 décembre prend une bonne vingtaine voire trentaine de secondes. Donc la résolution du 24 va prendre 30 x 1000 = 30000 secondes = 8,3 h
Citer : Posté le 02/01/2024 18:09 | #
Héhé oui y'a cette partie du problème haha. :P Tu peux utiliser pypy pour exécuter plus vite mais dans l'ensemble l'optimisation reste une partie du défi. Dans mon cas la simulation d'origine prend ~0.7 seconde et le programme du 25 prend environ 15 minutes.
Une idée utile pour la simulation c'est d'au lieu la faire minute par minute tu peux la faire déplacement par déplacement.
Sinon tu peux aussi prendre ton mal en patience et attendre 8 heures (de préférence en sauvegardant les résultats intermédiaires pour pouvoir le faire en plusieurs fois).
Citer : Posté le 02/01/2024 22:01 | #
J'ai réussi !!!!!!!!! Enfiiiiiiinnnnnnnn
Citer : Posté le 02/01/2024 22:02 | #
Lephe' je t'envoie un MP