Figure Out the Android Lock Pattern

Question

Lets say you saw your friend enter his or her password into their Android phone. You don't remember how they made the pattern but you remember what the pattern looks like. Being the concerned friend that you are you want to know how secure their password is. Your job is to calculate all the ways that a particular pattern can be made.

How Android patterns work

Patterns are drawn on a 3x3 grid of nodes. In a pattern one visits a series of nodes without ever lifting their finger from the screen. Each node they visit is connected to the previous node by a edge. There are two rules to keep in mind.

• You may not visit any one node more than once

• An edge may not pass through an unvisited node

Note that, while typically very hard to perform and thus not very common in real android lock combinations, it is possible to move like a Knight. That is, it is possible to move from one side to a non-adjacent corner or the other way around. Here are two examples of patterns employing such a move:

Here is a an animated Gif of it being performed.

Solving a pattern

A typical pattern might look something like this:

With a simple pattern like this one it there are two ways two draw the pattern. You can start at either of the two loose ends and traveling through the highlighted nodes to the other. While this is true for many patterns particularly ones that human beings typically employ this is not true for all patterns.

Consider the following pattern:

There are two immediately recognizable solutions. One starting in the upper left:

And one starting in the bottom center:

However because a line is permitted to pass through a point once it has already been selected there is an additional pattern starting in the top middle:

This particular pattern has 3 solutions but patterns can have anywhere between 1 and 4 solutions^{[citation needed]}.

Here are some examples of each:

1.

2.

3.

4.

I/O

A node can be represented as the integers from zero to nine inclusive, their string equivalents or the characters from a to i (or A to I). Each node must have a unique representation from one of these sets.

A solution will be represented by an ordered container containing node representations. Nodes must be ordered in the same order they are passed through.

A pattern will be represented by an unordered container of pairs of nodes. Each pair represents an edge starting connecting the two points in the pair. Pattern representations are not unique.

You will take a pattern representation as input via standard input methods and output all the possible solutions that create the same pattern via standard output methods.

You can assume each input will have at least one solution and will connect at least 4 nodes.

You may choose to use a ordered container in place of an unordered one, if you so desire or are forced to by language selection.

Test Cases

With the nodes arranged in the following pattern:

0 1 2
3 4 5
6 7 8

Let {...} be an unordered container, [...] be a ordered container, and (...) be a pair.

The following inputs and outputs should match

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

An imgur album of all the test cases as pictures can be found here. Patterns are in blue solutions in red.

Scoring

This is code golf. Fewest bytes wins.

Answer 1

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

The single line version wraps the program with exec("...".replace('I',' for i in ')) so that all for-loops and generators can be shorted with a single I and saves 15 bytes over this more readable version:

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

The program takes the input in the manner shown (e.g. {(1,4),(3,4),(5,4),(8,5)}) or as a list of string (e.g. ['14','34','54','85']) (or in other python friendly formats) and returns the output as a list of strings. So we technically have an ordered container of ordered containers.

The function N normalizes a pattern so that two patterns can be easily compared. The normalization sorts the pairs denoting edges (so '02' instead of '20'), use string replacement to expand double edges (e.g. '02' becomes '01 12'), splits the edges into a set to remove duplicates, and sorts the result.

The function F flattens tuples of ints/strings to strings, so we can normalize paths produced in different ways.

The list L contains all lines on screen.

We then take each permutation of all digits in the normalized pattern and compute a valid path or L if invalid (which never normalizes to list of pairs like real paths would), or a list of pairs indicating the order nodes are visited if valid. If this normalizes to the same pattern then we have a valid solution and include it in the final list.

The main check needed to validate a permutation as a string s is -1<s.find(i[::2])<s.find(i[1]), which detects an error with a line i. For instance with the line '210' the code detects an error if '20' occurs (i.e. it's index is greater than -1) and '1' occurs after it. We don't have to worry about 1 not occurring because the 1 will show up in the normalized pattern when it wasn't in the input.

---

NOTE: I know replacing str(i)for i in t with map(str,t) and {i for i in`x`if i.isdigit()} with set('012345678')&set(`x`) would make the original code shorter, but this would still be slightly longer that substituting I.