Seuls les membres ayant 30 points peuvent parler sur le chat.

Forum Casio - Actualités


Index du Forum » Actualités » Le Puzzle de l'Avent 2019
LephenixnoirEn ligneAdministrateurPoints: 16841 Défis: 140 Message

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


Pages : Précédente1 ... , 3, 4, 5, 6, 7, 8, 9, 10, 11Suivante
LephenixnoirEn ligneAdministrateurPoints: 16841 Défis: 140 Message

Citer : Posté le 10/12/2019 08:50 | #


Une clique de taille 2 c'est juste deux noeuds reliés par une arête.

Une clique de taille 3 c'est un triangle.

Une clique de taille 4 c'est un carré avec les diagonales.

Ça te parle jusque-là ? Il y des exemples sur Wikipédia, dans l'article que j'ai lié.
KikoodxHors ligneMembrePoints: 1754 Défis: 9 Message

Citer : Posté le 10/12/2019 08:57 | #


Je trouve que les explications de Lephé sont très claires, j'ai compris même si je n'ai pas une moindre idée de ce qu'est un graphe

Jour 6 :
Dimanche est passé, j'ai trouvé deux types d'entrées qui font boucler vais en donner deux :
A(a, b) avec a et/ou b négatif
A(a, b) avec a et/ou b avec une partie entière et une partie décimale
J'ai trouvé les paramètres retournant 61 durant mes tests d'ailleurs (par pur hasard )

