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 17/12/2023 13:20 | #
Salut, moi je suis toujours bloqué sur le 6/12 et j'ai pas envie de continuer tant que je l'ai pas fini, donc je commence à prendre du retard. Mais j'avance et je pense que j'aurais fini le 6/12 ce weekend normalement.
Sinon, c'est vraiment incroyable Lephe'
Citer : Posté le 17/12/2023 20:28 | #
Merci pour les retours. Le puzzle est un peu "punitif" dans le sens où il faut avoir fini tous les problèmes pour avoir toutes les pièces donc tout problème non fini vous empêche de tourner en rond. Je vous propose de me calmer pendant quelques jours pour vous laisser le temps de digérer les problèmes existants.
En fait je me fais moyennement confiance pour poser des problèmes raisonnables. x) Pour contexte même les problèmes "difficiles" posés jusqu'à présent sont genre "moyen" au pire dans ma tête (ie. "c'est l'affaire de 30 minutes"), alors que sans avoir les bons algos des fois c'est la dèche.
Donc à la place je vais prendre un peu de temps pour répondre aux questions / aider sur les problèmes précédents. Et voici aussi des pièces pour aujourd'hui.
Pièces du puzzle
La "combinaison" est un piège - en fait la contribution de chaque module est la même peu importe qui tu mets avec. C'est comme si je te demande de trouver les 4 nombres parmi {3, 5, 6, 8, 12, 19} dont la somme est maximal. Il suffit de choisir les quatre plus grands de façon indépendante.
J'ai pas pu vraiment avancer, ma résolution du 2nd est pas encore finie (
Si tu bloques n'hésite pas à demander.
Salut, moi je suis toujours bloqué sur le 6/12 et j'ai pas envie de continuer tant que je l'ai pas fini, donc je commence à prendre du retard. Mais j'avance et je pense que j'aurais fini le 6/12 ce weekend normalement.
Yup c'est un peu ma faute là. Je te montrerais bien comment coder le bon algorithme mais j'aime pas dire aux gens "la solution c'est de jeter ton code et faire ça à la place". Du coup t'es un peu coincé avec un code compliqué. Hésite pas à faire des aller-retours par MP vu que de toute façon t'as trouvé toutes les idées importantes et faut juste simplifier le code pour chasser les bugs...
Citer : Posté le 17/12/2023 20:32 | #
Enfin techniquement oui je "bloque" mais c'est que j'avais commencé à l'arrache ma résolution, et puis après j'avais plus de temps, je m'y suis pas remis tout ça
Mais oui comme tu le dis, je pense que avec mon savoir de 1ère spé math la résolution des quelques derniers est une question de plus de 30mn, par brute force informatisée ou non
Caltos : G90+E, FX-92+ (x2)
Citer : Posté le 17/12/2023 21:18 | #
Merci Lephé, c'est Easy Money ce soir
Bon du coup je vais travailler à me ruiner le cerveau sur la SDL2 plutôt que sur le Puzzle de l'Avent
Joli le Yatis Ninja Volant
Par contre j'arrive toujours pas à comprendre ce que c'est que cette forme sombre en haut à droite.
Tu nous tiens en haleine.
PS : rude la phase 2 d'hier ...
Citer : Posté le 18/12/2023 08:29 | #
En tout cas, c'est super cool que même avec le niveau en maths d'un début de 2nd, tout les problèmes sont possibles
P.S : @Lephe, pour le 6/12, j'ai recommencé de zéro toute la partie trop compliqué, donc je vais voir
Citer : Posté le 18/12/2023 21:39 | #
Aujourd'hui toujours chill pour vous permettre de rattraper votre retard potentiel. Mais certains d'entre vous (que je ne nommerai pas) insistent pour avoir un problème, et faut pas me provoquer. :P
Les pièces de ce problème seront données déjà décodées demain le temps que les tryharders se calment.
Vous l'aurez cherché #1
On veut construire un joli mur rectangulaire à partir de briques de taille 2x1 et 3x1. Un mur est considéré "joli" s'il n'y a pas deux jointures verticales alignées entre une rangée et la suivante. Par exemple, le mur ci-dessous est joli car chaque jointure de brique tombe au milieu d'une brique sur la ligne en-dessous.
Déterminer le nombre de murs jolis de taille 34x12.
Pièces du puzzle
Citer : Posté le 18/12/2023 21:43 | #
C'est cool de laisser le temps de rattraper le retard
Sinon, merci beaucoup pour l'aide sur le 6/12
Citer : Posté le 18/12/2023 21:52 | #
Aujourd'hui toujours chill pour vous permettre de rattraper votre retard potentiel. Mais certains d'entre vous (que je ne nommerais pas) insistent pour avoir un problème, et faut pas me provoquer. :P
Les pièces de ce problème seront données déjà décodées demain le temps que les tryharders se calment.
Tu parles de qui XD.
Visiblement c'est costaud là !!
Citer : Posté le 18/12/2023 22:44 | #
J'avais pas vu le titre du problème en plus
Citer : Posté le 19/12/2023 21:09 | #
Et hop voici les pièces d'hier déjà décodées comme promis. Pour info le problème en question est vraiment dur si vous n'avez que votre intuition pour vous guider ; le bruteforce naïf est hors de question puisque le résultat est un nombre à 19 chiffres. Le mot clé est programmation dynamique.
N'hésitez pas à me tenir au courant de vos progrès pour que je sache si je reprends dès demain ou si j'attends plus.
Pièces du puzzle
Citer : Posté le 19/12/2023 22:01 | #
J'avais pensé à un algo avec des "tiles" mais je sais pas si ça peut fonctionner en fait, c'est un peu une dérivation en sous problèmes, mais je sais pas si c'est ce genre d'approche qu'il faut utiliser.
En gros mon idée : partager le mur en tuiles de 2x2, on a donc 17*6 tuiles pour faire le mur complet.
La tuile en position (M,N) dépend de la tuile (M-1, N) et de la tuile (M, N-1) avec une liste de contraintes :
- si on est sur un bord, alors on impose un cote "fermé"
- on ne peut pas avoir de longueur >3 cellules donc si la case a une brique de 1 (en gros une arrête au milieu) alors on peut avoir soit une arrête au milieu (brique de 2) ou non mais alors elle a une arrête à droite donc une brique de 3.
- etc ...
Par récursivité on doit pouvoir reconstruire toutes les combinaisons possibles.
Le problème c'est qu'il faut parcourir toutes les branches de l'arbre donc le temps devient une contrainte extrêmement importante et je sais pas comment palier à ce problème.
Citer : Posté le 19/12/2023 22:07 | #
Ok, c'est une idée raisonnable. Le fait d'avoir une formule plus ou moins récursive avec une dépendances envers les positions M-1/N-1 est tout à fait bonne.
Prends les rangées une par une. Tu as environ 5000 rangées possibles, ce qui n'est pas très grand. Un mur de hauteur 12 c'est une première rangée r12 + un mur de hauteur 11 dont la première rangée r11 est "compatible" avec r12. Ce mur de hauteur 11 c'est donc r11 plus un mur de hauteur 10 dont la première rangée r10 est "compatible" avec r11.
Cette version va mieux marcher parce que le découpage du problème n'est pas "une tuile + d'autres tuiles" mais "une rangée + un mur" et donc tu as une structure récursive plus simple.
Citer : Posté le 19/12/2023 22:20 | #
Ok je pense que je vois l’idée. J’essaierai de coder un truc demain,.
Merci pour le tuyau.
Citer : Posté le 21/12/2023 22:31 | #
Votre cher admin, qui se perd, a oublié de vous donner des pièces hier ! Je suis sûr qu'elles vous manquent grandement. :P
Pièces du puzzle
Et voici un petit problème facile pour aujourd'hui pour reprendre le rythme. J'espère que vous avez pu vous débloquer, sinon n'hésitez pas à demander !
Pas un m² à perdre
Voyant le village s'étendre lentement mais sûrement, vous pressentez le besoin futur d'optimiser l'usage de l'espace dans l'usine. Comme exercice de pensée, on se demande si on pourrait caser une unité minimale comprenant des panneaux solaires, une batterie, et un four dans un format compact, c'est-à-dire rectangulaire.
Il faut donc placer ces éléments dans un rectangle sous les contraintes suivantes :
Déterminer la surface du plus petit rectangle dans lequel ces contraintes sont réalisables.
Pièces du puzzle
Citer : Posté le 21/12/2023 22:42 | #
J'ai une petite question sur le puzzle de l'avent: (je n'ai rien fais et je sais que c'est trop tard pour moi
Citer : Posté le 21/12/2023 23:01 | #
Tu as un script dans un des premiers posts ou tu rentre tes résultats et le script débrouille les pièces.
Petite question : on a combien de temps après le 25 pour résoudre le puzzle ?
Citer : Posté le 22/12/2023 11:04 | #
A bon? Dans quel post ? et il reste combien de temps, je vais essayer de commencer
Citer : Posté le 22/12/2023 14:07 | #
Dans le tout premier problème, page 1 des commentaires, le fichier joint
Citer : Posté le 22/12/2023 18:29 | #
Tiens tiens, de l’optimisation sous contraintes.
Enfin ça a peut être un autre nom en informatique. En mécanique c’est cette appellation qui est utilisée.
Citer : Posté le 23/12/2023 10:09 | #
Le puzzle est quand même pas facile à reconstituer, il y a pas mal de briques qui sont vraiment difficiles à positionner, entre le ciel, la neige et les sapins, c'est chaud patate
Les graphismes sont vraiment vraiment top.
Citer : Posté le 23/12/2023 22:24 | #
Tu as un script dans un des premiers posts ou tu rentre tes résultats et le script débrouille les pièces.
Petite question : on a combien de temps après le 25 pour résoudre le puzzle ?
Je confirme ce que SlyVTT a avancé. Vous avez le temps qu'il vous faudra. L'ultime puzzle le 25 sera certainement posté un peu plus tard dans la journée. Je vise que ce soit un problème un peu long, mais pas fondamentalement plus difficile que les précédents : le but est que ce ne soit pas la course à qui esquiverait les célébrations pour se jeter le premier sur l'énoncé.
L'image sera affichée dans l'article de Noël sans doute peu après que le gagnant ait été choisi, mais vous aurez le temps de résoudre au moins jusqu'au 1er Janvier (en donnant la liste des solutions du coup) pour faire valoir votre titre bien mérité.
A bon? Dans quel post ? et il reste combien de temps, je vais essayer de commencer
C'est serré mais il n'est pas fondamentalement trop tard haha, si tu coinces n'hésite pas à demander un indice !
Le puzzle est quand même pas facile à reconstituer, il y a pas mal de briques qui sont vraiment difficiles à positionner, entre le ciel, la neige et les sapins, c'est chaud patate
Oui j'ai réalisé ça après avoir fini l'image parce que c'est très chargé x) Je n'ai pas du tout essayé ce processus à la main. Si ça ajoute du challenge c'est bien !
L'image est en effet au top de mes capacités en pixel art, j'en suis très fier. :3