Original Puzzle: Pattern Lock - Combinatorics Puzzle - Number of Possible Passwords
Source: Discussion with Ankush Jain (CSE IITB 2011 Alumnus, Morgan Stanley Analyst) a few months back. Discussion revived by Sangram Raje (CSE IITB 2008 Alumnus, Tower Research Analyst) today.
Problem:
Ever seen a pattern lock in Galaxy S2? Password is a series of connected line strokes. How many possible password combinations can you have?
Some description about the problem:
1) Assuming the dots on the screen are like (1, 2, 3 in the first row), (4, 5, 6 in the second row) and (7, 8, 9 in the third row), you cannot go to 8 from 2, without going through 5. So, a password like * * 8 2 * * is not possible.
2) You cannot move over two lines twice You can move to a used point, but you cannot move to another used point from a used point
I do not see a simple way to solve this. But even coding this looks very difficult to me. Any takers?
Update: (19-07-2012)
This is essentially an open ended question
Coding at least is easy. Answer comes to 140240. I have assumed that a single number is not a valid password, and otherwise there is no restriction that all numbers must be used.
ReplyDeleteCoding does not seem so hard. Even a brute force approach seems to finish in a few minutes to give 149507072.
ReplyDeleteCode as follows, let me know if this looks okay:
#include
#define N 3
#define NN 9
void countPasswords (int* pickedArr, bool lastAlready, int lastPicked, int depth, int& count, int nextArr[][NN]) {
if (depth >= (NN + 1)) {
// return;
}
for (int i = 0; i < NN; i++) {
if ((lastPicked >= 0) && (nextArr[lastPicked][i] == 0)) {
continue;
}
bool lastThis = (pickedArr[i] > 0);
if (lastAlready == true && lastThis == true) {
continue;
}
++ pickedArr[i];
if (depth > 0) {
++ count;
// for (int k = 0; k < NN; k ++) {
// printf ("%d ", pickedArr[k]);
// }
// printf ("\n");
}
countPasswords (pickedArr, lastThis, i, depth + 1, count, nextArr);
-- pickedArr[i];
}
}
int main (void) {
int pickedArr[NN];
for (int i = 0; i < NN; i ++) {
pickedArr[i] = 0;
}
int lastPicked = -1;
int count = 0;
int nextArr[NN][NN];
for (int i = 0; i < NN; i++) {
int i1 = (i / N);
int i2 = (i % N);
for (int j = 0; j < NN; j ++) {
int j1 = (j / N);
int j2 = (j % N);
if (((i1 + j1) % 2 == 0) && ((i2 + j2) % 2 == 0)) {
nextArr[i][j] = 0;
} else {
nextArr[i][j] = 1;
}
// printf ("%d ", nextArr[i][j]);
}
// printf ("\n");
// printf ("\n");
}
int depth = 0;
countPasswords (pickedArr, false, lastPicked, depth, count, nextArr);
printf ("count %ld\n", count);
}
The solution is possible only on theoretical basis as per my knowledge.
ReplyDeleteBecause practically,the time lapse between two WRONG hits,increases exponentially.
I have an approach..please validate :)
ReplyDeleteFirst lets define three functions:-
T(k) = No of passwords using k vertices
F(k) = No of passwords where starting point = end point
G(k) = no of passwords where starting point is different from ending point
Argument 1:- T(k) = F(k) + G(k)
ie. All possible paths = Paths that start from a point and don't end at that point + Paths that start from a point and end at that point
Argument 2:- T(k+1) = (k+1)*(2.T(k)+k-k.F(k))
ie. If we add a vertex to our set of k vertices, the total number of paths =
Number of paths with edge > 1, that start from the new vertex but don't end in the same vertex = T(k) + paths that start and end on the same new vertex = T(k)
Plus number of paths with edge length one = k
Minus number of paths that start with some other vertex and end at the same vertex = k.(F(k))
For k+1 vertices...by symetry...All paths will be unique because we are defining unique starting vertices.
Now we need to find F(k)
Its actually easier to find G(k), so lets do that:-
Argument 3:- G(k+1)= (2.G(k)+k)(K+1)
No of paths which start with new vertex and does not end with the same vertex = (2.G(k) + k) why?...think
Solving the recurrence relation for G(k) and replacing F(k) by T(k)-G(k) in argument 2 and solving that recurrence relation should give the answer.
I am rusty with solving rec rel's...but comments are welcome...
Jatin Patni
@Pyrole, your solution assumes that it is possible to move to any vertex from any vertex, which is not the case here
ReplyDeletelike for example, we cannot move to 9 from 1 directly. So, we need to make a graph and then try to find the solution(which perhaps can be done by a little modification to DFS)