CareerCup

Let's first ask a question: how the path is constructed?
The user chooses one of 'n' available points, then goes to another point of 'n-1' points left, then goes to another point of 'n-2' points, and so on.

How many different paths of length 'n' are there?
Assumming 9 points on the screen.
For length 9, there are 9*8*7*6*5*4*3*2*1 paths.
For length 8, there are 9*8*7*6*5*4*3*2 paths.
For length 7, there are 9*8*7*6*5*4*3 paths.
For length 6, there are 9*8*7*6*5*4 paths.
For length 5, there are 9*8*7*6*5 paths.
For length 4, there are 9*8*7*6 paths.

Python code of the solution:

def paths_of_length(number_of_staring_points, length_of_path):
    """
    Returns number of different paths of length length_of_path when there are 
    number_of_staring_points available
    
    >>> paths_of_length(9,1)
    9
    >>> paths_of_length(9,2)
    72
    >>> paths_of_length(1,1)
    1
    """
    different_paths = 1
    for choosing_from in range(number_of_staring_points, 
                               number_of_staring_points - length_of_path,
                               -1):
        different_paths = different_paths * choosing_from
    
    return different_paths

def android_paths():
    """
    Returns number of different android lockscreen paths
    """
    different_paths = 0
    minimum_length = 4
    maximum_length = 9
    number_of_staring_points = 9
    for length in range(minimum_length,maximum_length + 1):
        different_paths += paths_of_length(number_of_staring_points,length)
    
    return different_paths

if __name__ == '__main__':
    import doctest
    doctest.testmod()
    
    print(android_paths())

Hello,
A little diversion from my suggestions above. The rules for Android locked patterns are :
Each pattern must connect at least four dots.
The dots in the pattern must all be distinct.
If the line segment connecting any two consecutive dots in the pattern, middle dot (between them) should be already in pattern.
Also it is allowed to have "knight" moves - for example two points on 0,0 and 2,1.
So what should be done : 1 Generate all variations of 4...9 of 9 points and cut all solutions that are not valid. We coudn't come to there following pattern rules.
Here below is Java code. Hope will help.

public class AndroidLockPattern {
		
		private boolean used[] = new boolean[9];
		
		private boolean isValid(int index, int last) {		
			if (used[index])
				return false;
			if(last == -1)
				return true;				
			// knight moves 
			if((index + last)%2 == 1)
				return true;
			// indexes are from both side of the diagonals for example 0,0, and 8,8
			int mid = (index +last)/2;
			if ( mid == 4)
				return used[4];
			// adajcent cells on diagonal  - for example 0,0 and 0,1
			if ((index%3 != last%3) && (index/3 != last/3)) {
				return true;
			}
			// all other adjacent cells (two cells in one row or two cells in one column)
			return used[mid];	
			
		}
		
		public void numberOfPatterns() {
			int res =0;
			for (int len = 4; len <= 9; len++) {				
				res += calcPatterns(-1,len);	
				for (int i = 0; i < 9; i++) {
					used[i] = false;					
				}
			}
			System.out.println(res);
		}
		
		
		private int calcPatterns(int last,int len) {
			if (len == 0) {				
				return 1;				
			} 
			else {
				int sum = 0;
				for (int i = 0; i < 9; i++) {									
					if (isValid(i, last)) 
					{
							used[i] = true;															
							sum += calcPatterns(i, len - 1);
							used[i] = false;					
					}
				}
				return sum;
			}			
		}
	}

Could be the problem represented as a graph problem where we need to find number of all simple paths with length >=4 and <=9?

Assuming we have 10 keys and paths have to be 4 <= length <=9 with no repeats, we can sum up the permutations of 10 permute r between [4,9], which is defined as (10!)/(10-r)!

import math
def getLockScreenCombos():
	sum = 0
	for i in range(4,10):
		sum += math.factorial(10) / math.factorial(10-i)
	return sum

create recursive procedure which traverses through 2D matrix, while counting all the valid paths (valid means that there are no intersections inside one path and a path is of at least needed length).
Call this procedure in loop for every element of given 2D matrix.

I read that lock pattern is at least 4 keys up to 9 where no key repeats (no cycles). But I am not sure if this is specified by Android.

Use permutations! n permute r = (n!)/(n-r)!

Assuming path length is between 4 and 9 include, with no repeats:

import math
def getLockScreenCombos():
	sum = 0
	for i in range(4,10):
		sum += math.factorial(10) / math.factorial(10-i)
	return sum

Assume that 1st point as 1 and corresponding points as 2 3 .... Horizontally then for a 4 point key if you use 1st 3rd 7th and 9th key it is not possible as there are other keys in between and if you form others using permutations there would be many exceptions like this(which has a key in between them if you want to take those two keys as 1st and 2nd key in your pattern)

