351 Android Unlock Patterns

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern:

1. Each pattern must connect at least m keys and at most n keys.

2. All the keys must be distinct.

3. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.

4. The order of keys used matters.

Explanation:

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

Invalid move:4 - 1 - 3 - 6 Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move:4 - 1 - 9 - 2 Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move:2 - 4 - 1 - 3 - 6 Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move:6 - 5 - 4 - 1 - 9 - 2 Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

Example: Given m= 1,n = 1, return 9.

Approach 1: Brute Force

The Idea: For the first reader this problem may have some confusions due to the poor phrasing of the problem. One ambiguity to resolve from the diagram is that the digits are actually circles, and not framed in boxes. For example, digit 1 has the following options to take in the first step without crossing over other digits. The remaining digits have the following options:

    g = {1: {2, 4, 5, 6, 8},
         2: {1, 3, 4, 5, 6, 7, 9},
         3: {2, 4, 5, 6, 8},
         4: {1, 2, 3, 5, 7, 8, 9},
         5: {1, 2, 3, 4, 6, 7, 8, 9},
         6: {3, 2, 5, 8, 9, 1, 7},
         7: {4, 5, 8, 2, 6},
         8: {7, 4, 5, 6, 9, 1, 3},
         9: {8, 5, 6, 4, 2}}

Modeling this problem the correct way, I thought was the most challenging part of this problem. We can begin but first concretely define the rules for this problem. I have used a matrix to denote what the required number is in order to get to another number. For example, conditional[1][3] = 2, which denotes, that in order to get 1 to 3, we must at least pass through 2.

In this problem, the number of valid combinations or root to leaf paths are also the number of valid patterns. One thing to keep in mind is that each path in the tree carries within it an independent visited set. When we back track, we need to make the that the elements we visited before get marked back to False so that adjacent paths have access to this number.

There are two rules we have to satisfy in order to recur down the tree:

1. The path has to be unique (visit only once)

2. We cannot visit a digit in the phone that is required by the conditional UNLESS we already visited the element that is required by the conditional

Complexity: O(P^n) time, O(P) space, where P = Number of digits in the Pattern, and n = n-1, n-2, n-3 ... 0 (depends on digit). On average, we can say that n begins at 6, and decreases by 1 every level in the tree (but also sometimes potentially gain), so its hard to say.

class Solution:
    conditional = [[0 for j in range(10)] for i in range(10)]
    conditional[1][3] = conditional[3][1] = 2
    conditional[1][7] = conditional[7][1] = 4
    conditional[3][9] = conditional[9][3] = 6
    conditional[7][9] = conditional[9][7] = 8
    conditional[1][9] = conditional[9][1] = conditional[2][8] = conditional[8][2] = conditional[3][7] = conditional[7][3] = conditional[4][6] = conditional[6][4] = 5

    def numberOfPatterns(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """

        visited = [False] * 10
        def DFS(digit, max_path_length):
            if max_path_length == 1:
                return 1

            total_count = 0
            visited[digit] = True

            for next_digit in range(1, 10):
                # 1) The path has to be unique (visit only once)
                # 2) We cannot visit a digit in the phone that is required by the conditional UNLESS
                #    we already visited the element that is required by the conditional
                #    when conditional[x] == 0, this indicates that there are not constraints
                required_digit = Solution.conditional[digit][next_digit]
                if not visited[next_digit] and (required_digit == 0 or visited[required_digit]):
                    total_count += DFS(next_digit, max_path_length - 1)

            visited[digit] = False
            return total_count

        # sum all the possible path lengths between m and n
        total_patterns = 0
        for length in range(m, n + 1):
            for digit in range(1, 10):
                total_patterns += DFS(digit, length)

        return total_patterns