Google Nexus One uses a pattern based locking mechanism. The idea is to pick up a pattern from a 3 x 3 matrix of nodes. The chosen pattern is the key and the same pattern has to be formed to unlock the device. 
- An edge is a link between two nodes.
- A pattern is a *connected* set of edges.
- Pattern can start from any of the nodes.
- Any node in the matrix can be visited at east once.
- Pattern can be of any length. (Length = Number of edges in the pattern).
Find out the number of distinct patterns that can be formed from the 3 x 3 matrix of nodes. Then, generalize the problem for n x n.
-- Varun
Just looks like a fancy way to describe the numpad without 0 key with possibly some restrictions
ReplyDeleteHI Varun,
ReplyDeleteWere you a part of the fantastic IndiBloggers meet in Hyderabad on 11th april 2010
It was a great meet and an opportunity to meet fellow bloggers in blood.
Just to keep the momentum, I have created a new Group on Linkedin - Indibloggers.
I invite all of you to join this Group.
In the long run, this will aid not only in personal development but also professional development.
http://www.linkedin.com/groups?viewMembers=&gid=2945994&sik=1270992008306
> Pattern can be of any length.
ReplyDeleteActually, it requires that the pattern connect at least four dots anna, which means there should be at least three edges. Did you leave that out just for simplicity?
Also, I guess
> can be visited at east once
should be
>can be visited at most once
I left out that condition for this problem.
ReplyDelete