Demi-Finale 2010: Android Unlock

Bonjour les gens.

J'ai une petite question relative à ce sujet de demi-finale que j'essaie de résoudre. Comme il est tard je vais peut-être dire des bêtises, mais il me semble que les exemples donnés dans l'énoncé sont faux (ou alors c'est moi qui ait sûrement mal compris la question). Et puis évitez de lire si vous n'avez pas réfléchit au sujet, des fois que je dise des trucs intelligents qui risqueraient de vous mettre sur la piste.

Dans l'exemple "1 2 3", on cherche les motifs à 3 sommets partant de la case (1,2). J'en compte 49 et l'exemple nous dis 37. Or j'ai bien l'impression que mes 49 motifs sont valables. Numérotons pour simplifier nos cases de 0 à 9 : (0,0) = 0, (0,1) = 1, (0,2) = 2, etc.
On part donc de la case 5, depuis laquelle 7 cases exactement sont accessibles : les cases {0,1,2,4,6,7,8} = A. Notons que chacune de ces cases est aussi voisine de la case numéro 3.
_ Mettons que je veuille tracer un motif à partir de 5, qui est allumé.
_ Je pars d'abord sur une des cases de A --> 7 possibilités.
_ Depuis là, quitte à revenir sur la case numéro 5, je peux accéder à n'importe quelle autre case du pavé, il en reste 7 ...
_ Etant donné qu'on tient compte de l'ordre d'allumage des cases, cela fait bien 7×7 = 49 possibilités.

Alors du coup soit l'énoncé est mal foutu (mais bon ça ... :rolleye:), soit l'exemple est foireux, soit j'ai loupé un truc dans la question (hypothèse la plus vraisemblable s'il en est).

You fail. RTFS (read the fucking sujet).
Depuis la case (1,2), tu as bien 7 possibilités, mais après selon les cases, ce n'est pas pareil, tu ne peux pas retourner sur une case déjà allumé, tu ne peux que sauter par dessus, c'est à dire des mouvement du types ±2 à x et/ou y si la case ±1 est allumé, il n'y a que 16 cas :

• (0,x)↔(2,x) possibles si (1,x) est allumé.
• (x,0)↔(x,2) possibles si (x,1) est allumé.
• (0,0)↔(2,2) et (0,2)↔(2,0) possibles si (1,1) est allumé.

C'est la seule manière de faire des mouvements avec dx≡0 mod 2 et dy≡0 mod 2.

Tu part de (1,2), tu as donc quatre groupes de possibilités:

• (12) Un autre côté : (0,1) ou (2,1).
  Depuis lequel tu as six choix : les sept cases qui sont éteintes moins l'opposée qui est trop loin.
• (7) Le centre : (1,1).
  Depuis le quel tu as sept choix : les cases éteintes.
• (10) Un angle proche : (0,2) ou (2,2).
  Cinq choix : sauter au-dessus de (1,2) plus deux saut cavaliers plus les deux cases voisines éteintes.
• (8) Un angle opposé: (0,0) ou (2,0).
  Quatre choix : les trois cases voisines plus un saut cavalier.

12+7+10+8 = 37. EQD !!

Je suis désolé mais dans le fuckin' sujet, ce n'est marqué nulle part. Enfin en gros, on a le droit à des chemins qui repassent plusieurs fois par un même sommet, mais pas par une même arête. EDIT : Rha merde non j'ai encore dit une connerie. N'empêche que le concept de "sauter par dessus une case allumée", je trouve pas ça très propre ...

Bon c'est dommage ça m'a toujours l'air vaguement NP-Complet comme truc. Mais bon au moins je vais pouvoir écrire un algo' qui fait ce qu'on lui demande xD

Euh, vu que le nombre limite de case à activer est fini, c'est pas un problème np-complet, il "suffit" de construire un arbre et ca doit aller, non ?

Non mais évidemment stu te limites à des instances de problèmes de taille bornée, tu auras généralement un nombre borné de solution et donc un algo' pour résoudre ton problème en O(1) (avec une grosse constante devant xD). Mais si demain j'veux faire le même pb sur un clavier de taille n*n, bah l'algo' que j'ai soumis et qui a une complexité exponentielle (O(16\^k) je crois, où k est le nombre de cases), bah j'suis pas sûr qu'il soit très adapté.