Disons que vous avez vu votre ami entrer son mot de passe dans son téléphone Android. Vous ne vous souvenez pas comment ils ont fait le motif mais vous vous souvenez à quoi ressemble le motif. Étant l'ami concerné que vous êtes, vous voulez savoir à quel point leur mot de passe est sécurisé. Votre travail consiste à calculer toutes les façons dont un motif particulier peut être créé.

Fonctionnement des modèles Android

Les motifs sont dessinés sur une grille 3x3 de nœuds. Dans un schéma, on visite une série de nœuds sans jamais lever le doigt de l'écran. Chaque nœud qu'ils visitent est connecté au nœud précédent par un bord. Il y a deux règles à garder à l'esprit.

• Vous ne pouvez visiter aucun nœud plus d'une fois

• Un bord ne peut pas traverser un nœud non visité

Notez que, bien que généralement très difficile à réaliser et donc peu courant dans les vraies combinaisons de verrouillage Android, il est possible de se déplacer comme un chevalier . Autrement dit, il est possible de passer d'un côté à un coin non adjacent ou dans l'autre sens. Voici deux exemples de modèles utilisant un tel mouvement:

Voici un Gif animé en cours d'exécution.

Résoudre un motif

Un modèle typique pourrait ressembler à ceci:

Avec un modèle simple comme celui-ci, il existe deux façons de dessiner le modèle. Vous pouvez commencer à l'une des deux extrémités libres et parcourir les nœuds en surbrillance à l'autre. Bien que cela soit vrai pour de nombreux modèles, en particulier ceux que les êtres humains utilisent généralement, ce n'est pas vrai pour tous les modèles.

Considérez le modèle suivant:

Il existe deux solutions immédiatement reconnaissables. L'un commençant en haut à gauche:

Et un commençant en bas au centre:

Cependant, comme une ligne est autorisée à passer par un point une fois qu'elle a déjà été sélectionnée, un motif supplémentaire commence au milieu supérieur:

Ce modèle particulier a 3 solutions, mais les modèles peuvent avoir entre 1 et 4 solutions ^{[citation nécessaire]} .

Voici quelques exemples de chacun:

1.

2.

3.

4.

E / S

Un nœud peut être représenté par les entiers de zéro à neuf inclus, leurs équivalents de chaîne ou les caractères de a à i (ou A à I). Chaque nœud doit avoir une représentation unique de l'un de ces ensembles.

Une solution sera représentée par un conteneur ordonné contenant des représentations de nœuds. Les nœuds doivent être classés dans le même ordre de passage.

Un motif sera représenté par un conteneur non ordonné de paires de nœuds. Chaque paire représente un bord commençant à relier les deux points de la paire. Les représentations de motifs ne sont pas uniques.

Vous prendrez une représentation de modèle en entrée via des méthodes d'entrée standard et sortirez toutes les solutions possibles qui créent le même modèle via des méthodes de sortie standard.

Vous pouvez supposer que chaque entrée aura au moins une solution et connectera au moins 4 nœuds.

Vous pouvez choisir d'utiliser un conteneur commandé à la place d'un conteneur non commandé, si vous le souhaitez ou si vous y êtes contraint par la sélection de la langue.

Cas de test

Avec les nœuds disposés dans le modèle suivant:

0 1 2
3 4 5
6 7 8

Soit {...}un conteneur non ordonné, [...]un conteneur ordonné et (...)une paire.

Les entrées et sorties suivantes doivent correspondre

{(1,4),(3,5),(5,8)} -> {[1,4,3,5,8]}
{(1,4),(3,4),(5,4),(8,5)} -> {[1,4,3,5,8]}
{(0,4),(4,5),(5,8),(7,8)} -> {[0,4,5,8,7],[7,8,5,4,0]}
{(0,2),(2,4),(4,7)} -> {[0,1,2,4,7],[1,0,2,4,7],[7,4,2,1,0]}
{(0,2),(2,6),(6,8)} -> {[0,1,2,4,6,7,8],[1,0,2,4,6,7,8],[8,7,6,4,2,1,0],[7,8,6,4,2,1,0]}
{(2,3),(3,7),(7,8)} -> {[2,3,7,8],[8,7,3,2]}
{(0,7),(1,2),(1,4),(2,7)} -> {[0,7,2,1,4],[4,1,2,7,0]}
{(0,4),(0,7),(1,3),(2,6),(2,8),(3,4),(5,7)} -> {[1,3,4,0,7,5,8,2,6]}
{(1,3),(5,8)} -> {}

