Algo de résolution d'une énigme Assassin's Creed - Page 1

Je rejouais à Assassin's Creed Brotherhood, et une des énigmes du jeu consiste à superposer des signaux, dont l'amplitude s'ajoute/s'annule entre eux, pour reproduire la solution donnée.
Plus les énigmes progressent, plus le nombre de signaux disponibles (connu) et le nombre de signaux à superposer (inconnu) augmente. On peut aussi bien avoir 6 signaux dispos et 4 à additionner, que 12 dispos et 3 à additionner.

Exemple de la dernière énigme :

(en blanc le signal à obtenir, en bleu le résultat du cumul actuel)

Dans les premiers, le résultat était assez simple, il suffit de regarder deux minutes pour trouver la combinaison.
Par la suite, je me suis mis à les réduire à l'état de nombre (chaque signal étant quatre courbes d'amplitude 4 à -4) en cherchant quelles combinaisons pouvaient former la première courbe, puis sur les signaux restants quelles combinaisons pouvaient former la seconde, etc.
Vers la fin, en gagnant en complexité, je me suis mis à écrire un script qui allait résoudre pour une combinaison de jusqu'à 4 signaux, avec une imbrication de quatre boucles.
Sur le dernier, j'ai refait le script en utilisant une récursive pour résoudre n'importe quel combinaison max donnée (pour 18 signaux par exemple, je sais qu'il ne peut y avoir que de 2 à 18 signaux cumulés).

Je propose aux intéressés de donner leur version, dans le langage de leur choix (langage "lisible" si possible ) de leur façon de résoudre cette énigme.
Pour résumer : on peut voir un signal comme des tableaux de 4 entiers compris entre 4 et -4, et le cumul des signaux est une simple addition de ces tableaux ([0, 1, 2, 3] + [4, -3, 0, 0] = [4, -2, 2, 3]).
Pour un signal solution donné, et une série de signaux donnés (les deux étant écrits en dur dans le code, faisons au plus simple), proposez un code qui permet de trouver une (ou toutes, mais l'important reste de résoudre l'énigme) solution, sachant que ce code doit être réutilisable d'une énigme à l'autre en changeant uniquement le contenu des variables de la solution et des signaux à utiliser.

L'ayant fait à domicile, je proposerai ma version une fois rentré chez moi.

Donc le but du jeu est de finir a Zero, donc je sors ma carte :

Zerosquare !!!!



GT a Zéro

Un peu occupé avec d'autres projets pour le moment, mais je suppose qu'une des solutions les plus simple est de calculer les combinaisons possibles pour le premier fragment de signal, puis appliquer ces combinaisons aux fragment suivants, etc.

Par contre comme c'est réfléchi en deux minutes, ça doit être loin d'avoir une bonne complexité. Je dirais que c'est du O(n^2), avec n le nombre de signaux.

Ce problème est NP-complet car le subset sum problem se réduit à lui. Celui qui trouve un algorithme dans O(n²) devient millionnaire

Ta méthode a une complexité quadratique seulement si les solutions combinent 2 signaux, ce qui n'est pas le cas. En l’état actuel de la science, le meilleur algorithme pour résoudre ce problème peut être polynomial pour certains ensembles de signaux, mais sera toujours exponentiel pour certains autres ensembles. Le défi consiste donc à trouver un algo aussi rapide que possible pour le plus grand nombre possible d'ensembles rencontrés en pratique.

[edit]
J'ai oublié ci-dessus que les valeurs des signaux sont restreintes entre -4 et +4, donc c'est seulement un cas particulier du subset sum problem qu'on peut réduire. En réalité, il pourrait exister un algorithme polynomial (peut-être par programmation dynamique)