La partie de poker du désert à peine finie, voilà qu'une tempête de sable approche. Et c'est ce moment-là que la femme lutin qui vous sert de guide choisit pour disparaître. Curieusement, elle venait justement de vous dire quelque chose à propos des fantômes du désert.
Heureusement, elle vous a laissé des cartes. Enfin, des cartes, c'est un bien grand mot, c'est en fait une ligne d'instructions suivie d'une liste de nœuds connectés les uns aux autres, par exemple :
RL
AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)La première ligne veut dire : prenez à droite, puis à gauche.
Les lignes suivantes veulent dire :
- à gauche et à droite du nœud AAA, il y a les nœuds BBB et CCC ;
- à gauche et à droite du nœud BBB, il y a les nœuds DDD et EEE ;
- etc.
Première partie
Il faut suivre les instructions pour arriver du départ AAA jusqu'à l'arrivée ZZZ. Et si on arrive au bout des instructions mais qu'on n'a pas encore atteint l'arrivée, on continue en repartant au début des instructions.
Deuxième partie
On ne s'en sort pas, ces instructions nous font juste tourner en rond.
Mais au fait, vu que le lutin était un fantôme, ce ne seraient pas des instructions pour fantômes par hasard ? Et comme chacun sait, les fantômes sont doués d'ubiquité et partent donc de plein de points de départ à la fois (tous les nœuds qui finissent par un A), dans le but d'atteindre autant de points d'arrivée en même temps (les nœuds qui finissent par un Z).
Une fois que vous aurez résolu ce nouveau problème un brin plus compliqué, vous pourrez continuer à tourner en rond dans le désert, parce que vous n'êtes pas un fantôme, vous, et que la solution pour fantôme, eh bien ça ne va pas vous faire avancer en fait.
# Partie 2
Posté par 🚲 Tanguy Ortolo (site web personnel) . Évalué à  5.
Juste un mot sur la partie 2. En force brute évidemment, ça prendrait des mois. Il y a une astuce évidemment, seulement avec l'énoncé seul, je ne crois pas qu'il y ait moyen de soupçonner de quoi il s'agit.
En fait l'astuce ne vient pas des règles du jeu, mais des données elles-mêmes, qui sont conçues pour que les fantômes tournent en rond. Je ne vous en dit pas plus.
[^] # Re: Partie 2
Posté par Christophe . Évalué à  3.
C'est un peu frustrant du coup: tout l’intérêt de cette énigme repose sur les données d’entrée, qu'on n'a pas ici.
Ou alors j'ai encore raté un truc.
[^] # Re: Partie 2
Posté par Elfir3 . Évalué à  2.
Déjà , je trouve qu'il manque la seconde partie de l'énoncé pour bien saisir l'intérêt (même si on peut se douter de ce qu'elle contient), et de fait les données à tester ne sont disponibles que si t'es connecté au site.
[^] # Re: Partie 2
Posté par rewind (Mastodon) . Évalué à  5.
Si les données n'étaient pas bien conçues, si je ne dis pas de bêtise, il faudrait utiliser le théorème des restes chinois pour résoudre le problème, ce qui enverrait ce problème dans une autre dimension niveau difficulté.
[^] # Re: Partie 2
Posté par vicnet . Évalué à  -3.
Non, c'est plus simple que le théorème des restes, une notion de math qu'on voit en collège (peut être plus tard maintenant…).
Il faut changer de paradigme entre le 1er jeu et le 2è.
Pour le 1er, en appliquant un algo en parcourant la map pas Ă pas, ca fonctionne et c'est rapide.
Pour le 2e, ce même algo n'aboutit pas mais les infos sont la, ils faut les traiter différement… je vous laisse chercher
[^] # Re: Partie 2
Posté par Yth (Mastodon) . Évalué à  2.
Je pense, en effet, que ce théorème aurait permit de résoudre le cas où les cycles ne commencent pas tous à 0.
Là on a une situation où les restes sont tous nuls, donc tout de suite, ça simplifie…
[^] # Re: Partie 2
Posté par YetiBarBar . Évalué à  1.
C'est presque vrai…
Dans le cas d'un depart desynchronisé, pour appliquer le crt, il faudrait aussi que les durées des cycles soient premières entre elles…
[^] # Re: Partie 2
Posté par Yth (Mastodon) . Évalué à  2. Dernière modification le 08 décembre 2023 à 14:43.
En fait, les données tournent forcément en rond.
Avec mes données :
On a 269 actions, et 750 positions.
Il est obligatoire qu'en 269*750 = 201750 déplacements on ait bouclé, pour chaque fantôme.
Il y a 6 fantĂ´mes.
On va donc chercher la longueur du cycle, et toutes les sorties (zone en ..Z) possibles à partir d'une entrée (..A).
Dès qu'on retombe sur la première sortie trouvée, ET qu'on en est au même point dans le programme : on a fait une boucle.
Il se trouve que :
* toutes les longueurs de boucles (entre deux passages sur une même sortie) sont divisibles par 269, on a donc un vrai cycle dès qu'on retombe sur la première sortie visitée ;
* on tombe, pour chaque entrée, sur une et une seule sortie, donc chaque cycle est indépendant ;
* la durée pour tomber sur la sortie une première fois est la même que la longueur du cycle, donc tous les cycles commencent au même point dans le temps : 0.
Ex: A -> [n-1 Ă©tapes] -> Z -> [n-1 Ă©tapes] -> Z -> [n-1 Ă©tapes] -> Z
Le cycle fait n de long, n est un nombre entier de fois le programme exécuté (n divisible par 269), et démarrer en A est équivalent à démarrer en Z.
Ça simplifie à mort, puisqu'en pratique il ne reste plus qu'à calculer le PPCM des longueurs de cycles.
Si ça n'avait pas été le cas, les cycles auraient été beaucoup plus longs, mais toujours inférieurs à 169*750 = 201750, ce qui se calcule vite.
Par contre on aurait pu avoir des périodes de démarrage où on parcours quelques zones, avant de « tomber » sur un cycle, et de rester dedans, ils auraient pu ne pas commencer au même moment.
Et lĂ le PPCM des cycles ne permet que d'avoir la longueur du super-cycle de l'ensemble des 6 fantĂ´mes, mais pas le moment oĂą ils se trouvent tous sur une sortie en mĂŞme temps.
Ce qui pourrait ne jamais arriver, et c'est probablement pour ça que le problème est « aussi simple », ça aurait peut-être été trop difficile de s'assurer qu'il y ait une solution, et que cette solution soit effectivement calculable rapidement ?
J'ai pas d'idée géniale, là tout de suite, sur comment résoudre ce problème là , mais la force brute n'est pas une solution, mon propre super-cycle faisant presque 12000 milliards, la solution on va pas tomber dessus par hasard.
J'ai failli tenter de résoudre le gros problème, mais heureusement j'ai d'abord regardé mes cycles, et la simplicité m'a fait prendre le raccourci d'un PPCM multiple vite fait.
PS: ça me rappelle une histoire de Tetris l'année dernière, avec des cycles de dingue et beaucoup de méninges triturées :)
[^] # Re: Partie 2
Posté par vicnet . Évalué à  1.
Ah, je ne me suis même pas posé la question de l'indépendance des cycles.
Du coup, j'ai tenté le PPCM et comme c'était bon, je suis passé à la suite (ca le lendemain).
Merci pour cette remarque.
[^] # Re: Partie 2
Posté par mac__ . Évalué à  2. Dernière modification le 08 décembre 2023 à 15:46.
Oui, non seulement qu'ils tournent en rond, mais qu'ils finissent quand même pas arriver à la sortie au même moment…
On peut facilement faire un exemple où les fantômes tournent en rond mais n'arrivent jamais à une sortie en même temps, auquel cas le problème n'aurait aucune solution.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.