Un album imgur de tous les cas de test sous forme d'images peut être trouvé ici . Les motifs sont en bleu, les solutions en rouge.

Notation

C'est le golf de code. Le moins d'octets gagne.

Python 2.7, 493 430 octets

exec("L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]IL];S=sorted;F=lambda t:''.join(str(i)It)\ndef N(x):\n s=' '.join(F(S(i))Ix)\nIL:s=s.replace(i[::2],i[:2]+' '+i[1:])\n return S(set(s.split()))\ndef P(s):\n e=0\nIL:e|=-1<s.find(i[::2])<s.find(i[1])\n return[zip(s[:-1],s[1:]),L][e]\nx=N(input());print[F(i)I__import__('itertools').permutations({iI`x`if i.isdigit()})if x==N(P(F(i)))]".replace('I',' for i in '))

La version à ligne unique enveloppe le programme exec("...".replace('I',' for i in '))afin que toutes les boucles for et les générateurs puissent être court-circuités avec un seul Iet économise 15 octets sur cette version plus lisible:

L=['012','345','678','036','147','258','048','246'];L+=[i[::-1]for i in L]
S=sorted;F=lambda t:''.join(str(i)for i in t)
def N(x):
 s=' '.join(F(S(i))for i in x)
 for i in L:s=s.replace(i[::2],i[:2]+' '+i[1:])
 return S(set(s.split()))
def P(s):
 e=0
 for i in L:e|=-1<s.find(i[::2])<s.find(i[1])
 return[zip(s[:-1],s[1:]),L][e]
x=N(input())
print[F(i)for i in __import__('itertools').permutations({i for i in`x`if i.isdigit()})if x==N(P(F(i)))]

Le programme prend l'entrée de la manière indiquée (par exemple {(1,4),(3,4),(5,4),(8,5)}) ou sous forme de liste de chaînes (par exemple ['14','34','54','85']) (ou dans d'autres formats compatibles python) et renvoie la sortie sous forme de liste de chaînes. Nous avons donc techniquement un conteneur commandé de conteneurs commandés.

La fonction Nnormalise un modèle afin que deux modèles puissent être facilement comparés. La normalisation trie les paires désignant les bords (donc '02'au lieu de '20'), utilise le remplacement de chaîne pour développer les doubles bords (par exemple, '02'devient '01 12'), divise les bords en un ensemble pour supprimer les doublons et trie le résultat.

La fonction Faplatit des tuples d'entiers / chaînes en chaînes, afin que nous puissions normaliser les chemins produits de différentes manières.

La liste Lcontient toutes les lignes à l'écran.

Nous prenons ensuite chaque permutation de tous les chiffres dans le modèle normalisé et calculons un chemin valide ou Ls'il n'est pas valide (qui ne se normalise jamais à une liste de paires comme le feraient des chemins réels), ou une liste de paires indiquant que les nœuds d'ordre sont visités s'ils sont valides. Si cela se normalise au même modèle, nous avons une solution valide et l'incluons dans la liste finale.

La vérification principale nécessaire pour valider une permutation sous forme de chaîne sest -1<s.find(i[::2])<s.find(i[1]), qui détecte une erreur avec une ligne i. Par exemple, avec la ligne, '210'le code détecte une erreur si elle '20'se produit (c'est-à-dire que son index est supérieur à -1) et '1'se produit après. Nous n'avons pas à nous inquiéter du fait que 1 ne se produise pas car le 1 apparaîtra dans le modèle normalisé lorsqu'il n'était pas dans l'entrée.

REMARQUE: je sais que le remplacement str(i)for i in t par map(str,t) et {i for i in`x`if i.isdigit()} par set('012345678')&set(`x`) raccourcirait le code d'origine, mais ce serait encore un peu plus long que le remplacement I .