Digamos que você tenha visto seu amigo digitar a senha dele no telefone Android. Você não se lembra como eles criaram o padrão, mas lembra como ele é. Sendo o amigo em causa que você é, você quer saber o quão segura é a senha deles. Seu trabalho é calcular todas as maneiras pelas quais um padrão específico pode ser feito.

Como os padrões do Android funcionam

Os padrões são desenhados em uma grade 3x3 de nós. Num padrão, visita-se uma série de nós sem nunca levantar o dedo da tela. Cada nó que eles visitam é conectado ao nó anterior por uma borda. Há duas regras a serem lembradas.

• Você não pode visitar nenhum nó mais de uma vez

• Uma aresta não pode passar por um nó não visitado

Observe que, embora normalmente seja muito difícil de executar e, portanto, não seja muito comum em combinações reais de bloqueio do Android, é possível se mover como um cavaleiro . Ou seja, é possível mover de um lado para um canto não adjacente ou vice-versa. Aqui estão dois exemplos de padrões que empregam essa mudança:

Aqui está um GIF animado dele sendo executado.

Resolvendo um padrão

Um padrão típico pode ser algo como isto:

Com um padrão simples como este, existem duas maneiras pelas quais desenham o padrão. Você pode começar em uma das duas pontas soltas e viajar pelos nós destacados para o outro. Embora isso seja verdade para muitos padrões, particularmente aqueles que os seres humanos normalmente empregam, isso não é verdade para todos os padrões.

Considere o seguinte padrão:

Existem duas soluções imediatamente reconhecíveis. Um começando no canto superior esquerdo:

E um começando no centro inferior:

No entanto, como é permitido que uma linha passe através de um ponto depois de já ter sido selecionada, existe um padrão adicional começando no meio superior:

Esse padrão específico tem 3 soluções, mas os padrões podem ter entre 1 e 4 soluções ^{[citação necessário]} .

Aqui estão alguns exemplos de cada um:

1

2)

3)

4)

I / O

Um nó pode ser representado como números inteiros de zero a nove, inclusive, seus equivalentes de cadeia ou os caracteres de a a i (ou A a I). Cada nó deve ter uma representação exclusiva de um desses conjuntos.

Uma solução será representada por um contêiner ordenado contendo representações de nós. Os nós devem ser ordenados na mesma ordem em que são transmitidos.

Um padrão será representado por um contêiner não ordenado de pares de nós. Cada par representa uma aresta começando a conectar os dois pontos no par. Representações de padrões não são exclusivas.

Você fará uma representação de padrão como entrada através de métodos de entrada padrão e produzirá todas as soluções possíveis que criam o mesmo padrão através de métodos de saída padrão.

Você pode assumir que cada entrada terá pelo menos uma solução e conectará pelo menos 4 nós.

Você pode optar por usar um contêiner solicitado no lugar de um contêiner não ordenado, se assim o desejar ou for forçado pela seleção de idioma.

Casos de teste

Com os nós organizados no seguinte padrão:

0 1 2
3 4 5
6 7 8

Seja {...}um contêiner não ordenado, [...]seja um contêiner solicitado e(...) seja um par.

As seguintes entradas e saídas devem corresponder

{(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)} -> {}

Um álbum imgur de todos os casos de teste, como imagens, pode ser encontrado aqui . Os padrões estão em soluções azuis em vermelho.

Pontuação

Isso é código de golfe. Menos bytes ganha.

Python 2.7, 493 430 bytes

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 '))

A versão de linha única envolve o programa, exec("...".replace('I',' for i in '))para que todos os loops e geradores possam ser reduzidos com um único Ie economizando 15 bytes nesta versão mais legível:

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)))]

O programa pega a entrada da maneira mostrada (por exemplo {(1,4),(3,4),(5,4),(8,5)}) ou como uma lista de cadeias (por exemplo ['14','34','54','85']) (ou em outros formatos compatíveis com python) e retorna a saída como uma lista de cadeias. Por isso, tecnicamente temos um contêiner encomendado de contêineres solicitados.

A função Nnormaliza um padrão para que dois padrões possam ser facilmente comparados. A normalização classifica os pares que indicam arestas (então, em '02'vez de '20'), use a substituição de cadeia para expandir arestas duplas (por exemplo, '02'torna-se'01 12' ), divide as arestas em um conjunto para remover duplicatas e classifica o resultado.

A função F nivela tuplas de ints / strings para strings, para que possamos normalizar os caminhos produzidos de maneiras diferentes.

A lista L contém todas as linhas na tela.

Em seguida, tomamos cada permutação de todos os dígitos no padrão normalizado e calculamos um caminho ou L se inválido (que nunca se normaliza para listar pares como caminhos reais o faria) ou uma lista de pares indicando que os nós de pedidos são visitados se válidos. Se isso normalizar para o mesmo padrão, teremos uma solução válida e a incluiremos na lista final.

A verificação principal necessária para validar uma permutação como uma string sé -1<s.find(i[::2])<s.find(i[1]), que detecta um erro com uma linha i. Por exemplo, com a linha, '210'o código detecta um erro se '20'ocorrer (ou seja, seu índice é maior que -1) e '1'ocorre depois dele. Não precisamos nos preocupar com o fato de 1 não ocorrer, porque o 1 aparecerá no padrão normalizado quando não estava na entrada.

NOTA: Eu sei que a substituição str(i)for i in t com map(str,t) e {i for i in`x`if i.isdigit()} com set('012345678')&set(`x`) tornaria o código original mais curta, mas este ainda seria um pouco mais longa que a substituição I .