🖶

Computing the number of Android patterns

Android phones allow you to unlock your device by drawing a pattern on a 3×3 grid. Here, we write a Python program to count the number of such patterns that can be created.

TL;DR: there are 285.792 of them!

We represent a pattern by a sequence of digits, where each digit corresponds to a dot on the 3×3 grid. The correspondance is simply given by the position of the dot on the keyboard's numpad. Try the following applet to draw your pattern:

This may not work properly on smaller screens (with a width smaller than 490px). If so, try on another device instead.

Here, the button × clears the canvas, the button ← acts like the backspace key (it removes the last character), and the button ⤨ generates a random pattern.

Here is a list of fun/beautiful/interesting patterns:

"1546982"

"4253917"

"529678134"

"352841796"

"852913764"

"26487913"

Step 1: handling the patterns

As said before, a pattern can be encoded by a string of digits from 1 to 9. However, not all such strings are valid patterns. One must check some conditions:

Only digits from 1 to 9 are allowed.

No dot can be used twice. That is, no digit can appear twice in the string.

The pattern must connect at least two dots, and up to nine dots. That is, the string is 2-9 characters long.

This can be achieved by some regular expressions voodoo. The regex ^(?!.*(.).*\1)[1-9]{2,9}$ does exactly that. Here is its cartoon picture:

We call that previous regex the validation check.

However, doing so will not get rid of all impossibilities. For instance, when drawing the pattern whose code is "13", one notices that the dot number 2 is also used in the process, and therefore cannot be reused afterwards. This means that one must resolve what I call the skips. There are 8 of them:

Three horizontal skips, where "13", "46" and "79" respectively prevent 2, 5 and 8 from being used again.

Three vertical ones, where "17", "28" and "39" respectively prevent 4, 5 and 6 from being used again.

Two diagonal ones, where "19" and "37" respectively both prevent 5 from being used again.

This can again be solved by more regular expressions, the bruteforce being of best help with the regex ^(.*(13|31).*2.*)|(.*(46|64).*5.*)|(.*(79|97).*8.*)|(.*(17|71).*4.*)|(.*(28|82).*5.*)|(.*(39|93).*6.*)|(.*(19|91).*5.*)|(.*(37|73).*5.*)$. This one is called the verification check.

Now, claiming that a string encodes a valid pattern is just a matter of using those two regular expressions:

import re

validation = r"^(?!.*(.).*\1)[1-9]{2,9}$"
verification = r"^(.*(13|31).*2.*)|(.*(46|64).*5.*)|(.*(79|97).*8.*)|(.*(17|71).*4.*)|(.*(28|82).*5.*)|(.*(39|93).*6.*)|(.*(19|91).*5.*)|(.*(37|73).*5.*)$"

def isValid(code):
    return bool(re.match(validation, code)) and not(bool(re.match(verification, code)))

Comparing two patterns: generating the shape

Several distinct pattern codes can yield the same shape. For instance, "31579" and "97513" give the same shape, and so do "13", "123" and "213". There is a way to compare the shapes induced by a code, by first computing that shape. Note that the shape corresponds to a graph on nine vertices, which can be fully encoded by the data of its edges.

Mathematically, a (directed) graph is a pair $(V,E)$ of two sets $V$ and $E\subset V\times V$ (we exclude edges from a vertex to itself). We will do exactly the same in Python, with $V=\{1,\dots,9\}$ here. However, we don't care about an orientation on the edges, so instead of storing a set of tuples, we will store a set of sets. For instance, the shape of the pattern whose code is "97513" is:

{ {"1", "2"}, {"2", "3"}, {"1", "5"}, {"5", "7"}, {"7", "8"}, {"8", "9"} }

Note that sets are a mutable class, which cannot be put inside other sets. This means that one must pass them as frozenset(...) instead.

We must split in two the skips form the verification check. This can be done naively:

