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 08/12/2024 12:48 | #
Bonjour,
est-il normal d'avoir à modifier le rang des chiffres à garder print(str(x)[15:35]) dans fins détails ?
Citer : Posté le 08/12/2024 13:26 | #
Bonjour, ce n'est pas ce que la solution "attendue" fait, mais si ça marche... toutes les méthodes de résolution sont acceptables.
Citer : Posté le 08/12/2024 20:28 | #
Correction : Dans le problème du 5 (Fins détails), à cause d'une erreur de ma part, la solution est constituée des chiffres 14 à 33 et non 15 à 34 (décalage de 1).
Citer : Posté le 08/12/2024 20:37 | #
Tiens chez moi ça marchait avec print(str(x)[15:35])
Tu as changé l'image du coup ? Faut refaire ou si on a une solution qui fonctionnait on la garde ?
Citer : Posté le 08/12/2024 20:38 | #
Non j'ai pas changé l'image. Si vous avez les pièces, vous avez les pièces, rien à changer.
Citer : Posté le 09/12/2024 00:24 | #
Changement de perspective
Les manchots les plus chauds de la promo sont des pros et ont résolu l'exo presto. Vous calmez leurs ardeurs en leur posant la colle suivante.
def f(i): # pas besoin de comprendre f
x = abs(math.cos(2739 * i + 3920))
return int((x - int(x)) * 10**15)
def s(n):
sc = n
ret = None
for a in range(n):
for b in range(a+1, n):
for c in range(n):
for d in range(c+1, n):
x = f(a) - f(b) + f(c) - f(d)
if abs(x) < sc:
sc = abs(x)
ret = (a, b, c, d)
print("{}{}{}{}{}".format(sc, *ret))
s(5000)
Pièces du jour :
Indice #1 : On cherche à minimiser f(a)-f(b)+f(c)-f(d) où c,d ont les mêmes bornes que a,b. Ce test nécessite n⁴ tests. Mais finalement on cherche donc deux valeurs qui s'écrivent f(x) - f(y) et sont les plus proches possibles l'une de l'autre (au signe opposé près).
Indice #2 : Une fois que vous avez calculé toutes les valeurs possibles de f(a)-f(b) sur l'intervalle considéré, vous voulez trouver les deux valeurs les plus proches possibles (au signe près). Vous pouvez faire ça sans tester toutes les paires de valeurs.
Citer : Posté le 09/12/2024 00:28 | #
J'avais oublié un indice, pas grave je me rattrape.
Indice #2 (Fins détails) : x, y, a et b s'écrivent tous comme un nombre entier plus un certain nombre entier de fois √7, et on peut donc les représenter par une paire d'entiers. Il se trouve qu'ajouter ou multiplier entre eux des valeurs ayant cette forme donne des résultats ayant également cette forme.
Indice #1 (Classes de complexité) : l'élément que l'on cherche peut être trouvé par un test bien plus simple. Considérez le cas a=b=c.
Citer : Posté le 11/12/2024 09:57 | #
J'ai un peu de mal à tenir le rythme, mais tout va bien, la seule fois où il est vraiment indispensable d'être à temps c'est le 23 et 24...
Indice #1 (Changement de perspective) : On cherche à minimiser f(a)-f(b)+f(c)-f(d) où c,d ont les mêmes bornes que a,b. Ce test nécessite n⁴ tests. Mais finalement on cherche donc deux valeurs qui s'écrivent f(x) - f(y) et sont les plus proches possibles l'une de l'autre (au signe opposé près).
Citer : Posté le 11/12/2024 12:09 | #
Révisions
Au retour de la pause déjeuner vous êtes accosté·e par un des étudiants, Plouf, qui essaie sans succès d'écrire une recherche dichotomique pour trouver la valeur de f() la plus proche possible de x par le haut. Vous jetez un oeil à son code et remarquez immédiatement trois erreurs classiques et une façon plus efficace de programmer ce calcul.
def f(i): # il suffit de regarder quelques valeurs de f()
x = abs(math.cos(2739 * i + 3920))
return int((x - int(x)) * 10**15)
def bsearch(n, x):
l, r = 0, n
while l <= r:
m = (l + r) // 2
if f(m) < x:
l = m
else:
r = m
return f(l)
x = 310283748389837
print(bsearch(1000000, x))
Pièces du jour (hier >.>) :
Indice #1 : La recherche dichotomique ne s'applique pas parce que le tableau donné par f() n'est pas trié (f() n'est pas croissante). On peut donc oublier le code fourni. Le calcul demandé peut être fait assez facilement à partir de zéro.
Citer : Posté le 12/12/2024 23:43 | #
Ce problème sera je pense coriace pour certains, et j'ai du mal à suivre le rythme moi-même (pas étonnant ça arrive à chaque fois lol... !) donc je vous donne du répit en combinant les problèmes du 11 et 13.
Sobriété douteuse
Aman vous emmène passer la soirée au bar, où vous rencontrez de nombreux nouveaux becs et tapez notamment la causette avec Arvien, le doyen, et Froull, le « piaf logistique » qu'on l'appelle apparemment. Rumeur court que toute une fête est prévue, auquel cas bien sûr Froull aurait le bec dedans, et il vous laisse subtilement entendre que les bavardages ne sont pas infondés. Il ne s'attarde pas cependant et décolle assez rapidement. Pour s'excuser, il vous laisse un problème qu'il a fini de concocter le matin-même et qui a déjà fait le tour du bar maintes fois sans trouver pour l'instant de solution. Une petite foule excitée s'assemble autour votre table pour jeter un énième coup d'oeil au problème et vous voir en action.
s = p - 1 - (p & 1)
for i in range(n):
p += 2
for j in range(2*i, 2*n):
s += (k ^ p ^ j) & 1 or f(p * i + 1, k + (j * i), n)
p += 2 * j * j + 1
s += i * j
s += p
return s
print(f(0, 2, 300))
On vous assure que malgré les apparences Froull était tout sauf éméché quand il a écrit ce programme.
Note : la solution attendue est environ 120 fois plus rapide que l'original et pourra mettre de l'ordre d'une minute. Vous pouvez réduire le 300 pour tester si votre code passe à l'échelle.
Jeux de pièces :
Indice #1 : Pour optimiser il serait déjà utile de voir où se passent les calculs. On a deux boucles imbriquées, et si l'appel récursif est fait on en a 4, et si l'appel récursif est fait de nouveau on en 6, et ainsi de suite. L'appel récursif est fait si la parité combinée de k, p et j est impaire. Ce serait donc un bon début si on pouvait déterminer ça.
Indice #2 : Il y a aura au plus un appel récursif de profondeur. Donc on peut remplacer l'appel récursif par un appel à une fonction f2() qu'on crée comme une copie de f() mais dans laquelle il n'y a plus d'appel récursif. f2() se simplifie ensuite significativement.
Citer : Posté le 12/12/2024 23:44 | #
Indice #2 (Changement de perspective) : Une fois que vous avez calculé toutes les valeurs possibles de f(a)-f(b) sur l'intervalle considéré, vous voulez trouver les deux valeurs les plus proches possibles (au signe près). Vous pouvez faire ça sans tester toutes les paires de valeurs.
Citer : Posté le 13/12/2024 14:59 | #
trop compliqué pour moi votre puzzle dans lequel je ne comprends rien du tout
mais amusez-vous bien
Citer : Posté le 15/12/2024 12:05 | #
Problème de culture
Aman vous parle d'un problème qu'elle a construit en naviguant Internet. La qualité du réseau en Antarctique est décidément... limitée... mais les progrès récents qui ont permis aux manchots de se connecter de façon à peu près fiable et ainsi de se mettre au Python leur ont également donné accès à des ressources scientifiques. Un groupe de filles lancées dans des explorations théoriques est en train de se rendre compte que tout ne se fait pas à l'intuition, et pratiquent depuis quelques semaines le sport de poser des colles aux mâles en exploitant leurs lacunes des fondamentaux. Vous avez sous les yeux un de ces problèmes, pour l'instant résolu par un seul membre de la colonie.
return g(m - 1, g(m, n - 1)) if m and n else (not m and n+1) or g(m-1,1)
print(str(g(4, 2))[1500:1520])
Indice #1 : Il est futile d'essayer de finir le calcul ou d'optimiser la fonction. Mais vous pouvez analyser g() en essayant de calculer une formule sympa pour g(0,m) en fonction de m, puis en déduire une pour g(1,m), et ainsi de suite.
Indice #2 : Cette fonction a été inventée par Wilhelm Ackermann.
Citer : Posté le 15/12/2024 23:32 | #
Indice #1 (Sobriété douteuse) : Pour optimiser il serait déjà utile de voir où se passent les calculs. On a deux boucles imbriquées, et si l'appel récursif est fait on en a 4, et si l'appel récursif est fait de nouveau on en 6, et ainsi de suite. L'appel récursif est fait si la parité combinée de k, p et j est impaire. Ce serait donc un bon début si on pouvait déterminer ça.
Citer : Posté le 16/12/2024 09:08 | #
Indice #1 (Révisions) : La recherche dichotomique ne s'applique pas parce que le tableau donné par f() n'est pas trié (f() n'est pas croissante). On peut donc oublier le code fourni. Le calcul demandé peut être fait assez facilement à partir de zéro.
Citer : Posté le 17/12/2024 01:08 | #
Problème de culture #2
(Je vous épargne de nouveau le lore à cette heure)
return (n == 1 and 1) or 1 + f(3 * n + 1 if n & 1 else n // 2)
def g(m):
return max(range(1, 10**m), key=f)
print(g(15))
Indice #1 : Ce n'est, à ma connaissance, pas un calcul que vous pouvez faire vous-même avec les ressources utilisées pour les autres problèmes de cette série. La réponse se trouvera sur Internet.
Indice #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.
Citer : Posté le 17/12/2024 13:04 | #
Indice #2 (Sobriété douteuse) : Il y a aura au plus un appel récursif de profondeur. Donc on peut remplacer l'appel récursif par un appel à une fonction f2() qu'on crée comme une copie de f() mais dans laquelle il n'y a plus d'appel récursif. f2() se simplifie ensuite significativement.
Citer : Posté le 17/12/2024 18:17 | #
Visions de l'espace
Le soir vous vous posez sur la banquise avec Aman et regardez les étoiles. Le crépuscule dure depuis un mois et va encore continuer un bon moment, mais par chance vous pouvez déjà voir scintiller tout un pan de l'horizon. Vous tracez des formes dans l'espace en reliant les points et vous perdez doucement dans les méandres du ciel clair... quand votre réflexion s'arrête, Aman vous propose avec un grand sourire un problème qui vient de lui venir à l'esprit.
return sum(x * y for x, y in zip(xs, ys)) == 0
def all_o(xss):
return all(o(xss[i], xss[j]) for i in range(len(xss)) for j in range(i))
def all_xs(n, M):
if n == 0:
yield []
return
for rest in all_xs(n-1, M):
for i in range(-M+1, M):
yield rest + [i]
def f(xss, n, M):
if not all_o(xss):
return -1
return 1 + max(f(xss + [xs], n, M) for xs in all_xs(n, M) if any(xs))
for n in [35, 76, 24, 143, 88, 73, 91]:
print(f([], n, 5), end="")
Pièces du jour :
Indice #1 : 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.
Indice #2 : 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 17/12/2024 18:24 | #
J'ai oublié quelques indices, les voici.
Indice #1 (Problème de culture) : Il est futile d'essayer de finir le calcul ou d'optimiser la fonction. Mais vous pouvez analyser g() en essayant de calculer une formule sympa pour g(0,m) en fonction de m, puis en déduire une pour g(1,m), et ainsi de suite.
Indice #1 (Problème de culture #2) : Ce n'est, à ma connaissance, pas un calcul que vous pouvez faire vous-même avec les ressources utilisées pour les autres problèmes de cette série. La réponse se trouvera sur Internet.
Citer : Posté le 20/12/2024 01:18 | #
J'avais ce problème en tête depuis quelques temps et je pensais qu'il serait facile, mais en fait pas tant que ça. Je combinerai peut-être avec le prochain.
Dénombrement
return (3 * k + 1) % (2**n) + (k % m)
def g(n, m):
return len({f(k, n, m) for k in range(2**(n-1))})
print(g(60, 13) + g(61, 13) + g(62, 13))
Pièces du jour :
Indice #1 : 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.
Indice #2 : 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.
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.