Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 122
Good morning! Here's your coding interview problem for today.

This question was asked by Zillow.

You are given a 2-d matrix where each cell represents number of coins in that cell. Assuming we start at `matrix[0][0]`, and ***can only move right or down***, find the maximum number of coins you can collect by the bottom right corner.

For example, in this matrix
```
0 3 1 1
2 0 0 4
1 5 3 1
```
The most we can collect is `0 + 2 + 1 + 5 + 3 + 1 = 12 coins.`

Pull request:
Day122
Resolves #252.

Patch:
diff --git a/README.md b/README.md
index 29d3541..c1553c8 100644
--- a/README.md
+++ b/README.md
@@ -128,6 +128,7 @@ problems from
 * [Day 116](https://github.com/vaskoz/dailycodingproblem-go/issues/242)
 * [Day 118](https://github.com/vaskoz/dailycodingproblem-go/issues/246)
 * [Day 120](https://github.com/vaskoz/dailycodingproblem-go/issues/248)
+* [Day 122](https://github.com/vaskoz/dailycodingproblem-go/issues/252)
 * [Day 123](https://github.com/vaskoz/dailycodingproblem-go/issues/253)
 * [Day 124](https://github.com/vaskoz/dailycodingproblem-go/issues/255)
 * [Day 125](https://github.com/vaskoz/dailycodingproblem-go/issues/257)
diff --git a/day122/problem.go b/day122/problem.go
new file mode 100644
index 0000000..2677e86
--- /dev/null
+++ b/day122/problem.go
@@ -0,0 +1,25 @@
+package day122
+
+// MaxCoinsPath finds the maximum possible coins collected by going from upper-left
+// to lower-right. This is a backtracking algorithm.
+func MaxCoinsPath(grid [][]int) int {
+	return maxCoinsPathRecursive(grid, 0, 0)
+}
+
+func maxCoinsPathRecursive(grid [][]int, row, col int) int {
+	if row == len(grid)-1 && col == len(grid[0])-1 {
+		lastRow := grid[len(grid)-1]
+		return lastRow[len(lastRow)-1]
+	}
+	var right, down int
+	if col+1 < len(grid[0]) {
+		right = maxCoinsPathRecursive(grid, row, col+1)
+	}
+	if row+1 < len(grid) {
+		down = maxCoinsPathRecursive(grid, row+1, col)
+	}
+	if right > down {
+		return right + grid[row][col]
+	}
+	return down + grid[row][col]
+}


Test patch:
diff --git a/day122/problem_test.go b/day122/problem_test.go
new file mode 100644
index 0000000..f22489c
--- /dev/null
+++ b/day122/problem_test.go
@@ -0,0 +1,31 @@
+package day122
+
+import "testing"
+
+var testcases = []struct {
+	grid     [][]int
+	maxCoins int
+}{
+	{[][]int{
+		{0, 3, 1, 1},
+		{2, 0, 0, 4},
+		{1, 5, 3, 1}},
+		12},
+}
+
+func TestMaxCoinsPath(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if coins := MaxCoinsPath(tc.grid); coins != tc.maxCoins {
+			t.Errorf("Expected %v got %v", tc.maxCoins, coins)
+		}
+	}
+}
+
+func BenchmarkMaxCoinsPath(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxCoinsPath(tc.grid)
+		}
+	}
+}