Leetcode discuss: 351. Android Unlock Patterns

 

C# - DFS - Code study - Simple and working

Nov. 20, 2020
Introduction
It is hard for me to understand the requirement under stress, my mock interview. I like to practice how to rephrase the problem.

Given the range of possible length of pattern, find how many variations to form pattern from 1-9 key screen 3 rows x 3 columns. The challenge is that every move should not cross unvisited digit in key screen.

Case study
1 2 3
4 5 6
7 8 9
example 1: pattern (2, 1, 3) - it is ok. second move, 1->3, 2 is already visited in first move.
example 2: pattern (1, 3, 2) - it is not allowed. First move 1 -> 3, 2 is not visited, so it is not a legal move.

The idea is to go over all possible lengths, and start from (0,0) or (0, 1) or (1, 1). It is true that all other three corners in 3 x 3 matrix is same as (0,0). Next it is true that all other three center node is same as (0, 1).

corner: 1, 3, 7, 9
middle: 2, 4, 6, 8
center: 5

 public class Solution {
    
	/// code study: https://leetcode.com/problems/android-unlock-patterns/discuss/311456/C-DFS-%2B-isValid-with-explanation
    public int NumberOfPatterns(int m, int n) {
         var row = 3;
            var col = 3;

            var minKeys = m;
            var maxKeys = n;

            var visited = new bool[row, col];

            var result = 0;

            // go over pattern - count of keys
            for (int i = minKeys; i <= maxKeys; i++)
            {
                visited[0, 0] = true;
                int topLeft = runDFS(visited, i - 1, 0, 0);
                visited[0, 0] = false;

                visited[0, 1] = true;
                int middleLeft = runDFS(visited, i - 1, 0, 1);
                visited[0, 1] = false;

                visited[1, 1] = true;
                int center = runDFS(visited, i - 1, 1, 1);
                visited[1, 1] = false;

                result += topLeft * 4 + middleLeft * 4 + center;
            }

            return result;
        }

        /// <summary>
        /// depth first search
        /// pattern -> sequence of digits - 
        /// </summary>
        /// <param name="visited"></param>
        /// <param name="stepsLeft">steps to go</param>
        /// <param name="currentRow">horizontal position</param>
        /// <param name="currentCol">vertical position</param>
        /// <returns></returns>
        private int runDFS(bool[,] visited, int stepsLeft, int currentRow, int currentCol)
        {
            if (stepsLeft == 0)
            {
                return 1;
            }

            const int SIZE = 3; 

            var sum = 0;

            for (int nextRow = 0; nextRow < SIZE; nextRow++)
            {
                for (int nextCol = 0; nextCol < SIZE; nextCol++)
                {
                    // one digit only once in a pattern
                    if (visited[nextRow, nextCol])
                    {
                        continue;
                    }

                    if (!IsValid(currentRow, currentCol, nextRow, nextCol, visited))
                    {
                        continue;
                    }

                    visited[nextRow, nextCol] = true;
                    sum += runDFS(visited, stepsLeft - 1, nextRow, nextCol);

                    // backtracking
                    visited[nextRow, nextCol] = false;
                }
            }

            return sum;
        }

        /// <summary>
        /// check valid move - 
        /// determine if the position is visited or not. 
        /// next is to determine if unvisited node is crossed - not allowed.
        /// </summary>
        /// <param name="startRow"></param>
        /// <param name="startCol"></param>
        /// <param name="nextRow"></param>
        /// <param name="nextCol"></param>
        /// <param name="visited"></param>
        /// <returns></returns>
        private bool IsValid(int startRow, int startCol, int nextRow, int nextCol, bool[,] visited)
        {
            var xDistance = Math.Abs(startRow - nextRow);
            var yDistance = Math.Abs(startCol - nextCol);
            
              // same row - one in between
            if ((xDistance == 0 && yDistance == 2 && !visited[startRow, 1]) ||
              // 1st, 3rd row - same column - three cases: column 0, 1, 2
                (xDistance == 2 && yDistance == 0 && !visited[1, startCol]) ||
              // diagonal - (0,0) and (2, 2) -
                (xDistance == 2 && yDistance == 2 && !visited[1, 1]))
            {
                return false;
            }

            return true;
        }
}