Phones currently give the option of using a 9 dot pattern to unlock the phone. Although this is not perfect, it is better than nothing. However, I was thinking the other day, most people use the same password, I wonder how many use the same pattern. Furthermore, how many possible patterns are there given a number of dots? I will be addressing the later question in this post and will collect input from readers to determine the former.
The pattern I will be using is the common 3 rows of 3 dots. I will number the dots from left to right. The top will be 1, 2, 3. The middle row 4, 5, 6 and bottom 7, 8, 9. I will also be calling a single continuous swipe amongst many numbers a route. So swiping from 1 to 5 to 7 would be a route.
I started to look at the number of possibilities for a pattern. The way the algorithm works, you can route between 2 and 9 non repeating dots. So I could route from 1 to 2 and that would be valid. I could also route 1 to 5 to 9. For you non-mathheads out there, this is known as a Factorial problem (which is delimited with an !, so 9! means 9 factorial). So for the number of choices with 2 dots, I have 9! but I only get 2 choices. All those possible 2 digit combinations are in the picture below.
So for 2 choices we have 9! with 2 choices. 9 * 8 = 72 choices.
However, after thinking about the problem, I realized that I could NOT select 1 to 9. Why? Because 5 is in the way of 1 to 9. So this immediately removes many choices. Not only could I not route 1 to 9, I could also not route these; 9 to 1, 1 to 3, 6 to 4, etc. It has been a LONG time since my discrete match course, but I couldn’t figure out a way to remove these consecutive patterns in a formula, so I graphed it in excel and highlighted in red all of the ones that would not be possible. The impossible choices are highlighted in red.
As you can see, by removing the impossible choices, we have reduced our possible combinations by 16 total (which is also 22%) from 72 to 56.
I would also add that their is another subset of choices, those are the “inconvenient” choices. These include all routes that involve moving from a corner to an opposite side middle dot or vice versa, for instance 1 to 6. To successfully do this you have to weave your finger between the 2 and 5 dot while routing from 1 to 6. In a world where convenience is king, I thought it important to consider these as unlikely and do a different data set on them. I highlighted the inconvenient routes in yellow.
Now with highlighting the 16 inconvenient choices, we have chopped off another 22% off the original set and the number of convenient combinations is 40, which is nearly half of our original 72.
I tallied up the number of possible and inconvenient choices in the table below. To read the table, the top row is your first dot choice, and the rows below represent the total number of Next Choices. So if you start with 1, you have 8 total choices, but 3 of those are impossible and 2 are inconvenient, leaving you with 5 total choices with impossible removed and 3 total choices with impossible and inconvenient removed.
[table caption=”Table of Possible Routes” width=”600″ colwidth=”250|50|50|50|50|50|50|50|50″ colalign=”left|left|left|left|left|left|left|left|left”]
X,1,2,3,4,5,6,7,8,9
Total Choices,8,8,8,8,8,8,8,8,8
Impossible Choices, 3,1,3,1,0,1,3,1,3
Inconvenient Choices, 2,2,2,2,0,2,2,2,2
Total Choices – Impossible Removed,5,7,5,7,8,7,5,7,5
Total Choices – Impossible and Inconvenient Removed,3,5,3,5,8,5,3,5,3
[/table]
At this point, the math is beyond my ability. However, I do recognize some patterns with the graph and in the palindrome of the numbers above. Either way, I brute forced this by whipping up a couple of quick ruby recursive function that determined the number of good, impossible and inconvenient permutations. I will put the in my github account here. If you need help understanding the code please leave a comment.
What you will notice with the results is that the impossible and inconvenient routes compound exponentially, meaning that the more dots we have, the quicker we lose possible good routes. The results are below.
[table caption=”Table of Possible Routes with Impossible Exceptions” width=”600″ colwidth=”50|50|300|300|300
” colalign=”left|left|left|left|left”]
Total Choices,Total Routes, Good and Convenient, Good but Inconvenient Routes, Impossible Routes
2, 72, 40 (55.56%), 56 (77.78%), 16 (22.22%)
3, 504, 160 (31.75%), 304 (60.32%), 200 (39.68%)
4, 3024, 496 (16.40%), 1400 (46.30%), 1624 (53.70%)
5, 15120, 1208 (7.99%), 5328 (35.24%), 9792 (64.76%)
6, 60480, 2240 (3.70%), 16032 (26.51%), 44348 (73.33%)
7, 181440, 2984 (1.64%), 35328 (19.5%), 146112 (80.53%)
8, 362880, 2384 (.66%), 49536 (13.65%), 313344 (86.35%)
9, 362880, 784 (.22%), 32256 (8.89%), 330624 (90.11%)
[/table]
http://www.stef.be/dev/javascript/patternlock/
But it gets more complicated than that. You CAN go from 1 to 9 if 5 is selected. So I added exceptions to our algorithm that tests for our impossible routes and then checks the preceding string to see if the dot that would allow the formally impossible string is present. So if the route were “52197”. We would see the “19” and then check the digits before that, since their is a “5” in “52” this route is actually possible. Here are the numbers after adding the new logic.
[table caption=”Table of Possible Next Choices” width=”600″ colwidth=”50|50|300|300|300
” colalign=”left|left|left|left|left”]
Total Choices,Total Routes, Good and Convenient, Good but Inconvenient Routes, Impossible Routes
ALL, 986400, 46128 (4.68%), 389203 (39.46%), 596912 (60.51%)
2, 72,40 (55.56%),56 (77.78%), 16 (22.22%)
3, 504,176 (34.92%),320 (63.49%), 184 (36.51%)
4, 3024,648 (21.43%),1624 (53.7%), 1400 (46.30%)
5, 15120,2040 (13.49%),7152 (47.3%), 7968 (52.7%)
6, 60480,5248 (8.68%),26016 (43.02%), 34464 (56.98%)
7, 181440,10448 (5.76%),72912 (40.19%), 108528 (59.81%)
8, 362880,15168 (4.18%),140704 (38.77%), 222176 (61.23%)
9, 362880,12360 (3.41%),140704 (38.77%), 222176 (61.23%)
[/table]
Conclusion
We find that we have less than 5% of the 986,400 dot patterns are in the subset of Good and Convenient, which is over 46,128 routes. Most phones will only give you 5 tries per 30 seconds so it would take over 64 hours to get through every permutation. To get through all Good but Inconvenient Routes it would take over 540 hours, which is a little less than 22 days.
So, although this is not anywhere close to a game changer, I suspect that this problem will end up being similar to passwords. For instance, although their are 8,153,726,976 possible 5 character passwords using 96 characters, the vast majority of them will be common ones like “12345”, “god” and “monkey”.
I suspect that we will find something similar with pattern swiping. For instance, most right handed people probably start with dot 1 because that is where the thumb is when you pick it up with your right hand. Left handed people will probably have the same tendancy with dot 3. Also, their will also probably be some motions that I did not capture in the inconvenient subsets I defined above.
I also suspect that most people will have a tendency to use a set number of dots, I don’t know what that it, but 4 or 5 seems like something that is convenient and long enough to make someone feel good about setting the swipe password.
Here soon, I will put up a swipe checker and collect data from people for a few months to see what we find.
The code can be accessed here https://github.com/Austio/DotPattern