Sunday, August 2, 2009

Counting Unlock Patterns

In this blog post I will enumerate the number of unlock patterns of the andriod operating system.


Imagine a square array of points, arranged in a three by three formation. We set our selfs the task of tracing a path through a number of these points subjected to the following rules.

  1. No point can be visited twice.
  2. If a point obstructs an other point, the obstructing point should be visited first.

I will illustrate rule two with an example. Let's say we start our path in the lower left point of our arrangement. Our goal is the upper right point. If we would trace a pattern from our starting point to the target point we visit the center point, which should be included in our path.
Here is an other example which also illustrates rule one. Now our path starts in the center point and again our goal is the upper right point. Instead of directly going to our target we make a little detour via the lower left point. Because we started in the center point, it does not obstruct our goal any more and we can go directly to our goal, the upper right point.

This lengthy explanation is in fact a description of the android unlock pattern. Being a proud owner of a android phone I pondered about the question: "How many unlock patterns are possible". So I set out and wrote a little script to enumerate the different unlock patterns.

The following tables summarizes my findings. The first column list the path lengths. The second column list the corresponding number of unlock patterns. So there is a total of 389498 unlock patterns.



Pattern length#Patterns
01
19
256
3320
41642
57152
626016
772912
8140704
9140704

The most important section of code is displayed here below. It recursively builds a tree of patterns which can be inspected via a visitor. Check out the source if you like.

def generate(self):
for patternElement in self.possible:
nextPossible = self.possible.copy()
nextPossible.remove(patternElement)

if (self.reachable(patternElement)):
child = PatternTree(self,patternElement,nextPossible)
self.children.add(child)
child.generate()

4 comments:

  1. Hey,

    This is some very interesting stuff you have here. I like contributing to the OEIS (although I only have one sequence).

    Keep up the good work.

    ReplyDelete
  2. Thanks for your encouragements, I like to think I will keep this blog up to date.

    As for OEIS, I already submitted this sequence. But I guess it is not in the database yet. I would be nice to find it there do.

    An other idea is to generalize this sequence on different sized arrangements.

    ReplyDelete
  3. The sequence of number of unlock patterns of a certain length can now be found at: The On-Line Encyclopedia of Integer Sequences.

    It is identified by A163889.

    ReplyDelete