September 17, 2008
Android's locking pattern
This page contained an embedded video. Click here to view it.
As you might already know, Android uses an innovative approach to lock your phone and prevent accidental dialing. Play the short video above to see how it works.
For the rest of this discussion, I will use the following convention to designate a locking pattern:
0 1 2
3 4 5
6 7 8
It needs to contain at least four dots (and obviously, no more than nine). Once a dot is lit, it can't be used again. You can use one or several "knight moves", such as in [0 5 4 2]:
![[image]](http://mowser.com/img?url=http%3A%2F%2Fbeust.com%2Fpics%2Fknight.png)
In this example, the knight move is between 0 and 5. You cannot go over an unlit dot without lighting it. For example, the pattern [0 2 1 4] is illegal, because moving your finger between 0 and 2 will light 1. Once a dot is lit, you can use it to reach another unlit dot. For example, both [0 4 3 5] and [0 4 5 3] are legal:
![[image]](http://mowser.com/img?url=http%3A%2F%2Fbeust.com%2Fpics%2Foverride.png)
This example is a bit ambiguous but you get the idea: I trace [0 4 5] and then I slide over 4 again to reach 3.
With these constraints in place, I wondered how many combinations were actually possible, so I wrote a short program to simulate it. It turns out there are quite a few: 389,112. Here is a breakdown:
In this example, the knight move is between 0 and 5. You cannot go over an unlit dot without lighting it. For example, the pattern [0 2 1 4] is illegal, because moving your finger between 0 and 2 will light 1. Once a dot is lit, you can use it to reach another unlit dot. For example, both [0 4 3 5] and [0 4 5 3] are legal:
This example is a bit ambiguous but you get the idea: I trace [0 4 5] and then I slide over 4 again to reach 3.
4 dots: 1624 solutions 5 dots: 7152 solutions 6 dots: 26016 solutions 7 dots: 72912 solutions 8 dots: 140704 solutions 9 dots: 140704 solutions Total: 389112If you're not convinced, here is a full list of all the four dot patterns (the page uses a big canvas object, it might take a few seconds to load).
Still, I'm not sure my calculations are right, so I'd like you, dear reader, to confirm my numbers, and optionally explain how you coded your solution...
Posted by cedric at 02:43 PM | Comments (6)
September 16, 2008
Best software blogs
![[image]](http://mowser.com/img?url=http%3A%2F%2Fbeust.com%2Fpics%2F100.jpg)
Good list overall, I'll add some of these to my RSS reader.
Posted by cedric at 12:46 PM | Comments (0)
