8
$\begingroup$

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

enter image description here
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} *)
$\endgroup$
  • $\begingroup$ Just out of curiosity, because I am not using Android, what are the valid configurations? Can you state it in words? $\endgroup$ – yarchik Nov 2 at 8:48
  • $\begingroup$ @yarchik Updated. $\endgroup$ – mathe Nov 2 at 13:47
  • 1
    $\begingroup$ Related on Stackoverflow: https://stackoverflow.com/a/6979963/395258 $\endgroup$ – C. E. Nov 2 at 13:50
  • $\begingroup$ 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? $\endgroup$ – yarchik Nov 2 at 14:12
  • 2
    $\begingroup$ 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. $\endgroup$ – yarchik Nov 2 at 14:41
6
+100
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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}

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for help, but your answer given 845944, not 389112. $\endgroup$ – mathe Oct 31 at 1:43
  • $\begingroup$ Aha, strange. Either way it would be counting the occurrences of invalid lock patterns, rather than valid ones... $\endgroup$ – Carl Lange Oct 31 at 10:22
  • 1
    $\begingroup$ 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. $\endgroup$ – C. E. Nov 2 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.