def split_skips(E):
    if not(E in [{1,3}, {4,6}, {7,9}, {1,7}, {2,8}, {3,9}, {1,9}, {3,7}]):
        return [frozenset(E)]
    else:
        if E=={1,3}: return [frozenset({1,2}), frozenset({2,3})]
        if E=={4,6}: return [frozenset({4,5}), frozenset({5,6})]
        if E=={7,9}: return [frozenset({7,8}), frozenset({8,9})]
        if E=={1,7}: return [frozenset({1,4}), frozenset({4,7})]
        if E=={2,8}: return [frozenset({2,5}), frozenset({5,8})]
        if E=={3,9}: return [frozenset({3,6}), frozenset({6,9})]
        if E=={1,9}: return [frozenset({1,5}), frozenset({5,9})]
        if E=={3,7}: return [frozenset({3,5}), frozenset({5,7})]

Now, generating the shape is easy:

def shape(code):
    result = set()
    for i in range(len(code)-1):
        p = int(code[i])
        q = int(code[i+1])
        for E in resolve_skips({p,q}):
            result.add(E)
    return frozenset(result)

For instance:

shape("651923")
>>> frozenset({frozenset({5, 6}), frozenset({1, 5}), frozenset({2, 3}), frozenset({9, 2}), frozenset({9, 5})})

Now, comparing the shapes is just a matter of comparing those two results:

shape("123") == shape("31")
>>> True

shape("19") == shape("169")
>>> False

Gotta count'em all!

Here is the full code for the implementation:

full-code.py

The idea is very simple: check all possible patterns, and add new shapes to the storage. We will discuss the optimizations a little.

First, instead of storing everything in a list and checking if the element isn't already in it before adding it is longer than dealing with a set and always adding an element without doing this check. Indeed, no duplicates are allowed in a set. However, because it uses hash tables, this is far more efficient than working with mere lists.

Looping through all patterns is easy:

allShapes = set()

for c in range(10**9):
    code = str(c)
    if bool(re.match(validation, code)) and not(bool(re.match(verification, code))):
        # compute the shape
        allShapes.add(shape)
        del shape
    del code

Computing the shape boils down to resolving the skips, and this can be done via lookup tables:

skips = {
        frozenset({"1","3"}),
        frozenset({"4","6"}),
        frozenset({"9","7"}),
        frozenset({"1","7"}),
        frozenset({"8","2"}),
        frozenset({"9","3"}),
        frozenset({"1","9"}),
        frozenset({"3","7"})
    }
lookupOne = {
        frozenset({"1","3"}): frozenset({"1","2"}),
        frozenset({"4","6"}): frozenset({"4","5"}),
        frozenset({"7","9"}): frozenset({"7","8"}),
        frozenset({"1","7"}): frozenset({"1","4"}),
        frozenset({"2","8"}): frozenset({"2","5"}),
        frozenset({"3","9"}): frozenset({"3","6"}),
        frozenset({"1","9"}): frozenset({"1","5"}),
        frozenset({"3","7"}): frozenset({"3","5"})
    }
lookupTwo = {
        frozenset({"1","3"}): frozenset({"2","3"}),
        frozenset({"4","6"}): frozenset({"5","6"}),
        frozenset({"7","9"}): frozenset({"8","9"}),
        frozenset({"1","7"}): frozenset({"4","7"}),
        frozenset({"2","8"}): frozenset({"5","8"}),
        frozenset({"3","9"}): frozenset({"6","9"}),
        frozenset({"1","9"}): frozenset({"5","9"}),
        frozenset({"3","7"}): frozenset({"5","7"})
    }

Having two lookup tables returning an element each, instead of one that returns a list, allows for not having to loop through that list. Again, storing all the 8 possible skips in a set rather than a list allows for slightly faster checks for when it comes to the in statement. This provides:

shape = set()
for i in range(len(code)-1):
    E = frozenset({code[i], code[i+1]})
    if (E in skips):
        shape.add(lookupOne[E])
        shape.add(lookupTwo[E])
    else:
        shape.add(E)
allShapes.add(frozenset(shape))

Running the whole code takes rougly half an hour on a not-so-decent computer, for a grand total of 285.792 unique shapes! This is its prime factorization: $$285\,792=2^5\times 3\times 13\times 229.$$

There is nothing combinatorially interesting here, especially because of those last two higher prime factors. If someone manages to count the total number of patterns in a combinatorial way, please, do let me know!