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 20/12/2024 01:22 | #
Indice #2 (Problème de culture) : Cette fonction a été inventée par Wilhelm Ackermann.
Indice #1 (Visions de l'espace) : Chaque xs représente une direction. Quand n=2 c'est une direction dans le plan, quand n=3 c'est une direction dans l'espace, et de façon générale c'est une direction dans un espace de dimension n. all_xs() génère la liste de toutes les directions possibles (plus précisément un petit échantillon représentatif - la réponse du programme serait la même si on testait l'infinité possible de directions). o() teste si deux directions sont perpendiculaires.
Citer : Posté le 21/12/2024 12:37 | #
J'ai pas eu de retours explicites sur Dénombrement donc je me replie sur mon intuition initiale qu'il est assez dur pour mériter un jour de battement.
Il nous reste 4 jeux de pièces. 2 problèmes seront postés le 24 à midi, et ce ne seront pas des problèmes de culture ou nécessitant un accès à Internet. De fait ils seront du même ordre que d'autres problèmes précédents, ce qui devrait mettre à peu près tout le monde sur un pied d'égalité. Les deux autres (22 et 23) seront plutôt faciles.
Citer : Posté le 21/12/2024 20:23 | #
Je confirme que l'énigme d'hier est raide.
J'ai commencé seulement cette fin d'après midi, mais chaud patate le zinzin
Citer : Posté le 21/12/2024 21:31 | #
c'est pour les cerveaux à plusieurs étages ce défi :/
Citer : Posté le 22/12/2024 19:02 | #
c'est pour les cerveaux à plusieurs étages ce défi :/
Il est plus facile que l'an dernier, même si je reconnais que la tête du code ne le suggère pas... ^^"
Citer : Posté le 22/12/2024 19:39 | #
Tu dis que c'est facile cette année, c'est parce que tu as pas mis d'erreur dans la clef de décryptage
J'ai une estimation de la clef du 19/20 dans une fourchette de 400 milliards, c'est pas mal par rapport à 3E18 +/- 1E18
Citer : Posté le 22/12/2024 20:48 | #
Tu peux presque finir par une énumération bruteforce du coup.
Citer : Posté le 22/12/2024 20:55 | #
Indice #1 (Dénombrement) : Une réponse exacte est nécessaire. Commencez par vous défaire du modulo en découpant les entrées selon si le résultat est dans les bornes, ou overflow une fois, ou deux, etc.
Citer : Posté le 22/12/2024 22:23 | #
Pentes glissantes
La fête est maintenant confirmée, dans quelques jours plus ou moins ; vous n'êtes pas trop sûrs de quand, et les manchots non plus puisque la notion de temps est plus abstraite qu'il n'y paraît quand le Soleil ne tourne pas rond. Froull vous propose de faire de la descente d'iceberg, le sport de glisse local qui est un de ses passe-temps favoris. Le dénivelé n'est pas exceptionnel mais l'ambiance est dans la stratosphère, car des oiseaux de toutes plumes se bousculent pour jouer : le moment est bon. Il faut que le Soleil tape juste assez pour créer une couche de glace pas trop dure ce qui n'arrive pas si souvent. Après quelques ruées exhilarantes vers l'eau glaciale, vous grimpez revigoré·e et prenez le chemin de la file. Votre voisin de devant entame la papote avec Froull avant de vous poser l'énoncé suivant.
def f(i): # pas besoin de comprendre f
x = abs(math.cos(2739 * i + 3920))
return int((x - int(x)) * 10**15)
def g(i):
return sum(f(j) for j in range(i, i + 2**21))
x = min(range(2**21), key=g)
y = max(range(2**21), key=g)
print("{}{}".format(x, y))
Pièces du jour :
Indice #1 : Il y a beaucoup de calculs redondants cachés dans les appels successifs à g().
Citer : Posté le 22/12/2024 22:28 | #
Indice #2 (Problème de culture #2) : Le calcul 3 * n + 1 if n & 1 else n // 2 itère une suite célèbre qu'on appelle suite de Syracuse (English: Collatz sequence). Il est conjecturé, mais pas prouvé, que cette suite finit toujours par passer par un. f() calcule le « temps de vol » nécessaire pour atteindre 1 en partant d'une certaine entrée.
Indice #2 (Visions de l'espace) : f() essaie de construire une suite xss de direction la plus grande possible dans laquelle tous les xs sont perpendiculaires deux à deux. Combien de directions toutes perpendiculaires peut-on caser au maximum dans un espace de dimension n ? Vous pouvez vous limiter aux cas du plan (n=2) et de l'espace à trois dimensions (n=3).
Citer : Posté le 23/12/2024 21:11 | #
Pour rappel, les deux derniers problèmes seront publiés demain autour de midi (voire un peu avant).
This escalated quickly
Vous racontez à Froull le tout premier problème qui vous avait été livré via Bren au début de votre voyage, et il pense rapidement à un grand classique. Le lien entre ces deux problèmes ne vous semble pas évident, mais Aman qui tend l'oreille se fait une joie de vous raconter la théorie derrière.
N = 2**64
print((73 ** n) % N)
Pièces du jour :
Citer : Posté le 23/12/2024 21:20 | #
Indice #2 (Dénombrement) : Une fois que vous avez des ensembles dans lesquels le modulo 2**n a été éliminé, il vous reste à savoir si au sein d'un même ensemble vous pouvez avoir des doublons (non—mais pourquoi ?) et s'il va y avoir des éléments partagés d'un ensemble à l'autre (oui). Déterminer le nombre de « collisions » sur 2⁶⁰ entrées a l'air long, mais ces collisions sont périodiques.
Indice #1 (Pentes glissantes) : Il y a beaucoup de calculs redondants cachés dans les appels successifs à g().
Citer : Posté le 24/12/2024 12:01 | #
La fête est là !
Résolvez ces deux problèmes pour finir de reconstituer une image complète de la fête !
Configurations de foule
if l <= 0:
yield []
return
for i in range(N):
for sub in all_sequences(N, l-1):
yield [i] + sub
def red(f, it, v):
for i in it:
v = f(v, i)
return v
def P(seq):
s, p, x = sum(seq), red(int.__mul__, seq, 1), red(int.__xor__, seq, 0)
return ((s + p) * ((s ^ p) | x) & 0x100) != 0
def f(N, l):
total = 0
for seq in all_sequences(N, l):
total += P(seq)
return total
print(f(8, 22))
L'intention est d'analyser P() mais pas de la modifier/reproduire.
Pièces (du "24 Décembre" dans le script) :
Décompte des invités
return (s * k) % N
def g(s, N):
return len({f(k, s, N) for k in range(N)})
def h(N):
return sum(g(s, N) for s in range(1, N+1))
print(h(2749281825979311820300034269197320091780))
Malgré les apparences, ce problème est plus facile que Dénombrement.
Pièces (du "25 Décembre" dans le script) :
Citer : Posté le 24/12/2024 12:05 | #
Rappel des modalités : envoyez-moi le puzzle complété par MP (vous pouvez héberger l'image sur https://t.breizh.pm/) ou par mail à contact@... avec l'image en PJ. Avec votre code/notes de résolution, parce que je publierai l'image dans un article dès que les gagnant·es des lots seront décidé·es, après quoi un simple envoi de l'image ne sera plus une preuve de résolution. La première personne qui m'envoie le puzzle correct gagne, date de MP/mail faisant foi. La seconde personne remporte le deuxième lot.
Si le puzzle contient des erreurs je vous ferai un retour pour vous permettre d'ajuster, cependant je ne garantis pas le temps de réponse et donc il est possible que quelqu'un vous passe devant entre temps. Visez d'avoir juste au premier coup.
Citer : Posté le 24/12/2024 13:41 | #
C'est quoi que tu appelles code/notes de résolution ? C'est le fichier "decode.py" ?
Citer : Posté le 24/12/2024 13:45 | #
Oui. Remarque si vous avez du code à proprement parler je suis preneur aussi mais plus par curiosité pour voir comment vous avez résolu les problèmes. Ce serait marrant de débrief là-dessus comme on le fait parfois pour le concours de rentrée.
Citer : Posté le 24/12/2024 13:58 | #
Correction : le script decode_pieces.py a une erreur de logique sur le décodage du problème du 25. Il utilisera le code que vous avez saisi pour le 24 à la place. Remplacez la fonction problem_no() par :
return [1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,24,25].index(day)
Ou bien re-téléchargez-le dans le post principal et re-saisissez vos solutions.
Ou bien modifiez votre solution du 24 une fois que vous avez récupéré les pièces du 24...
Citer : Posté le 24/12/2024 14:49 | #
J'ai oublié de préciser : comme l'an dernier les reconstitutions du puzzle sont validées à 4 pièces près (i.e. s'il y a 4 pièces ou moins pas à leur place c'est compté, sinon je vous dit à peu près où et aller-retour de message).
Citer : Posté le 24/12/2024 16:03 | #
Mesdames messieurs nous avons une première résolution du puzzle par Redoste !
La Math+ te revient, du coup o/
Citer : Posté le 24/12/2024 16:18 | #
Bravo Redoste (de manière officielle cette fois)
GG
Quand je dis que le puzzle est une épreuve en soit ...
Citer : Posté le 24/12/2024 16:39 | #
Topic mis à jour et titre activé. Aux suivants !