Assume that 1st point as 1 and corresponding points as 2 3 .... Horizontally then for a 4 point key if you use 1st 3rd 7th and 9th key it is not possible as there are other keys in between and if you form others using permutations there would be many exceptions like this(which has a key in between them if you want to take those two keys as 1st and 2nd key in your pattern)

Assume that 1st point as 1 and corresponding points as 2 3 .... Horizontally then for a 4 point key if you use 1st 3rd 7th and 9th key it is not possible as there are other keys in between and if you form others using permutations there would be many exceptions like this(which has a key in between them if you want to take those two keys as 1st and 2nd key in your pattern)

Assume that 1st point as 1 and corresponding points as 2 3 .... Horizontally then for a 4 point key if you use 1st 3rd 7th and 9th key it is not possible as there are other keys in between and if you form others using permutations there would be many exceptions like this(which has a key in between them if you want to take those two keys as 1st and 2nd key in your pattern)

This can be represented as a graph problem. May be we can run DFS or BFS on the graphs 123
456
789
and find all the paths of length ;n', where n is the length of path which can be obtained as input from the user.

one possible solution can be the following:

1. create an adjacency matrix with all the points handling the edge cases like 1 won't connect to 3.

2. then matrix^3 will tell number of paths a to b of length 4 and so on...
count all the paths and you have the answer.

public class Solution1 {
    public static void main(String[] args) {
        int total = 0;
        for (int i = 4; i <= 9; i++) {
            total = total + countPatterns(i);
        }
        System.out.println(total);
    }

    private static int countPatterns(int i) {
        return (int) Math.pow(9, i);
    }
}

public class Solution1 {
    public static void main(String[] args) {
        int total = 0;
        for (int i = 4; i <= 9; i++) {
            total = total + countPatterns(i);
        }
        System.out.println(total);
    }

    private static int countPatterns(int i) {
        return (int) Math.pow(9, i);
    }
}

I'm not quite sure what exactly the rules are, but I'm interpreting it as as a path min=4 and max=9 length, you can do 'knight moves' (aka L) and all adjacent, but never touching back on something you already did. If so then this algorithm isn't quite right as is, but you could keep a similar recursive solution.

def nextPossibleMoves(spot):
  # grid is
  # 1 2 3
  # 4 5 6
  # 7 8 9
  allMoves = {
    1: [1, 2, 4, 5, 6, 8],
    2: [1, 2, 3, 4, 5, 6, 7, 9],
    3: [2, 3, 4, 5, 6, 8],
    4: [1, 2, 3, 4, 5, 7, 8, 9],
    5: [1, 2, 3, 4, 5, 6, 7, 8, 9],
    6: [1, 2, 3, 5, 6, 7, 8, 9],
    7: [2, 4, 5, 6, 7, 8],
    8: [1, 3, 4, 5, 6, 7, 8, 9],
    9: [2, 4, 5, 6, 8, 9] }
  return set(allMoves[spot])

pathMin = 4
pathMax = 9
def countPaths(fromSpot, pathLength=1, visited=set()):
  if pathLength == pathMax:
    return 1 # we're at the end, count ourselves

  # get plausible
  nextSpots = nextPossibleMoves(fromSpot)
  # remove visited
  nextSpots.difference_update(visited)
  # check if no possible left
  if len(nextSpots) == 0:
    if pathLength < pathMin:
      # backtrack
      return -1
    else:
      # count ourselves
      return 1
  # get recursively path length possibilities from here out
  nextLengths = [countPaths(spot, pathLength + 1, visited | set([fromSpot])) 
                 for spot in nextSpots]
  # remove backtracks
  nextLengths = filter(lambda x: x != -1, nextLengths)
  if len(nextLengths) == 0 and pathLength < pathMin:
    # we have no possible moves, and we don't qualify either
    # turns out not needed for this particular problem but
    # i wouldn't have guessed that
    return -1 # backtrack
  # add ourselves as valid plus the sum of the options
  return 1 + sum(nextLengths)

def calcTotalPossibilities():
  fromEachSpot = [countPaths(spot) for spot in range(1, 10)]
  return sum(fromEachSpot)

In this Graph problem we have to find the Combinations of all possible numbers which will create a pattern.
n=9, minlength = 4
So the total Combinations are
9C4 + 9C5 +9C6 +9C7 + 9C8 + 9C9

Using backtracking.

public class CountPatternsInAndroidLockScreen {

	private static int count = 0;

