## Saturday, May 12, 2018

### LeetCode 688 - Knight Probability in Chessboard

https://leetcode.com/problems/knight-probability-in-chessboard/
On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly K moves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).
A chess knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.
The knight continues moving until it has made exactly K moves or has moved off the chessboard. Return the probability that the knight remains on the board after it has stopped moving.
Example:
Input: 3, 2, 0, 0
Output: 0.0625
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

Note:

• N will be between 1 and 25.
• K will be between 0 and 100.
• The knight always initially starts on the board.

• https://leetcode.com/problems/knight-probability-in-chessboard/solution/
Let f[r][c][steps] be the probability of being on square (r, c) after steps steps. Based on how a knight moves, we have the following recursion:
$f[r][c][steps] = \sum_{dr, dc} f[r+dr][c+dc][steps-1] / 8.0$
where the sum is taken over the eight $(dr, dc)$ pairs $(2, 1),$ $(2, -1),$ $(-2, 1),$ $(-2, -1),$ $(1, 2),$ $(1, -2),$ $(-1, 2),$ $(-1, -2)$.
Instead of using a three-dimensional array f, we will use two two-dimensional ones dp and dp2, storing the result of the two most recent layers we are working on. dp2 will represent f[][][steps], and dp will represent f[][][steps-1].
• Time Complexity: $O(N^2 K)$ where $N, K$ are defined as in the problem. We do $O(1)$ work on each layer dp of $N^2$ elements, and there are $K$ layers considered.
• Space Complexity: $O(N^2)$, the size of dp and dp2.
It's no need to create 'double[][] dp1' inside the loop. Create it outside and reuse it, swap 'dp0' and 'dp1' after calculating.
public double knightProbability(int N, int K, int sr, int sc) {
double[][] dp = new double[N][N];
int[] dr = new int[]{2, 2, 1, 1, -1, -1, -2, -2};
int[] dc = new int[]{1, -1, 2, -2, 2, -2, 1, -1};

dp[sr][sc] = 1;
for (; K > 0; K--) {
double[][] dp2 = new double[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
for (int k = 0; k < 8; k++) {
int cr = r + dr[k];
int cc = c + dc[k];
if (0 <= cr && cr < N && 0 <= cc && cc < N) {
dp2[cr][cc] += dp[r][c] / 8.0;
}
}
}
}
dp = dp2;
}
double ans = 0.0;
for (double[] row: dp) {
for (double x: row) ans += x;
}
return ans;
}
https://leetcode.com/problems/knight-probability-in-chessboard/discuss/108214/My-easy-understand-dp-solution
    private int[][] dirs = new int[][]{{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
public double knightProbability(int N, int K, int r, int c) {
double[][][] dp = new double[K + 1][N][N];
dp[0][r][c] = 1;
for (int step = 1; step <= K; step++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int[] dir : dirs) {
int x = dir[0] + i;
int y = dir[1] + j;
if (x < 0 || x >= N || y < 0 || y >= N) continue;
dp[step][i][j] += dp[step - 1][x][y] * 0.125;
}
}
}
}
double res = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
res += dp[K][i][j];
}
}
return res;
}

X. https://leetcode.com/problems/knight-probability-in-chessboard/discuss/113954/Evolve-from-recursive-to-dpbeats-94
recursive version(TLE):
class Solution {
private int[][]dir = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
public double knightProbability(int N, int K, int r, int c) {
return find(N,K,r,c);
}
public double find(int N,int K,int r,int c){
if(r < 0 || r > N - 1 || c < 0 || c > N - 1) return 0;
if(K == 0)  return 1;
double rate = 0;
for(int i = 0;i < dir.length;i++){
rate += 0.125 * find(N,K - 1,r + dir[i][0],c + dir[i][1]);
}
return rate;
}
}

dp version:
class Solution {
private int[][]dir = new int[][]{{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
private double[][][] dp;
public double knightProbability(int N, int K, int r, int c) {
dp = new double[N][N][K + 1];
return find(N,K,r,c);
}
public double find(int N,int K,int r,int c){
if(r < 0 || r > N - 1 || c < 0 || c > N - 1) return 0;
if(K == 0)  return 1;
if(dp[r][c][K] != 0) return dp[r][c][K];
double rate = 0;
for(int i = 0;i < dir.length;i++)   rate += 0.125 * find(N,K - 1,r + dir[i][0],c + dir[i][1]);
dp[r][c][K] = rate;
return rate;
}
}

X. BFS + Path Compression

private static final int[][] direction = new int[][] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 },
{ -2, -1 } };

