Faster way to solve android lock valid patterns

Question

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.

Read more, How Many Different Unlock Patterns Could You Create?

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} *)

Answer 1

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 ?

Answer 2

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};

eightfoldStarts = Thread /@
    {{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}

Answer 3

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.