	private static int[][] graph = new int[][] { { 0, 1, 0, 1, 1, 1, 0, 1, 0 }, { 1, 0, 1, 1, 1, 1, 1, 0, 1 },
			{ 0, 1, 0, 1, 1, 1, 0, 1, 0 }, { 1, 1, 1, 0, 1, 0, 1, 1, 1 }, { 1, 1, 1, 1, 0, 1, 1, 1, 1 },
			{ 1, 1, 1, 0, 1, 0, 1, 1, 1 }, { 0, 1, 0, 1, 1, 1, 0, 1, 0 }, { 1, 0, 1, 1, 1, 1, 1, 0, 1 },
			{ 0, 1, 0, 1, 1, 1, 0, 1, 0 } };

	/*
	 * Must take care of the corner cases. 1->9 is not a valid case because 5
	 * lies in the way, however 1->5->9 is.
	 */
	public static void count(int level, int index, boolean[] visited, int minLevel) {
		if (allVisited(visited))
			return;
		if (level >= minLevel)
			count++;
		for (int i = 0; i < 9; i++) {
			if (!visited[i] && graph[index][i] == 1) {
				visited[i] = true;
				count(level + 1, i, visited, minLevel);
				visited[i] = false;
			}
		}
	}

	private static boolean allVisited(boolean[] visited) {
		for (boolean b : visited)
			if (!b)
				return false;
		return true;
	}

	public static void main(String[] args) {
		for (int i = 0; i < 9; i++) {
			count(0, i, new boolean[9], 3);
		}
		System.out.println(count);
	}

}

389112

Consider the Android grid as a matrix -
0 1 2
3 4 5
6 7 8

any valid move is one which has length greater than 4 and does not have any illegal jumps (like going from 1 to 3 without visiting 2).
The solution basically checks all possible patterns for illegal jumps and eliminates the illegal patters.

Java Code for Solution -

package PracticeStuff;

import java.util.HashMap;

public class AndroidLockScreen {
	static boolean [] visited={false,false,false,false,false,false,false,false,false};
	static HashMap<String, String> illegal=new HashMap<String,String>();
	static int count;
	
	public static void main(String [] args){
		illegal.put("02", "1");
		illegal.put("06", "3");
		illegal.put("08", "4");
		illegal.put("17", "4");
		illegal.put("26", "4");
		illegal.put("28", "5");
		illegal.put("35", "4");
		illegal.put("68", "7");
		illegal.put("20", "1");
		illegal.put("60", "3");
		illegal.put("80", "4");
		illegal.put("71", "4");
		illegal.put("62", "4");
		illegal.put("82", "5");
		illegal.put("53", "4");
		illegal.put("86", "7");
		
	for(int i=0;i<9;i++)
		getMoves(i);
		System.out.println(count);
	}
	static void getMoves(int i){
		
			int length=0;
			visited[i]=true;
			for(int j=0;j<9;j++){
				if ((visited[j]!=true)&&(validmove(i,j))){
					getMoves(j);
				}
			}
			for(int k =0;k<9;k++){
				if (visited[k]==true)
					length++;
			}
			if (length>=4)
				count++;
			visited[i]=false;
	}
	static boolean validmove(int i, int j){
		String y = i + "" +j;
		//System.out.println(y);
		String x =illegal.get(y);
		if (x==null)
			return true;
		return visited[Integer.parseInt(x)];

	}
}

Brute-force Python solution:

from copy import deepcopy

def count_possibilities():
    cnt = 0
    keys = [[ False, False, False ],
            [ False, False, False ],
            [ False, False, False ]]
    for num_of_patterns in range(4,10):
        for i in range(3):
            for j in range(3):
                keys_cp = deepcopy(keys)
                keys_cp[i][j] = True
                cnt += _count_possibilities(keys_cp, 0, i, j, num_of_patterns)
    return cnt

def _count_possibilities(keys, cnt, i, j, num_of_patterns):
    if check_complete(keys, num_of_patterns):
        return 1
    for x in range(3):
        for y in range(3):
            if is_valid(keys, i, j, x, y) and not keys[x][y]:
                keys_cp = deepcopy(keys)
                keys_cp[x][y] = True
                cnt += _count_possibilities(keys_cp, 0, x, y, num_of_patterns)
    return cnt

def is_valid(keys, i, j, x, y):
    if (i == x+1 or i == x-1) and (j == y+1 or j == y-1 or j == y):
        return True
    if (i == x+1 or i == x-1 or i == x) and (j == y+1 or j == y-1):
        return True
    if (i == x+2 or i == x-2) and (j == y+1 or j == y-1):
        return True
    if (i == x+1 or i == x-1) and (j == y+2 or j == y-2):
        return True
    if is_middle_valid(keys, i, j, x, y):
        return True
    return False

def is_middle_valid(keys, i, j, x, y):
    if abs(i-x) == 2 and abs(j-y) == 2:
        return keys[1][1]
    elif abs(i-x) == 2 and j == y:
        return keys[1][j]
    elif abs(j-y) == 2 and i == x:
        return keys[i][1]
    else:
        return False

