Le Puzzle de l'Avent 2024
Posté le 01/12/2024 17:58
Décembre, c'est attendre les fêtes dans une ambiance cozy, un plaid sur le dos et une tasse de thé à la main, avec un puzzle sous les yeux et du Python pour se remuer les neurones. Et vous toutes et tous invité·es !
Pour le principe de l'événement et les lots qui sont à remporter (une Graph Math+ moddée et une coque ou housse), voyez
l'article d'annonce de l'événement. Je ne vous remets ici que les points principaux
- Presque chaque jour de Décembre, je posterai un problème à résoudre, qui prendra cette année la forme d'un programme Python ayant un souci de performance ou de fonctionnalité à corriger.
- Une fois corrigé le programme Python, lorsque lancé, affichera sa « solution », un gros nombre permettant de décoder les pièces de puzzle du jour.
- Réassemblez le puzzle pour gagner des lots et le titre de Maître du Puzzle !
Mon intention est d'alterner entre des problèmes « plutôt faciles » (avec 1 jour laissé pour trouver la solution) et des problèmes « plutôt difficiles » (avec 2 jours laissés pour trouver la solution) pour que ce ne soit pas trop la course pour vous.
Si vous trouvez des solutions créatives, mathématiques, algorithmiques qui vous permettent de trouver le résultat sans lancer le programme Python, c'est valide aussi ! Je vous invite à vous en vanter dans les commentaires si ça arrive. Si vous trouvez un moyen de cheese le puzzle entier (i.e. avec une astuce qui marche pour tous les problèmes), vous ne pourrez pas prétendre au lots principaux, mais ça comptera quand même comme une résolution.
En juste admin qui fait trop de choses en même temps, je n'ai pas fini d'apporter les touches finales au puzzle, donc je vous donnerai les pièces du puzzle d'aujourd'hui et le script de décodage demain.
Comme vous pouvez le voir à la bannière, le puzzle est pas moche !!
À vos calculatrices dans les commentaires, bon courage tout le monde ! o/
Comment participer ?
Vous aurez besoin d'un ordinateur ou d'une calculatrice avec Python pour résoudre les problèmes et d'un ordinateur avec Python et la bibliothèque
Pillow pour décoder les pièces. Téléchargez
decode_pieces.py (lien direct) et indiquez vos solutions dedans. Placez-le dans un dossier à côté des images
Avent2024_Dec*r.png contenant les pièces brouillées, et exécutez-le pour décoder les pièces. Ensuite, réassemblez le puzzle dans un outil de votre choix (je conseille d'ouvrir les pièces comme des calques dans GIMP).
Liste des problèmes :
Le puzzle a été résolu par :
Fichier joint
Citer : Posté le 24/12/2024 16:39 | #
Topic mis à jour et titre activé. Aux suivants !
Citer : Posté le 24/12/2024 16:58 | #
Merci !
Le style de problèmes de cette année est un style que j'aime bien donc j'ai adoré les résoudre tout au long du mois. Le pixel art du puzzle est très stylé aussi, gg Lephe pour tout !
Et bien sûr, je suis honorée d'avoir une superbe couleur violette !
Citer : Posté le 24/12/2024 17:29 | #
On n'est pas pressés mais on verra par MP pour la gestion du lot.
Citer : Posté le 25/12/2024 10:32 | #
Nous avons une deuxième résolution du puzzle par Slyvtt !
Le deuxième lot est donc attribué aussi. \o/ Je publierai l'image dans un article bref aujourd'hui pour fêter l'occasion. Vous pouvez encore revendiquer le titre de Maître du Puzzle en soumettant vos puzzles avec vos solutions et scripts.
Citer : Posté le 25/12/2024 10:53 | #
Merci beaucoup !!
Bon j'avais déjà le titre, mais je suis très content d'avoir réussi le puzzle encore cette année. Les neurones de Papy Sly sont pas encore trop en céleri rémoulade
L'image est vraiment magnifique, GG Lephé sur le pixel art (et sur les épreuves).
S'ouvre donc aujourd'hui par la même occasion (avec la divulgation de l'image), la deuxième partie du jeu : "Trouver qui est qui sur l'image".
Bon courage aux autres compétiteurs. Et Big GG à Redoste qui a un peu plié le Game quand même
Et surtout Joyeux Noël à Toutes et Tous.
Citer : Posté le 25/12/2024 10:56 | #
Merci !!
Il faut réfléchir à ce qu'on te met comme titre du coup, vu que c'est pas le premier puzzle que tu finis ! Des suggestions ?
Citer : Posté le 25/12/2024 11:07 | #
Franchement ça n'a pas trop d'importance
Je fais le puzzle pour le fun, pas pour un titre
Citer : Posté le 25/12/2024 19:33 | #
Et une troisième résolution par Afyu, bravo ! Avec le puzzle parfait du premier coup.
Citer : Posté le 25/12/2024 20:15 | #
Bravo Afyu, bien joué. Confirmation d'un grand Maître du Puzzle encore cette année
Faut toujours compter sur Afyu
Y'a du level aussi de ce côté
Citer : Posté le 26/12/2024 00:17 | #
Congratulations Redoste on your win!
“They call me the king of the spreadsheets, got 'em all printed out on my bedsheets.” — “Weird Al” Yankovic
Citer : Posté le 02/01/2025 21:33 | #
Comme il y a encore au moins une personne qui cherche, voici des indices manquants !
Indice #1 (Configurations de foule) : P() ne dépend pas de l'ordre des éléments dans la liste. Donc f() teste beaucoup de séquences redondantes. Ce serait bien si on pouvait compter ces séquences redondantes sans les énumérer.
Citer : Posté le 05/01/2025 11:19 | #
Et J2l est la dernière personne à résoudre le Puzzle, ce qui nous fait 4 résolutions complètes cette année. Félicitations !!
Nous avons donc un membre de plus dans le club exclusif des Maîtres du Puzzle !
Je n'ai pas encore envoyé les MP pour gérer les lots : désolé pour le délai. J'ai les deux yeux dessus (quand le site est pas down).
Pour ne pas rater la partie la plus fun du challenge, je vous propose de discuter un peu des méthodes que vous avez utilisé pour résoudre les problèmes. J'ai vu du code passer donc je sais que vous avez pas toujours suivi la direction que j'attendais. En particulier je crois qu'il y a des trucs drôles sur Changement de perspective, Visions de l'espace, Dénombrement. Est-ce qu'il y a des problèmes que vous avez trouvé plus/trop durs ?
Citer : Posté le 05/01/2025 11:24 | #
Bravo à J2I, persévérance est mère de réussite ... C'est cool de voir des résolutions un peu distantes de Noël.
Du coup Lephé, tu veux qu'on commence d'expliciter les méthodes à partir de maintenant ? On risque pas de divulgacher (j'adore ce mot, nos cousins Québécois sont tellement imaginatifs) ?
Citer : Posté le 05/01/2025 11:27 | #
Personne d'autre ne s'est manifesté durant ni après l'événement (J2l avait posté) donc je pense qu'on peut considérer que c'est fini ?
Citer : Posté le 05/01/2025 12:19 | #
Ok, je me lance alors.
En lisant le code, j'ai vu qu'on avait 2 boucles imbriquées qui calculaient exactement la même chose, pour trouver les valeurs de a,b,c et d qui amène au minimum de |f(a) - f(b) + f(c) - f(d)|.
J'ai donc dans un premier temps utilisé un stockage des valeurs de |f(a)-f(b)| dans une liste de tuples en gardant trace de la valeur de f(a)-f(b) avec le signe et des grandeurs a et b correspondantes.
f_value= [f(i) for i in range(n)]
liste=[]
for a in range(n):
for b in range(a + 1, n):
value = f_value[a] - f_value[b]
liste.append( (abs(value), value, a, b) )
L'astuce consiste alors à trier cette liste de manière croissante et à chercher les 2 valeurs successives de cette liste qui sont les plus proches (on cherche l'index dans la liste qui correspond, pas la valeur en elle même) :
best_location=0
for i in range(nb_value-1):
value = abs(liste[i][1]+liste[i+1][1])
if value<best_diff:
best_diff = value
best_location = i
Ensuite, la clef correspond à la concaténation de cette différence en valeur absolue et des différents paramètres de la liste (a,b) stockés en position i et (c,d) stockés en position (i+1) :
print(f"Clef = {best_diff}{liste[best_location][2]}{liste[best_location][3]}{liste[best_location+1][2]}{liste[best_location+1][3]}")
Alors comme d'habitude, j'ai commencé à tester les valeurs de N petites pour voir ce qui sortait de l'algo, et très vite je me suis rendu compte que les valeurs crachées f(N) par l'algo correspondait à N. J'ai donc tenté au bluff de concaténer les valeurs de N pour la clef et c'était la solution.
(Bon après ça me satisfaisait moyen comme résolution, j'ai donc cherché pourquoi et en réfléchissant (oui ça m'arrive
Celui-ci par contre on a vraiment galéré dessus à 2 cerveaux, car on y a réfléchit avec Afyu.
J'ai remarqué que si N modulo 12 valait (1,6,8,10) alors g(n) valait 2^(n-1).
On cherche en fait le nombre de valeurs distinctes générées par f en prenant en compte deux modulos à fréquences différentes. En traçant les valeurs sur un graphique, on voit qu'avant l'occurrence du premier modulo (fréquence 2^n), on ne retombe jamais sur les mêmes valeurs car le modulo fréquence m (ici 13) redonne toujours des valeurs différentes.
Passer de n+12 à n donne un f(n)=f(n+12)/2^12 (2^12 valant 4096), aux arrondis près. Nous on cherche à avoir f(n+12) en fonction de f(n), donc la précision sera la clef car on va propager une erreur. En calculant les valeurs de n=0,2,3,4,5,7,9,11 et idem pour les valeurs de n permettant un calcul "rapide", on voit qu'on a en fait des harmoniques avec une gamme de 13 "notes". il faut donc juste obtenir une précision suffisamment fine de la loi de passage entre les fréquences des harmoniques et ensuite on obtient une estimation relativement fine des valeurs de g(60 et g(62) sachant que g(60) donne une valeur exacte.
A la fin, j'ai calculé mon estimation de g(60) = g(61) + g(62) et un peu bruteforce autours de cette valeur. Pour trouver la clef. Afyu a une méthode différente sur la fin, il saura expliciter mieux. J'ai utilisé un tableur pour résoudre ce problème.
Clairement celui-ci était chaud patate, ça nous a pris 2 jours.
J'ai vu de suite que c'était un cas de programmation dynamique, mais n'étant pas au faît du truc, j'ai donné l'algo à ChatGPT en lui demandant si on pouvait optimiser avec de la prog dynamique. Il m'a craché un algo direct qui sortait la solution en à peine 5 secondes.
J'avoue que j'étais bluffé
Citer : Posté le 05/01/2025 14:19 | #
Je crois que j'ai une solution intéressante que pour le jour 4, j'ai regardé les fonctions pendant un moment et je me suis rendu compte que ça faisait juste un motif. Avec des congruences, et un peu d'essai/erreur, j'ai trouvé la valeur la plus petite qui donne le même résultat que le mille milliards de l'énnoncé
#f(n) = (not n-1) or (g(n-1) + 1) = (not n-1) or ((not n-2) or h(n-2) + 2)
# = (not n-1) or ((not n-2) or ((not n-3) or f(n-3)))
#
for i in range(15):
print(f(11+i), end="")
print("")
Caltos : G35+EII, G90+E (briquée