View Single Post

Dici's Avatar


Dici
10.15.2012 , 04:46 AM | #13
Je suis désolé pour la longueur j'ai édité 15 fois pour raccourcir mais j'aimerais être compris ! Dans le pire des cas je peux fournir le programme en Pascal et tu pourras tester en jeu (oui je sais c'est vieux mais on m'a appris que ça en prépa !).

Tout d'abord merci d'être passé Xhylette, les politesses étant rendues je vais éclaircir quelques points !

Premièrement la partie que tu as citée avait pour seul but de prouver que si la solution existe (et je me demande si la solution existe car rien ne dit que le jeu, lorsqu'il réinitialise l'énigme, ne choisit pas exprès une configuration soluble parmi d'autres non solubles) alors on peut la raccourcir à moins de 9 coups.

Pour cela je définis en quelques sortes 9 fonctions : F1 ... F9. Utiliser F1 consiste à appuyer sur le pylône numéroté 1 etc, et cela modifie tous les pylônes reliés. Mon argumentation réside en deux points :

- pour tout i, Fi o Fi = id où "o" est le signe de la composition et id est la fonction identité
- pour tout i et tout j, Fi o Fj = Fj o Fi (c'est là que je parle de concaténation de deux listes non ordonnées, j'avais choisi comme structure des listes non ordonnées de pylônes pour représenter un pylône, oublie ça même si je trouvais ce choix astucieux, car si ce résultat est simple à comprendre, il faut pouvoir l'amener rigoureusement)

Ces deux arguments suffisent à dire que pour toute solution, on peut se ramener à neuf coups au pire.
Par exemple : F1 o F2 o F1 o F5 o F7 = F1 o F1 o F2 o F5 o F7 = F2 o F5 o F7

Pour prouver que je pouvais toujours faire cela, il me fallait l'involutivité des Fi ainsi que leur commutativité par rapport à la composition. Avec ça, j'ai juste donné la preuve qu'il ne sert à rien de s'affoler sur les boutons et qu'on doit cliquer maximum une fois sur chaque pylône.


Maintenant, l'existence. Je n'aurais pas dû te presser parce que du coup tu n'a spas tout lu ! Si tu te reportes à mon post de la première page où il y a des tas de schémas, j'y donne la solution explicite du problème ; c'est bien une solution que j'expose pas une réflexion inaboutie.

L'idée c'est que je regarde quels pylônes sont éteints, et je vais m'arranger pour les allumer un par un sans modifier le reste du circuit.

Pour faire ça, il suffit de voir qu'il y a 3 types de pylônes (reliés au centre, non reliés au centre, centre). Dès lors, on cherche :

- 1 /comment allumer le centre sans changer l'état des autres (il y a des étapes intermédiaires durant lesquels les autres pylônes vont changer mais au bout du compte on retrouvera les mêmes états sauf le centre, qui sera allumé plutôt qu'éteint)
- 2/ comment allumer un pylône relié au centre sans changer les autres
- 3/ comment allumer un pylône non relié au centre sans changer les autres

Il suffit alors d'utiliser les symétries du montage et un peu d'intuition pour trouver :

1/ il faut cliquer sur le centre et sur tous les pylônes reliés au centre. Au final, seul le centre a changé d'état.

2/ Il faut cliquer sur tous les pylônes sauf le pylône à allumer, les deux premiers pylônes à sa droite, les deux premiers pylônes à sa gauche. Au final, seul le pylône à allumer a changé d'état.

3/ il faut modifier tous les pylônes sauf le centre, le premier pylône à droite du pylône à allumer et le pylône. Au final, seul le pylône à allumer a changé d'état.

Tu peux tester au papier, ça marche. Ensuite, tu comptes pour chaque pylône le nombre de fois que tu devras cliquer, si c'est impair tu cliqueras une seule fois, sinon tu ne cliqueras pas du tout.
Cette décomposition en 3 sous-problèmes montre aussi que toutes les configuration imaginables sont accessibles depuis n'importe quelle autre puisqu'on peut séquentiellement éteindre un pylône sans modifier les autres.

------------------------------------------------------------------------------------------------------------------------------------------------------

PPS : pour la complexité ce calculs, je te rassure tout de suite ce problème n'est pas du tout encombrant. En fait, il est même très léger puisque cette solution le résout avec une complexité O(n)... C'est plus court que le plus court des algorithmes de tri d'un tableau d'entiers.
C'est parce que le tableau est totalement aléatoire et n'a aucune propriété tandis que dans le cas de Traken, le montage dispose de qualités intrinsèques que j'ai utilisées pour réussir à allumer un pylône donné sans modifier les autres au bout du compte.