def check_complete(keys, num_of_patterns):
    cnt = 0
    for i in range(3):
        for j in range(3):
            if keys[i][j]:
                cnt += 1
    return cnt == num_of_patterns

if __name__ == "__main__":
    print(count_possibilities()) # => 389112

You can look at this as a recurrence problem you can solve with a primitive form of dynamic programming
There are 3 types of positions
The center: you can get to it from an of the other positions
Let center(n) be the number of ways to end up in the center point after n moves
An edge: you cannot get to the edge on the other side
Let edge(n) be the number of ways to end up on one particular edge after n moves
A corner: you can get to it from any edge and the center but not the other edges.
Let corner(n) be the number of ways to end up on one particular corner after n moves
The total number of patterns consists of how many ways it could take to end up on a particular location.
This will be
patterns(n) = center(n) + 4 * edge(n) + 4 * corner(n);
To get to the center after n moves we can come from some other location by n-1 moves so we get
center(n) = 4 * edge(n-1) + 4 * corner(n-1);
likewise we can compute the number of ways to get to the other points.
corner(n) = 4 * edge(n-1) + center(n-1)
edge(n) = 2 * edge(n-1) + center(n-1) + 4 * corner(n-1)
there is only one way to get to a key when you start so :
center(0) = 1, corner(0) = 1, edge(0) =1
all you now need is a loop that computes new values of 3 values but each time through you need to compute from the previous values:

center_old = 1; corner_old = 1; edge_old = 1;
for(I = 0:n)

center_new = 4 * edge_old + 4 * corner_old;
corner_new = 4 * edge_old + center_old;
edge_new = 2 * edge_old + center_old + 4 * corner_old;

corner_old = corner_new;
center_old = center_new;
edge_old = edge_new;

end loop

return center_old + 4 * edge_old + 4 * corner_old;

if you are clever you might be able to reduce it to a single recurrence and then possibly get a direct solution but that is beyond my current ability.
Note my code is pretty slack about n so there might be a +/- error in it

I ran it on a spread sheet and got this:

corner edge center total
1 1 1 9
5 7 8 56
36 42 48 360
216 276 312 2280
1416 1728 1968 14544
8880 11088 12576 92448
56928 70272 79872 588672
360960 448128 508800 3745152
2301312 2848896 3236352 23837184
14631936 18139392 20600832 151686144
93158400 115407360 131085312 965348352
592714752 734533632 834263040 6143256576

You can look at this as a recurrence problem you can solve with a primitive form of dynamic programming
There are 3 types of positions
The center: you can get to it from an of the other positions
Let center(n) be the number of ways to end up in the center point after n moves
An edge: you cannot get to the edge on the other side
Let edge(n) be the number of ways to end up on one particular edge after n moves
A corner: you can get to it from any edge and the center but not the other edges.
Let corner(n) be the number of ways to end up on one particular corner after n moves
The total number of patterns consists of how many ways it could take to end up on a particular location.
This will be
patterns(n) = center(n) + 4 * edge(n) + 4 * corner(n);
To get to the center after n moves we can come from some other location by n-1 moves so we get
center(n) = 4 * edge(n-1) + 4 * corner(n-1);
likewise we can compute the number of ways to get to the other points.
corner(n) = 4 * edge(n-1) + center(n-1)
edge(n) = 2 * edge(n-1) + center(n-1) + 4 * corner(n-1)
there is only one way to get to a key when you start so :
center(0) = 1, corner(0) = 1, edge(0) =1
all you now need is a loop that computes new values of 3 values but each time through you need to compute from the previous values:

center_old = 1; corner_old = 1; edge_old = 1;
for(I = 0:n)

center_new = 4 * edge_old + 4 * corner_old;
corner_new = 4 * edge_old + center_old;
edge_new = 2 * edge_old + center_old + 4 * corner_old;

corner_old = corner_new;
center_old = center_new;
edge_old = edge_new;

end loop

return center_old + 4 * edge_old + 4 * corner_old;

if you are clever you might be able to reduce it to a single recurrence and then possibly get a direct solution but that is beyond my current ability.
Note my code is pretty slack about n so there might be a +/- error in it

I ran it on a spread sheet and got this:


corner edge center total
1 1 1 9
5 7 8 56
36 42 48 360
216 276 312 2280
1416 1728 1968 14544
8880 11088 12576 92448
56928 70272 79872 588672
360960 448128 508800 3745152
2301312 2848896 3236352 23837184
14631936 18139392 20600832 151686144
93158400 1.15E+08 1.31E+08 965348352
5.93E+08 7.35E+08 8.34E+08 6143256576

how about this

int main(){
	long total = 9 * 8 * 7 * 6;
	long sum = total;
	for (int i = 5; i > 0; i--){
		total *=  i;
		sum += total;
	}
	printf("%ld",sum);
	return 0;
}