## Friday, November 20, 2020

### 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;
}
}``````