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 02/12/2024 16:21 | #
Si je comprends bien, j'ai un score de 0,112 :
truc_gmp [o]<n> [repetitions]
$ ./truc_gmp o10000 5000
3107...6253
duration: 2700037446ns (2.700s)
$ time python omg.py
945165213
python omg.py 24,10s user 0,05s system 99% cpu 24,190 total
$ python -c "print(2700037446 / 24100000000)"
0.1120347487966805
Mon blog ⋅ Mes autres projets
Citer : Posté le 02/12/2024 16:37 | #
Yup, c'est ça.
Et donc avec ma version précédente (linéaire + pas de cache en C/GMP), j'avais 0.08 de score. La méthode que Hackcell mentionnait sur le chat est meilleure pour les grandes valeurs de n (... 150 fois plus rapide pour n = 1 million), donc avec n=10000 elle déjà pas mal avantagée, et j'arrive à 0.059 rien qu'en Python. Alors en C...
Citer : Posté le 02/12/2024 20:52 | #
Pour régner
Sans surprise, vous n'avez fait aucune bouchée du problème de la suite récurrente. Bren, le pingouin voyageur qui vous a apporté la missive, et un fin bec lui-même, trouve également le problème trivial et se propose de rentabiliser son long voyage en vous posant un défi un peu plus solide.
Déterminez ce que le programme suivant affiche.
R, D, Q = 1, 53632, 0
for i in range(N+1):
Q = 0
while R >= D:
R -= D
Q += 1
R *= 10
return Q
for N in range(10**12, 10**12 + 15):
print(s(N), end="")
print("")
Pièces du jour :
Indice #1 : s() est un algorithme qui calcule la division euclidienne entre deux entiers, décimales comprises. En d'autres termes, il calcule la série de décimales d'un certain nombre rationnel. Or, le développement décimal d'un nombre rationnel est très « prévisible ».
Indice #2 : D est constant et Q est réinitialisé à chaque tour. Toute la suite découle donc de R, et certaines valeurs de R vont apparaître plusieurs fois.
Citer : Posté le 02/12/2024 21:58 | #
J'ai ajouté les pièces d'hier et aujourd'hui ainsi que le script de décodage dans le post principal. Enjoy! o/
Citer : Posté le 02/12/2024 22:16 | #
Are the puzzle pieces already in the correct orientation, or might I need to rotate them?
“They call me the king of the spreadsheets, got 'em all printed out on my bedsheets.” — “Weird Al” Yankovic
Citer : Posté le 02/12/2024 22:19 | #
They're already in the correct orientation. Only translation.
Citer : Posté le 02/12/2024 22:24 | #
J'ai oublié un indice pour le problème d'hier (ajouté dans le post en plus d'ici) :
Indice (Penguin Programming Party) : C'est une suite récurrente, il est plus facile de la calculer en commençant par le bas.
Citer : Posté le 03/12/2024 21:33 | #
Un premier indice pour le problème d'hier (il y en aura deux).
Indice #1 (Pour régner) : s() est un algorithme qui calcule la division euclidienne entre deux entiers, décimales comprises. En d'autres termes, il calcule la série de décimales d'un certain nombre rationnel. Or, le développement décimal d'un nombre rationnel est très « prévisible ».
Citer : Posté le 05/12/2024 01:18 | #
Logique douteuse
Et hop, les horaires de post délirantes commencent. >_< Je m'épargne le lore, j'ai plus le cerveau pour le produire.
return not n or g(n-1) + 1
def g(n):
return not n or h(n-1) + 1
def h(n):
return not n or f(n-1) - 2
for i in range(15):
print(f(93203847342983+i), end="")
print("")
Pièces du jour :
Indice #1 : regardez les valeurs renvoyées par f() sur des petites entrées.
—
Et un indice pour le problème précédent :
Indice #2 (Pour régner) : D est constant et Q est réinitialisé à chaque tour. Toute la suite découle donc de R, et certaines valeurs de R vont apparaître plusieurs fois.
Citer : Posté le 06/12/2024 15:04 | #
Bon j'ai absorbé un peu de retard, plus que celui du 2 que j'ai pas encore regardé ... Faut pas commencer d'accumuler sinon ça va être chaud à la fin ...
Les couleurs ont l'air très girly
Citer : Posté le 06/12/2024 15:52 | #
The artwork is looking great. Let's free the colors. All colors are for everyone! 🌈
“They call me the king of the spreadsheets, got 'em all printed out on my bedsheets.” — “Weird Al” Yankovic
Citer : Posté le 06/12/2024 17:03 | #
pinky pinky pinky boy !!!
Citer : Posté le 06/12/2024 17:35 | #
Les couleurs sont bien ! Faut varier les tons ! Tu verras ça met une ambiance de fou !
N'hésitez pas, comme Sly, à dire où vous en êtes pour que je puisse ajuster. Sinon je me cale sur les gens forts qui finissent instantanément et ça va être de plus en plus dur. xD
Fins détails
Maintenant arrivés en terre Adélie, vous faites vos adieux à Bren, qui repart pour d'autres missions intercontinentales. Bren, c'est un peu le cool kid qui voyage tout le temps. À la tienne, Bren! o/
Vous êtes reçus à la colonie par la douce et imposante Aman, un manchot empereur qui a la tâche de vous guider pendant les quelques semaines de votre visite. Elle vous présente aux curieux passants qui sont au courant de votre arrivée et sont nombreux à vouloir vous soumettre des petits casse-têtes. La plupart sont triviaux et vous les résolvez sur-le-champ, mais un retient votre attention.
def s(n):
x = 1 + 2 * sqrt(7)
y = 1 - 2 * sqrt(7)
a = -2 + 3 * sqrt(7)
b = -2 - 3 * sqrt(7)
for i in range(n):
x, y = x * x, y * y
return round(a * x + b * y)
x = s(12)
print(str(x)[14:34])
La fonction s() ne fonctionne que pour des petites entrées, parce que pour les grandes entrées comme 12 le calcul de x et y déborde de la capacité des nombres flottants et atteint l'infini.
Réécrivez la fonction de façon à pouvoir terminer le calcul de s(12) et afficher ses chiffres 14 à 33 comme souhaité par le code.
Correction : Les chiffres à afficher sont 14 à 33 et non pas 15 à 34 comme indiqué initialement.
Pièces du jour :
Indice #1 : Le résultat du calcul est un entier, et les entiers disposent d'une précision infinie en Python. Il est de fait possible de faire le calcul sans recourir à des nombres en point flottant.
Indice #2 : 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.
Citer : Posté le 06/12/2024 17:41 | #
Et un indice pour le puzzle précédent :
Indice #1 (Logique douteuse) : regardez les valeurs renvoyées par f() sur des petites entrées.
Citer : Posté le 06/12/2024 22:00 | #
Du coup y-a-t'il un deuxième set de pièces avec une énigme aujourd'hui ? Comme tu as aujourd'hui mis les pièces d'hier ?
Petite précision qui n'apparaît pas : le puzzle fait-il comme l'année dernière 396 x 224 pixels ?
Citer : Posté le 06/12/2024 22:04 | #
Non selon le planning il n'y avait pas de problème prévu aujourd'hui (c'est tous les jours de Décembre pas multiples de 3), donc on est dans les temps.
Le puzzle fait 198x112 (comme l'an dernier), il s'affichera en 2:2 sur la Math+
Citer : Posté le 06/12/2024 22:21 | #
Ok, mais les pièces sont en 2:2 telles que livrées dans les énigmes ? non ?
Citer : Posté le 06/12/2024 22:27 | #
Ah oui c'est vrai j'oublie toujours que je l'ai fait comme ça. xD
Citer : Posté le 07/12/2024 11:56 | #
Indice pour le problème d'hier :
Indice #1 (Fins détails) : Le résultat du calcul est un entier, et les entiers disposent d'une précision infinie en Python. Il est de fait possible de faire le calcul sans recourir à des nombres en point flottant.
Citer : Posté le 07/12/2024 23:01 | #
Classes de complexité
Au détour de la colonie, Aman vous fait visiter l'école, où vous observez les oiseaux... studieux... et moins studieux... s'attaquer à un cours de complexité algorithmique. L'exemple introductif à base de catégorisation de poissons n'était pas un choix très judicieux de l'enseignant, Zen, puisqu'il rappelle surtout aux pingouins que l'heure du repas est proche. Quand la classe finit par se terminer, reste sur le tableau le devoir du jour.
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, N):
for a in range(N):
for b in range(N):
for c in range(N):
if 3 * f(i) < f(a) + f(b) + f(c):
return False
return True
def s(N):
for i in range(N):
if g(i, N):
return f(i)
print(s(10000))
La seule instruction est d'ignorer la fonction f() et d'optimiser g() et s().
Pièces du jour :
Indice #1 : 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 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 ?