// k moves, n*n board, starts at r, c
// n, k starts with 1
public double knightProbability(int n, int k, int r, int c) {

Queue<Element> queue = new ArrayDeque<>();

while (k > 0) {
k--;
int size = queue.size();
Map<Integer, Double> cache = new HashMap<>();
for (int i = 0; i < size; i++) {
Element cur = queue.poll();
for (int j = 0; j < direction.length; j++) {
int newRol = cur.row + direction[j][0];
int newCol = cur.col + direction[j][1];
if (isValid(newRol, newCol, n)) {
int key = newRol * n + newCol;
cache.put(key, cache.getOrDefault(key, 0d) + cur.prob / 8);
}
// queue.add(new Element(newRol, newCol, cur.step + 1, cur.prob / 8));
}
}

for (Entry<Integer, Double> entry : cache.entrySet()) {
queue.add(new Element(entry.getKey() / n, entry.getKey() % n, entry.getValue()));
}
}

double totalPro = 0;
// for (int i = 0; i < queue.size(); i++) {
while (!queue.isEmpty()) {
totalPro += queue.poll().prob;
}
}

private boolean isValid(int row, int col, int n) {
return row >= 0 && row <= n - 1 && col >= 0 && col <= n - 1;
}

private static class Element {
public final int row, col;
public double prob;

public Element(int row, int col, double prob) {
super();
this.row = row;
this.col = col;
this.prob = prob;
}

@Override
public String toString() {
return "Element [row=" + row + ", col=" + col + ", prob=" + prob + "]";
}
}
X. Approach #2: Matrix Exponentiation
The recurrence expressed in Approach #1 expressed states that transitioned to a linear combination of other states. Any time this happens, we can represent the entire transition as a matrix of those linear combinations. Then, the $n$-th power of this matrix represents the transition of $n$ moves, and thus we can reduce the problem to a problem of matrix exponentiation.
Algorithm
First, there is a lot of symmetry on the board that we can exploit. Naively, there are $N^2$ possible states the knight can be in (assuming it is on the board). Because of symmetry through the horizontal, vertical, and diagonal axes, we can assume that the knight is in the top-left quadrant of the board, and that the column number is equal to or larger than the row number. For any square, the square that is found by reflecting about these axes to satisfy these conditions will be the canonical index of that square.
This will reduce the number of states from $N^2$ to approximately $\frac{N^2}{8}$, which makes the following (cubic) matrix exponentiation on this $O(\frac{N^2}{8}) \times O(\frac{N^2}{8})$ matrix approximately $8^3$ times faster.
Now, if we know that every state becomes some linear combination of states after one move, then let's write a transition matrix $\mathcal{T}$ of them, where the $i$-th row of $\mathcal{T}$ represents the linear combination of states that the $i$-th state goes to. Then, $\mathcal{T}^n$ represents a transition of $n$ moves, for which we want the sum of the $i$-th row, where $i$is the index of the starting square.
• Time Complexity: $O(N^6 \log(K))$ where $N, K$ are defined as in the problem. There are approximately $\frac{N^2}{8}$canonical states, which makes our matrix multiplication $O(N^6)$. To find the $K$-th power of this matrix, we make $O(\log(K))$ matrix multiplications.
• Space Complexity: $O(N^4)$. The matrix has approximately $\frac{N^4}{64}$ elements.

public double knightProbability(int N, int K, int sr, int sc) {
int[] dr = new int[]{-1, -1, 1, 1, -2, -2, 2, 2};
int[] dc = new int[]{2, -2, 2, -2, 1, -1, 1, -1};

int[] index = new int[N * N];
int t = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (r * N + c == canonical(r, c, N)) {
index[r * N + c] = t;
t++;
} else {
index[r * N + c] = index[canonical(r, c, N)];
}
}
}

double[][] T = new double[t][t];
int curRow = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (r * N + c == canonical(r, c, N)) {
for (int k = 0; k < 8; k++) {
int cr = r + dr[k], cc = c + dc[k];
if (0 <= cr && cr < N && 0 <= cc && cc < N) {
T[curRow][index[canonical(cr, cc, N)]] += 0.125;
}
}
curRow++;
}
}
}

double[] row = matrixExpo(T, K)[index[sr*N + sc]];
double ans = 0.0;
for (double x: row) ans += x;
return ans;
}

public int canonical(int r, int c, int N) {
if (2*r > N) r = N-1-r;
if (2*c > N) c = N-1-c;
if (r > c) {
int t = r;
r = c;
c = t;
}
return r * N + c;
}
public double[][] matrixMult(double[][] A, double[][] B) {
double[][] ans = new double[A.length][A.length];
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B[0].length; j++) {
for (int k = 0; k < B.length; k++) {
ans[i][j] += A[i][k] * B[k][j];
}
}
}
return ans;
}
public double[][] matrixExpo(double[][] A, int pow) {
double[][] ans = new double[A.length][A.length];
for (int i = 0; i < A.length; i++) ans[i][i] = 1;
if (pow == 0) return ans;
if (pow == 1) return A;
if (pow % 2 == 1) return matrixMult(matrixExpo(A, pow-1), A);
double[][] B = matrixExpo(A, pow / 2);
return matrixMult(B, B);
}