Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 304
Good morning! Here's your coding interview problem for today.

This problem was asked by Two Sigma.

A knight is placed on a given square on an 8 x 8 chessboard. It is then moved randomly several times, where each move is a standard knight move. If the knight jumps off the board at any point, however, it is not allowed to jump back on.

After `k` moves, what is the probability that the knight remains on the board?

Pull request description:
Day304
Resolves #618.

Patch:
diff --git a/README.md b/README.md
index 9735534..89aec29 100644
--- a/README.md
+++ b/README.md
@@ -310,3 +310,4 @@ problems from
 * [Day 300](https://github.com/vaskoz/dailycodingproblem-go/issues/612)
 * [Day 302](https://github.com/vaskoz/dailycodingproblem-go/issues/615)
 * [Day 303](https://github.com/vaskoz/dailycodingproblem-go/issues/616)
+* [Day 304](https://github.com/vaskoz/dailycodingproblem-go/issues/618)
diff --git a/day304/problem.go b/day304/problem.go
new file mode 100644
index 0000000..b970ead
--- /dev/null
+++ b/day304/problem.go
@@ -0,0 +1,36 @@
+package day304
+
+// ProbKnightOnBoard returns the probability that the knight is
+// on the board after k-random moves from a given start position.
+// Assumes an 8x8 chessboard.
+// Uses O(N*N*k) extra space and O(N*N*k) in run time.
+func ProbKnightOnBoard(row, col, k int) float64 {
+	const N = 8
+	moves := []struct{ x, y int }{
+		{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2},
+	}
+	probs := make([][][]float64, N)
+	for i := range probs {
+		probs[i] = make([][]float64, N)
+		for j := range probs[i] {
+			probs[i][j] = make([]float64, k+1)
+			probs[i][j][0] = 1.0
+		}
+	}
+	for step := 1; step < k+1; step++ {
+		for r := range probs {
+			for c := range probs[r] {
+				p := 0.0
+				for _, move := range moves {
+					nextRow := r + move.x
+					nextCol := c + move.y
+					if nextRow >= 0 && nextRow < 8 && nextCol >= 0 && nextCol < 8 {
+						p += probs[nextRow][nextCol][step-1] / 8.0
+					}
+				}
+				probs[r][c][step] = p
+			}
+		}
+	}
+	return probs[row][col][k]
+}


Test patch:
diff --git a/day304/problem_test.go b/day304/problem_test.go
new file mode 100644
index 0000000..805dbc9
--- /dev/null
+++ b/day304/problem_test.go
@@ -0,0 +1,30 @@
+package day304
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	row, col, k int
+	expected    float64
+}{
+	{0, 0, 3, 0.125},
+	{3, 3, 1, 1.0},
+	{3, 3, 2, 0.875},
+}
+
+func TestProbKnightOnBoard(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := ProbKnightOnBoard(tc.row, tc.col, tc.k); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkProbKnightOnBoard(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ProbKnightOnBoard(tc.row, tc.col, tc.k)
+		}
+	}
+}