# Faster way to solve android lock valid patterns

With the password grid shown in the Android home screen, how many valid passwords are possible?

The rules for creating a pattern is as follows.

• We must use four nodes or more to make a pattern at least.
• Once a node is visited, then the node can't be visited anymore.
• You can start at any node.
• A pattern has to be connected.
• Cycle is not allowed.

I have code that worked, one way using pattern-matching, another way using string-manipulation, they are not efficient, takes about 10 seconds. The Python version takes about 1 second.

As far as I know, both of them does not support Compile. Is there a more efficient way?

(* pattern-matching version *)

list={{1,3},{3,1},{4,6},{6,4},{7,9},{9,7},{1,7},{7,1},{2,8},{8,2},{3,9},{9,3},{1,9},{9,1},
{3,7},{7,3}};

ps=Function[{a,b},{___,(a+b)/2,___,a,b,___}|Except[{___,a,b,___}]] @@@ list;

Fold[Cases, Permutations[Range[9],{4,9}], ps]//Length//AbsoluteTiming

(* Output: {8.69702, 389112} *)
(*---------------------------------------------------------------------------------------*)

(*string-manipulation version*)

AbsoluteTiming[
invalidList = {{"13","2"}, {"31","2"}, {"46","5"}, {"64","5"}, {"79","8"}, {"97", "8"},
{"17","4"}, {"71","4"}, {"28","5"}, {"82","5"}, {"39","6"}, {"93","6"}, {"19","5"},
{"91","5"}, {"37","5"}, {"73","5"}} ;

count = 0;
Do[
Catch[
Do[
If[StringContainsQ[stri, First@i] &&
StringFreeQ[StringTake[stri, StringPosition[stri, First@i][[1, 1]]], Last@i],
Throw[0]];,
{i, invalidList}]; count++]

, {stri,
StringJoin /@ Permutations[Characters@"123456789", {4, 9}]}];
count
]

(* Output: {12.8075, 389112} *)

• Just out of curiosity, because I am not using Android, what are the valid configurations? Can you state it in words? Nov 2 '19 at 8:48
• @yarchik Updated. Nov 2 '19 at 13:47
• Related on Stackoverflow: https://stackoverflow.com/a/6979963/395258 Nov 2 '19 at 13:50
• Sorry for disturbing, but I still do not understand. 1) What does it mean that "A pattern has to be connected."? 2)What is the difference between the point 2 "Once a node is visited, then the node can't be visited anymore." and the point 5 "Cycle is not allowed."? 3) If in your example 1, you make a stop at 2, would it be a valid pattern or not? Nov 2 '19 at 14:12
• To the best of my knowledge, rules here require a question should be self-explanatory. That is, understandable without external links. They may not be available later. Nov 2 '19 at 14:41

It is possible to speed up your existing code even without compilation. The idea is to count not all configurations, but rather the topologically different ones.

There are 3 topologically distinct possibilities to start a path

1. Corner: 1, 3, 7, 9
2. Edge: 2, 4, 6, 8
3. Center: 5

Thus, it is sufficient to count the number of paths starting from 1 (n[1]), starting from 2 (n[2]) and starting from 5 (n[5]). The total number of configurations is given by the sum weighted with symmetry factors.

I keep your definitions of list and ps and perform timing of each part of the algorithm.

(x=Permutations[Range[9],{4,9}];)//AbsoluteTiming
Out[3]= {0.145363,Null}

(y[1]=Cases[x,{1,___}];
y[2]=Cases[x,{2,___}];
y[5]=Cases[x,{5,___}];)//AbsoluteTiming
Out[4]= {0.3311,Null}

Fold[Cases,x,ps]//Length//AbsoluteTiming
Out[5]= {13.6685,389112}

(n[1]=Fold[Cases,y[1],ps]//Length)//AbsoluteTiming
(n[2]=Fold[Cases,y[2],ps]//Length)//AbsoluteTiming
(n[5]=Fold[Cases,y[5],ps]//Length)//AbsoluteTiming

Out[6]= {1.40567,38042}
Out[7]= {1.60751,43176}
Out[8]= {1.71645,64240}

4n[1]+4n[2]+n[5]
Out[9]= 389112


## Discussion

The results of the timing with respect to the original algorithm are as follows:

1. Generation of all configurations 1%.
2. Selection of the corner, edge and center classes 2%.
3. Brute-force selection of the valid configurations 99%.
4. Selection of valid paths starting at the corner 10%, the edge 12%, and the center 12%.

Even with this simplest idea the achieved time saving is 65%. This approach can be systematically extended further depending on the time one wants to invest in the topological analysis.

## Challenge

This problem can be easily generalized to any $$n\times n$$ grid. However, only for $$3\times 3$$ and $$4\times 4$$ the solution is known. Can someone compute the $$5\times 5$$ number ?

In the same manner as yarchik's answer, but leveraging more symmetries.

Also using ps as defined in the question.

t = {2, 6};
u = {3, 6, 9};

{{1, t}, {1, 5, {2, 3, 6}}, {1, 5, 9, t},
{2, u}, {2, 5, u}, {2, 5, 8, u},
{5, 1, t}, {5, 1, 9, t}, {5, 2, u}, {5, 2, 8, u}} // Catenate;

finish[s : {__Integer}] :=
Join[s, #] & /@ Permutations[Complement[Range@9, s], {4 - Length@s, 9}];

filter[s : {__Integer}] := Fold[Cases, finish@s, ps]

8 Total[Length@*filter /@ eightfoldStarts] // AbsoluteTiming


{1.15843, 389112}

There is a more concise and slightly faster pattern matching solution:

impossible = {{1, 3}, {3, 1}, {4, 6}, {6, 4}, {7, 9}, {9, 7}, {1,
7}, {7, 1}, {2, 8}, {8, 2}, {3, 9}, {9, 3}, {1, 9}, {9, 1}, {3,
7}, {7, 3}};
possible = Permutations[Range[9], {4, 9}];

Count[possible, {___, PatternSequence @@@ Alternatives @@ impossible, ___}];


This takes around 7.22 seconds on my machine, against 11.24 seconds for your pattern matching solution. (By the way, you should use RepeatedTiming, not AbsoluteTiming, for more accurate timing results!)

Edit 1: Ah, OrdlessPatternSequence is a thing.

Count[possible,
{___, OrderlessPatternSequence @@@
Alternatives @@ {{1, 3}, {4, 6}, {7, 9}, {1, 7}, {2, 8}, {3,
9}, {1, 9}, {3, 7}}, ___}
]


Takes 5.24 seconds on my machine.

• Thanks for help, but your answer given 845944, not 389112. Oct 31 '19 at 1:43
• Aha, strange. Either way it would be counting the occurrences of invalid lock patterns, rather than valid ones... Oct 31 '19 at 10:22
• I agree that this is the solution to the problem as it is currently stated. I solved it using a graph approach, which is super fast, but it also says that there are 139880 valid patterns rather than 389112. I wrote a comment to the question about where the number 389112 comes from. Nov 2 '19 at 14:30