Le Puzzle de l'Avent 2019
Posté le 01/12/2019 11:47
Bienvenue à tous dans la période de l'Avent. Pour vous aider à attendre Noël, Planète Casio vous propose son calendrier aux 24 problèmes mathématiques et informatiques. 
Le Puzzle de l'Avent de cette année est un jeu dans lequel vous devez résoudre des petits problèmes mathématiques et informatiques. Chaque jour, je vous donnerai des pièces du puzzle codées par un
code couleur. Votre tâche est de retrouver le code de chaque image et de les décoder ! À la fin du mois, les pièces se combineront pour former une
image de Noël.
J'ai demandé une Graph 35+E II à Casio pour récompenser la première personne qui résoud le puzzle. Casio a confirmé qu'ils sont d'accord, je pourrai donc envoyer le lot dès que je l'aurai reçu.
Voici l'énoncé précis du jeu !
Le but du jeu est de reconstituer intégralement l'image de Noël. Il s'agit d'une image de 128x64 pixels en quatre niveaux de gris (noir, gris foncé, gris clair, blanc). Il y a 128 pièces à ce puzzle, que je distribuerai tous les jours jusqu'à Noël.
Pour participer, envoyez-moi un MP avec votre image. La personne qui aura reconstitué le plus fidèlement l'image le 24 Décembre à 23h59 remportera le Puzzle et aura le titre de
Maître du Puzzle.
Toutes les personnes qui m'auront envoyé une participation ayant plus de 90% de pixels justes (soit 7372 sur 8192) auront également le titre.
Les pièces sont réparties en quatre cadrants comme ceci :
Contrairement à l'année dernière, les indices ne sont pas cachés, donc vous pouvez poser des questions et je vous répondrai dans une certaine mesure (sans révéler les résultats). Donc n'hésitez pas à demander dans les commentaires si vous avez du mal, je donnerai des explications !
Tous à vos postes, on commence maintenant !
Notes du futur.
• Le 23 Décembre, Filoji a reconstitué l'intégralité de l'image !
• La solution des problèmes est disponible au format PDF !
Liste des indices et pièces de l'image
1er Décembre
Pour les premiers jours, on va se concentrer sur le code couleur. Toutes les images, sauf la première, ont été un peu modifiées et bougées. Le
carré code à droite de chaque image indique quelle opération j'ai faite.
Les pièces ont été agrandies fois 2 (elles font 16x16 pixels au lieu de 8x8), je vous conseille de les réduire avant de commencer à travailler avec.
2 Décembre
Contrairement à hier, aujourd'hui les transformations se marchent un peu sur les pieds. Il faut donc trouver la bonne façon de les combiner...
Sinon le principe est exactement comme hier. Si vous avez déjà utilisé des couleurs en programmation, ça vous posera pas de problème.
3 Décembre
Il n'y a rien de vraiment nouveau, mais parfois durant les problèmes j'aurai besoin de transformer les pièces plusieurs fois.
4 Décembre
Vous avez déjà tous les éléments concernant le fonctionnement du code couleur. Désormais, on va jouer un peu avec des problèmes de maths et d'informatique.
Attention, ne vous précipitez pas car j'ai
mélangé les carrés codes.
Pour retrouver qui va avec qui, voici une aide. L'image ci-dessous représente un
graphe, avec des
noeuds (les ronds) et des
arêtes (les traits). Les noeuds de gauche représentent les pièces d'aujourd'hui, les noeuds de droite représentent les carrés codes mélangés.
J'ai fait en sorte que chaque pièces à gauche soit reliée par une arête à son carré code à droite. Mais j'ai aussi rajouté des arêtes inutiles pour vous embêter.
Votre tâche est de retrouver l'unique façon de faire correspondre les pièces avec les carrés codes par des arêtes. Ça s'appelle un
couplage parfait.
5 Décembre
Cette fois, j'ai
mélangé les pièces. Pour retrouver l'ordre correct, vous devez trier les nombres inscrits à gauche des pièces par ordre de qui se divise le mieux. L'image à côté du nombre qui se divise le moins bien se décode par le carré code
#. L'image à côté du nombre qui se divise le mieux se décode par le carré code
O. Tout le reste est dans l'ordre, vous verrez qu'il n'y a pas d'ambiguité.
6 Décembre
Aujourd'hui, j'ai encodé toutes les pièces avec
le même carré code. Pour trouver lequel, utilisez le programme Python suivant. Vous devez chercher
n et
m de sorte que la fonction
A renvoie 61. Caclulez alors
n*m%6 et vous aurez le numéro du carré code à utiliser. (Ils sont numérotés de 1 à 6 de haut en bas).
def A(m, n):
if m == 0:
return n+1
elif n == 0:
return A(m-1, 1)
else:
return A(m-1, A(m, n-1))
7 Décembre
Là encore j'ai été sympa, j'ai tout codé avec le même carré code. Pour savoir lequel, utilisez le graphe ci-dessous. Dans ce graphe, il y a des
arêtes pleines et des
arêtes pointillées, et un noeud marqué par un double trait. Je prétends qu'il existe une suite de "plein" et de "pointillé" telle que peu importe d'où vous partez, si vous suivez des arêtes du type indiqué par la suite, vous arriverez toujours au noeud marqué.
Le numéro du carré code à utiliser aujourd'hui est la longueur de la plus petite séquence de "plein" et "pointillé" qui a cette propriété.
Cela s'appelle un
mot synchronisant.
8 Décembre
Pas d'indice, vous devriez trouver tous seuls quelle pièce a été encodée comment.
9 Décembre
Je continue sur mon format simple pour l'instant, j'ai tout encodé avec le même carré code (j'espère que ça vous simplifie un peu le travail). Lequel ? Tout est inscrit dans le graphe ci-dessous.
Ce graphe contient un certain nombre de
cliques. Une clique, c'est k sommets différents qui sont totalement reliés entre eux. Cela signifie que si vous regardez deux des sommets, il y a forcément une arête entre les deux. Pour avoir une clique de taille k, il faut donc que chacun des sommets soit directement reliés aux k-1 autres !
La taille de la plus grande clique dans ce graphe est le numéro du carré code à utiliser aujourd'hui. Et pour votre information, ce problème de la
clique maximale est très difficile à résoudre (on ne connaît pas d'algorithme rapide qui trouve la plus grande clique d'un graphe).
10 Décembre
Comme d'habitude, un des carrés codes a été utilisé pour coder toutes les image. Pour retrouver lequel, déterminez le chiffre des dizaines dans le prochain élément de cette suite suite relativement connue.
18, 9, 28, 14, 7, 22, 11, 34, 17, ?
11 Décembre
Le programme ci-dessous affiche le numéro (toujours entre 1 et 6) du bon carré code... si vous arrivez au bout.
def h(x):
return not not x and g(x - (not not x))
def g(x):
return not x or h(x - (not not x))
a = 67091015026795951534974163063551679485
b = 14869428421844477043415143396333267370
c = 18130045244705851716678308487239340348
d = 27737016800392073340078206984446832421
e = 27050830777865150327799699254308046502
f = 31380753929535438225805729259152129373
print(h(a) + g(b) + h(c) + g(d) + h(e) + g(f))
12 Décembre
Comme d'habitude, un seul carré code a été utilisé pour tout encoder. Aujourd'hui, ils sont numéros de 0 (le plus haut) à 5 (le plus bas). Pour savoir quel carré j'ai utilisé, trouvez un chemin le plus long possible de s à t dans le graphe ci-dessous, et calculez sa longueur modulo 6.
13 Décembre
Les pièces sont de nouveau numérotées de 0 à 5. Trouvez p et q non triviaux tels que p×q = 142941853471579. Le numéro de la pièce aujourd'hui est égal au modulo 6 de p. Pour vous aider, sachez que le modulo 6 de q doit désigner la même pièce.
14 Décembre
Comptez le nombre de triangles dans le graphe du 9 Décembre. Un triangle, c'est quand trois noeuds sont complètement reliés entre eux (une clique de taille 3). Le résultat modulo 6 est le numéro du carré code permettant de décoder les pièces d'aujourd'hui, comptées de 0 à 5.
Pour les gens très chauds type
Dark Storm : Compter le nombre de mineurs isomorphes à K₃. Programme fortement conseillé.
15 Décembre
Comptez le nombre de façons différentes d'obtenir 15 par somme de 5, 2, 1 (sans prendre l'ordre en compte). Par exemple, 5+5+2+2+1, ou 2+2+2+2+2+2+1+1+1. Le nombre de façons modulo 6 est le numéro du carré code d'aujourd'hui.
Pour les gends très chauds type
Dark Storm : Compter le nombre de façons, toujours sans prendre l'ordre en compte, mais avec le parenthésage. Par exemple, ((5+5)+(2+2))+1 ou ((5+5)+2)+(2+1).
16 Décembre
Les carrés code sont encore numérotés de 0 à 5. Pour trouver le bon, déterminez le nombre d'arêtes minimum qu'il faut enlever pour couper la grille de taille 5 (ci-dessous) en deux parties :
Ça s'appelle une
coupe minimum.
Pour les gens très chauds type
Dark Storm : Trouver la coupe minimum du tore n×n pour tout n.
17 Décembre
Prenez la liste [7,4,2,5,1,3,6]. Elle n'est pas croissante, mais en supprimant des éléments on peut la rendre croissante. Par exemple, si je supprime 7, 4, 5 et 1, il me reste [2,3,6] qui est croissante. On appelle ça une sous-liste croissante (rien de surprenant ici).
Comptez le nombre de sous-listes croissantes de [7,4,2,5,1,3,6].
Pour les gens très chauds type
Dark Storm : Caractériser le nombre de sous-listes croissantes de taille 2 dans la liste [σ(i) : 1 ≤ i ≤ n] pour σ ∈ Sn (permutations de {1..n}).
18 Décembre
Aujourd'hui on ne fait pas très intellectuel, voici les pièces et leurs carrés codes associés, comme les premiers jours. Rassurez-vous, c'est pas aussi méchant.
19 et 20 Décembre
Pas de codage pour aujourd'hui. On arrive à la fin !
21 Décembre
Comptez le nombre de faces de la rosace au dos de la Graph 35+E II !
Il s'agit du nombre de face sur la rosace complète (la Graph 35+E II étant rectangulaire, elle n'est pas imprimée entièrement). Vous pouvez le faire sans quitter votre chaise, y compris si vous n'avez pas de Graph 35+E II.
Calculez le nombre de faces modulo 157, 97, 79 et 71. L'un de ces modulos a une parité différente des autres, et il correspond au carré code à utiliser pour déchiffrer les 8 pièces centrales.
22 Décembre Il y a des schémas de la rosace dans le manuel.
23 Décembre À cause des symétries de la rosace, il suffit de compter environ 4% des faces.
Fichier joint
Citer : Posté le 21/12/2019 18:14 | #
Le puzzle a l'air si joli :eyes:
Citer : Posté le 21/12/2019 18:15 | #
Oui, je me suis lâché sur le dessin
Citer : Posté le 21/12/2019 18:16 | #
On veut des cours de pixel aaart xD
Citer : Posté le 21/12/2019 18:17 | #
Pour un TDM peut-être ? Je me suis jamais considéré comme un artiste, surtout qu'il y avait Drak... ^^"
Citer : Posté le 21/12/2019 18:19 | #
Juste par curiosité, je vais tenter de résoudre le puzzle (même si j'ai rien fait depuis le début, ce qui est la pire strat de tous les temps)
Citer : Posté le 21/12/2019 20:11 | #
Pour le jour 16, il faut couper la grille en deux parties égales ?
Citer : Posté le 21/12/2019 20:46 | #
Juste par curiosité, je vais tenter de résoudre le puzzle (même si j'ai rien fait depuis le début, ce qui est la pire strat de tous les temps)
Lâche-toi !
Pour le jour 16, il faut couper la grille en deux parties égales ?
Non, il suffit de faire deux parties non vides.
Ajouté le 21/12/2019 à 22:05 :
Et... voici l'ultime problème que je vous pose dans ce Puzzle !
Comptez le nombre de faces de la rosace au dos de la Graph 35+E II !
Il s'agit du nombre de face sur la rosace complète (la Graph 35+E II étant rectangulaire, elle n'est pas imprimée entièrement). Vous pouvez le faire sans quitter votre chaise, y compris si vous n'avez pas de Graph 35+E II. Je donnerai des indices jusqu'à Mardi pour vous aider.
Calculez le nombre de faces modulo 157, 97, 79 et 71. L'un de ces modulos a une parité différente des autres, et il correspond au carré code à utiliser pour déchiffrer les 8 pièces centrales.
Vouz avez désormais tous les éléments nécessaires pour reconstituer intégralement l'image parfaite.
Merci à tous ceux qui ont pris le temps de décoder les pièces et problèmes. Et que le plus rapide gagne !
Ajouté le 22/12/2019 à 17:24 :
Petit indice pour aujourd'hui. Il y a des images de la rosace dans les manuels, si vous cherchez bien.
Citer : Posté le 23/12/2019 16:27 | #
MP Envoyé
Citer : Posté le 23/12/2019 17:05 | #
Participation reçue de Filoji !
Score de 8029/8192 pixels exacts, soit 98%.
Excellent ! Tu as quasiment tout juste sur toutes les pièces. Que dire... ?
Ajouté le 23/12/2019 à 18:30 :
Petit indice supplémentaire pour aujourd'hui : compte tenu des symétries dans la rosace, il suffit de compter environ 4% des faces pour obtenir le résultat.
Citer : Posté le 23/12/2019 20:48 | #
Bravo Filoji
Citer : Posté le 23/12/2019 20:57 | #
Deuxième envoi de Filoji.
Score de 8192/8192 pixels exacts, soit 100%.
Bravo Filoji, tu es officiellement le troisième Maître du Puzzle de Planète Casio ! Et tu remportes cet événement haut la main, ce qui n'est pas une broutille. Ça valait le coup de persévérer !
Ajouté le 23/12/2019 à 21:05 :
Le puzzle est désormais résolu. Bravo Filoji !
Il va probablement falloir un moment avant que mon contact chez Casio ne m'envoie la Graph 35+E II qui est le lot de l'événement (désolé pour ça, il est surchargé, et c'est pas faute de s'y être pris à l'avance). Dès qu'elle arrive, je te prépare tout ce qu'il faut pour te l'envoyer.
D'ici là, toute personne capable de reconstituer 90% de l'image avant demain soir recevra aussi le titre de Maître du Puzzle. Essentiellement si vous avez compris le décodage et compris de quoi parlent les problèmes, vous devriez pouvoir y arriver sans difficulté majeure.
Je vais continuer de distribuer des indices à qui en veut.
Notez également que je publierai une image complète et les solutions des problèmes à Noël, préparés spécialement pour vous.
Citer : Posté le 23/12/2019 22:04 | #
Bravo Filoji !
Citer : Posté le 23/12/2019 22:07 | #
Félicitations Filoji, tu as grandement mérité ta superbe Graph 35+E II que tu connais maintenant sous ses moindres coutures n'est-ce pas ?
Sinon, tu ne m'as pas répondu par ici pour l'expédition de ton autre lot :
https://www.planet-casio.com/Fr/forums/topic16051-3-resultat-du-concours-de-rentree-2019-epreuve-de-basic.html#172465
Citer : Posté le 24/12/2019 10:29 | #
Pas d'autres amateurs ?
N'hésitez surtout pas à raconter ce que vous avez fait et si vous avez trouvé certains aspects trop difficiles. Je veux faire de mon mieux pour améliorer la formule la prochaine fois, et ce n'est pas possible sans les retours de ceux qui ont essayé.
Citer : Posté le 24/12/2019 10:49 | #
Je n'aime pas la partie puzzle pour être honnête, mais j'ai trouvé les énigmes individuelles de la seconde partie très intéressantes.
Citer : Posté le 24/12/2019 22:43 | #
Participation reçue de Afyu ! Une perle cachée !
Pas encore finie, mais Afyu obtient quand même un score de 6519/8192 pixels justes, soit 80% !
Ajouté le 25/12/2019 à 08:35 :
Nouvelle participation de Afyu avec un score de 6774/8192, soit 83%.
Cette nouvelle participation est un gros progrès visuellement, même si le score a pas trop monté. Bien joué !
Je prends les participations jusqu'à ce que la news d'aujourd'hui soit publiée au moins.
Ajouté le 25/12/2019 à 11:28 :
L'image est maintenant publiée. J'ai donné aussi le titre à Afyu pour l'effort monstrueux de code et de décodage en Python (j'espère qu'il donnera les détails !).
Je vais publier sous peu un PDF avec l'ensemble des problèmes et leurs solutions, pour les curieux.
Ajouté le 25/12/2019 à 16:06 :
Malgré l'annonce, Afyu continue d'améliorer sa soumission avec 7290/8192 pixels justes, soit 89%. Quel effort !
Citer : Posté le 25/12/2019 20:47 | # |
Fichier joint
Et voilà le PDF avec les solutions des problèmes. N'hésitez pas à y jeter un œil ! Aperçu ci-dessous.
Citer : Posté le 25/12/2019 21:03 | #
Bravo à Filoji et Afyu !
Citer : Posté le 26/12/2019 10:01 | #
Une question : as tu toujours les les pièces à décoder qui était trop compliqué ? On pourrait s'amuser à les faire
Citer : Posté le 26/12/2019 11:07 | #
Ah, je vois ce que tu veux dire. Non, je les ai surtout faites au fur et à mesure, donc je ne les ai pas.
Mais l'idée initiale était d'éviter que vous tentiez toutes les possibilités à la main et d'utiliser du coup des séquences de codes. Par exemple pour le chemin le plus long dans le graphe, j'aurais mis des codes sur les arêtes et il aurait fallu appliquer tous les codes le long du chemin.
Ça renforce la "sécurité" du truc mais par contre ça vous aurait pris des plombes... x)
N'abandonnant toujours pas, Afyu a soumis sa dernière version avec pas moins de 8114/8192 pixels justes, soit 99% ! Ce qui fait deux résolutions complètes ou quasi-complètes du puzzle, comme l'année dernière.
Citer : Posté le 26/12/2019 11:40 | #
Bonjour,
Je viens (enfin !) poster sur le forum.
Bravo à Filoji pour la résolution du puzzle !! Pour avoir longuement essayé, je sais que ça représente un sacré boulot et un paquet d'heures !
Bravo également à Lephenixnoir pour la construction de cet impressionnant puzzle avec de nombreuses, variées et instructives énigmes !
Il fallait résoudre les énigmes quotidiennes, puis décoder les pièces du puzzle, puis les assembler dans le bon ordre.
Faute de temps en décembre, j'ai regardé les énigmes quotidiennes presque quotidiennement mais je n'avais pas trop de temps pour le décodage et ça m'a fait un peu peur d'avoir autant de pièces à décoder. D'autant plus que je ne suis pas un expert en programmation.
Puis les vacances sont arrivées et je me suis finalement lancé dimanche midi (oui, le 22/12 ! à 3 jours de la fin...) pour la partie programmation du décodage. J'ai même hésité à le faire avec Paint (Kolourpaint, précisément) avec les retournements/miroir... Ça aurait été plus rapide à décoder, mais pas réutilisable s'il faut changer de carré de décodage et tout refaire ou s'il faut décoder les 6 pièces du jour avec le même carré de décodage. J'ai programmé le décodage en Python. Je vous montrerai tout ça bientôt
Si vous voulez quelques détails tout de suite : j'ai utilisé le module PIL(LOW) de Python et les fonctions getpixel et putpixel avec quelques conditions et beaucoup de repérage à la main pour compter les colonnes et les lignes. Je n'ai pas suivi le conseil préconisant de réduire les images au format 8x8 alors qu'elles sont en 16x16. J'ai tout calculé sur les images proposées.
En fait, j'ai eu beaucoup plus de mal à remettre les pièces dans l'ordre qu'à les décoder. Pour les remettre dans l'ordre, j'ai utilisé Kolourpaint avec lequel j'ai tracé une grille (rouge) constituée de cases (blanches) de 16x16 pixels, dans lesquelles j'ai déplacé, déplacé et encore déplacé mes pièces décodées, jusqu'à trouver le bon ordre. Il est troublant de ne pas avoir en noir le haut des arbres...
Je compte fournir un dernier effort pour la résolution du puzzle, mais un dernier hein ! J'ai encore quelques pièces qui ne sont pas très "propres" visuellement. Je pense que j'ai choisi un mauvais carré de décodage pour certaines pièces et ça donne presque ce qu'il faut, mais certaines lignes de pixels sont coupées. Je vais revoir ça une dernière fois, avant d'aller voir l'image résolue.
Je prendrai le temps d'expliquer ma méthode et ma réflexion autour des énigmes quotidiennes. @Lephe m'expliquera sous quelle forme je peux fournir une telle explication pour qu'elle soit visible de toutes et tous
Merci @Lephe d'avoir pris le temps de noter mes participations, même après la date limite.
Merci @Massena.
Passez une bonne journée ! À bientôt pour mes explications