Android Unlock Patterns


  • 2

    0_1461680354983_android_lock_screen.jpg

    Find the total number of patterns of the Android lock screen. The number of key used has to be at least 4, and max 9.

    Example:

    use 5 keys:
    OAB
    OOC
    OED

    OAB
    OCD
    OOE

    Same thing goes with 4, 6, 7, 8, 9 keys. Count the total possible pattern. The order of keys used matters.

    Rules:

    1. At-least 4 and at-max 9 dots must be connected.
    2. There can be no jumps
    3. Once a dot is crossed, you can jump over it.

    1_1461680354988_cpTQH.png


  • 1

    I solved this problem some months ago. Here is my code of the problem. You need to follow google rules for the unlocking pattern . Hope this will help you.

    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) {
    			for(int i = 0; i < 9; i++) {
    				if(used[i])
    				System.out.print(i);
    			}
    			System.out.println();
    			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;
    		}			
    	}
    }
    

  • 0

    By the way is your program able to count how many total unlock pattern combinations possible? I am curious to know how secure android is


  • 0

    try it, I this it was about 300 000 or more


  • 0

    @elmirap Good to know! That's a lot, good luck cracking it
    I have also uploaded the android unlocking rules. Could you please confirm this seems correct to you?


  • 0

    right, these three were the rules


  • 0
    N

    | 1 | 2 | 3 |
    | 4 | 5 | 6 |
    | 7 | 8 | 9 |

    Is 6-9-2 a valid move? How about 5-9-2? And 2-3-6-9-1?


  • 0

    @nixed said in Android Unlock Patterns:

    Is 6-9-2 a valid move? How about 5-9-2? And 2-3-6-9-1?

    Both 6-9-2 and 5-9-2 are valid, because the path 9-2 does not have a point in between. 2-3-6-9-1 is invalid, because the path 9-1 has a point 5 in between and it was not connected before. 2-3-6-5-9-1 is valid though, because when the path crosses from 9-1, 5 was already crossed before.


  • 0
    Q

    I've got an answer of 389112


  • 0

    @qiyang.lu I think that's the correct answer! Can you share with us how did you arrive at this answer?


  • 1
    Q

    My code in C#:

    private int getPossiblePatterns(string currentPatternString)
    {
        if (possiblePatterns.ContainsKey(currentPatternString))
        {
            return possiblePatterns[currentPatternString];
        }
    
        possiblePatterns.Add(currentPatternString, 0);
    
        if(currentPatternString.Length >= 4)
        {
            possiblePatterns[currentPatternString]++;
        }
        
        var nextPatternStrings = this.getNextPatternStrings(currentPatternString);
    
        foreach(var nextPatternString in nextPatternStrings)
        {
            possiblePatterns[currentPatternString] += this.getPossiblePatterns(nextPatternString);
        }
    
        return possiblePatterns[currentPatternString];
    }
    
    private List<string> getNextPatternStrings(string currentPattern)
    {
        var result = new List<string>();
        var lastChar = currentPattern.Last();
        var newPatternPrefix = new string(currentPattern.OrderBy(c => c).ToArray());
        for(char i = '1'; i <= '9'; i++)
        {
            if (currentPattern.Contains(i))
                continue;
            if (middleChar.ContainsKey(i.ToString() + lastChar)
                && !currentPattern.Contains(middleChar[i.ToString() + lastChar]))
                continue;
            result.Add(newPatternPrefix + i);
        }
        return result;
    }
    
    private void Init()
    {
        middleChar.Add("13", '2');
        middleChar.Add("31", '2');
        middleChar.Add("17", '4');
        middleChar.Add("71", '4');
        middleChar.Add("39", '6');
        middleChar.Add("93", '6');
        middleChar.Add("79", '8');
        middleChar.Add("97", '8');
        middleChar.Add("19", '5');
        middleChar.Add("91", '5');
        middleChar.Add("37", '5');
        middleChar.Add("73", '5');
        middleChar.Add("28", '5');
        middleChar.Add("82", '5');
        middleChar.Add("46", '5');
        middleChar.Add("64", '5');
    }

  • 0
    T

    @1337c0d3r , I understood the question in general. Could you explain what do you mean by this example.

    use 5 keys:
    OAB
    OOC
    OED

    OAB
    OCD
    OOE

    Thanks.


  • 0

    @therealfakebatman

    Compared

    OAB
    OOC
    OED

    to:

    | 1 | 2 | 3 |
    | 4 | 5 | 6 |
    | 7 | 8 | 9 |

    Which means the sliding pattern is 2-3-6-9-8.


    OAB
    OCD
    OOE

    the sliding pattern is 2-3-5-6-9.


  • 0
    R

    @elmirap
    I didn't get the logic used in your isValid() method. Could you please explain it?


  • 0

    @RajatVaryani is Valid checks the conditions in which we don't have valid combinations according the rules above
    There can be no jumps
    Once a dot is crossed, you can jump over it.
    I put comments in the code to show which combinations are acceptable.


  • 0

    Possible second problem: "Android Unlock PIN", where you can enter strings of digits, e.g., "938817". Let's assume someone tries a smudge attack, i.e., look at smudge on your screen to see which digits you used (but can't see how often each was used). Suggestion for the problem: Write a function numberOfPins(int totalDigits, int differentDigits) that returns how many different PINs there are of length totalDigits and using differentDigits different digits.

    Examples:
    numberOfPins(9, 9) = 362880
    numberOfPins(9, 7) = 2328480

    (These btw show that if you're going to use length 9, you might better not use all nine different digits but only use seven different ones.)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.