(J'ai un peu détourné les règles il est vrai )
Grâce à ton programme j'ai appris que la limite de récursion en Python par défaut est d'environ 1000.
BulitoHors ligneMembrePoints: 117 Défis: 3 Message

Citer : Posté le 10/12/2019 09:02 | #


61, pareil, je l'ai trouvé totalement au hasard.
à cause de la limite Python, je ne pouvais même pas me faire un petit programme Python qui tourne tout seul (j'aurais pu mais la flemme).
Finalement j'ai essayé à la main et j'ai trouvé en 10 coups.
Après, le nom "A()" pour une fonction, tu as juste la flemme de trouver un nom

Sinon pour le graphe d'hier, est-ce que le point tout en haut et celui tout en bas sont considérés comme reliés ?
N'hésitez pas à me MP pour des échanges d'indices pour le Puzzle de l'Avent 2019 !
LephenixnoirEn ligneAdministrateurPoints: 16841 Défis: 140 Message

Citer : Posté le 10/12/2019 09:13 | #


Kikoodx a écrit :
Dimanche est passé, j'ai trouvé deux types d'entrées qui font boucler vais en donner deux :
A(a, b) avec a et/ou b négatif
A(a, b) avec a et/ou b avec une partie entière et une partie décimale

Aaaah mais j'ai jamais précisé parce que ça me paraissait évident... cette fonction est définie pour n et m deux entiers naturels !

Grâce à ton programme j'ai appris que la limite de récursion en Python par défaut est d'environ 1000.

Oui ; tu peux toujours la changer avec sys.setrecursionlimit().

Bulito a écrit :
Après, le nom "A()" pour une fonction, tu as juste la flemme de trouver un nom

Non, cette fonction a un nom canonique et elle est souvent abrégée A(). Je l'ai appelée comme ça sans m'en rendre compte et ai eu peur d'avoir donné une information sans faire exprès quand je m'en suis rendu compte. ^^"

Sinon pour le graphe d'hier, est-ce que le point tout en haut et celui tout en bas sont considérés comme reliés ?

Non. Les chemins formés de plusieurs arêtes ne comptent pas pour les cliques. Et là il n'y a pas d'arête directe (même si on peut se demander).
KikoodxHors ligneMembrePoints: 1754 Défis: 9 Message

Citer : Posté le 10/12/2019 09:24 | #


Lephenixnoir a écrit :
Aaaah mais j'ai jamais précisé parce que ça me paraissait évident... cette fonction est définie pour n et m deux entiers naturels !

Je m'en doutais bien, c'est pour ça que j'ai essayé ces nombres
J'ai aussi trouvé une "propriété" de ton système :
Avec a nombre entier naturel
A(a, a) est assez proche de a³ (avant a = 4 j'en suis sûr, après la récursion est juste trop grande mon PC ne supporte pas). J'aimerais donner plus d'exemple mais ce serait donner des indices :/
A(1, 1) = 3 ; 1³ = 1
A(2, 2) = 7 ; 2³ = 8

(L'assez proche ne transparaît pas beaucoup avec ces exemple ^^')
LephenixnoirEn ligneAdministrateurPoints: 16841 Défis: 140 Message

Citer : Posté le 10/12/2019 09:28 | #


Kikoodx a écrit :
A(a, a) est assez proche de a³ (avant a = 4 j'en suis sûr, après la récursion est juste trop grande mon PC ne supporte pas).

Indice : si ça ne marche pas pour a=4 c'est que ça monte (beaucoup) plus vite que a³.

C'est plus efficace de chercher par lignes.
Dark stormEn ligneMembre d'honneurPoints: 10920 Défis: 176 Message

Citer : Posté le 10/12/2019 10:08 | #


Après en cherchant un peu, on tombe facilement sur la fonction en question. Qui a en effet des propriétés intéressantes. On voit bien que Lephe a fait un stage à l'INRIA si je me trompe pas
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
LephenixnoirEn ligneAdministrateurPoints: 16841 Défis: 140 Message

Citer : Posté le 10/12/2019 12:43 | #


C'est exact (à Paris, en 2018), mais ce n'est pas du tout là que ça vient. D'ailleurs c'était en prépa que je l'ai vue pour la première fois.

Pour ceux qui la cherchent encore, elle joue un rôle historique assez important car elle n'est pas récursive primitive.

Ajouté le 11/12/2019 à 21:06 :
Argh il fallait bien que j'oublie de poster les pièces un jour. Désolé pour la confusion... >_>

Voici les pièces d'hier, donc. 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, ?


Ajouté le 11/12/2019 à 22:07 :
Voilà également les pièces pour aujourd'hui.


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))
MassenaHors ligneRédacteurPoints: 1051 Défis: 5 Message

Citer : Posté le 12/12/2019 08:20 | #


...
Pardon ? X)
Peace was never an option. - Untitled goose game, 2019
LephenixnoirEn ligneAdministrateurPoints: 16841 Défis: 140 Message

Citer : Posté le 12/12/2019 09:20 | #


Quelque chose est pas clair dans l'énoncé ?
Dark stormEn ligneMembre d'honneurPoints: 10920 Défis: 176 Message

Citer : Posté le 12/12/2019 09:38 | #


Plus simple que prévu ce défi

Ajouté le 12/12/2019 à 09:44 :
Au passage, il est assez aisé de démontrer le comportement de cet algo par une démonstration par récursion (au programme de première de mémoire)
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
MassenaHors ligneRédacteurPoints: 1051 Défis: 5 Message

Citer : Posté le 12/12/2019 10:48 | #


Quand je regarde l'algorithme, j'ai l'impression que la fonction h(x) fait appel à la fonction g(x) et vice-versa...
En gros je comprends pas du tout l'algorithme xD
Peace was never an option. - Untitled goose game, 2019
LephenixnoirEn ligneAdministrateurPoints: 16841 Défis: 140 Message

Citer : Posté le 12/12/2019 10:49 | #


C'est ça, ces deux fonctions sont mutuellement récursives.

Si tu n'arrives pas à comprendre, lance-les sur des exemples, tu verras très vite.
MassenaHors ligneRédacteurPoints: 1051 Défis: 5 Message

Citer : Posté le 12/12/2019 11:09 | #


Si on recopie tout le programme, ça passe ?
Peace was never an option. - Untitled goose game, 2019
LephenixnoirEn ligneAdministrateurPoints: 16841 Défis: 140 Message

Citer : Posté le 12/12/2019 11:33 | #


Tu peux mais la dernière ligne va mettre très longtemps à calculer.
Dark stormEn ligneMembre d'honneurPoints: 10920 Défis: 176 Message

Citer : Posté le 12/12/2019 11:50 | #


En fait, elle va même faire planter le programme, vu qu'elle est "trop" récursive pour les entrées en question.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
LenoHors ligneMembrePoints: 262 Défis: 0 Message

Citer : Posté le 12/12/2019 18:15 | #


Est-ce que les pièces, une fois trouvée peuvent subir des rotations pour s'assembler avec le reste de l’image ?
Seid ihr das essen ? Nein ! Wir sind der Jaeger !
LephenixnoirEn ligneAdministrateurPoints: 16841 Défis: 140 Message

Citer : Posté le 12/12/2019 18:18 | #


Une fois décodées, les pièces sont toutes dans le bon sens. Il n'y a aucune rotation à faire pour reconstituer l'image
LenoHors ligneMembrePoints: 262 Défis: 0 Message

Citer : Posté le 12/12/2019 18:19 | #


Ok merci c'est déjà plus simple comme ça.
Seid ihr das essen ? Nein ! Wir sind der Jaeger !
YoustonesHors ligneMembrePoints: 328 Défis: 0 Message

Citer : Posté le 12/12/2019 21:39 | #


Euh je reviens comme ça (exams à la chaîne) mais pourquoi dans l'exemple Wikipedia il mettent le dernier en rouge ?
Mon cerveau se répète tous les jours la mythique phrase : "Houston, je crois que nous avons un problème"
LephenixnoirEn ligneAdministrateurPoints: 16841 Défis: 140 Message

Citer : Posté le 12/12/2019 21:45 | #


Parce que c'est une 4-clique ! L'image illustre la recherche d'une 4-clique et tous les schémas en bleu n'en sont pas. Celui en rouge en est une !
Pages : Précédente1 ... , 3, 4, 5, 6, 7, 8, 9, 10, 11Suivante

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2020 | Il y a 94 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd