Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 220
Good morning! Here's your coding interview problem for today.

This problem was asked by Square.

In front of you is a row of N coins, with values `v1, v1, ..., vn`.

You are asked to play the following game. You and an opponent take turns choosing either the first or last coin from the row, removing it from the row, and receiving the value of the coin.

Write a program that returns the maximum amount of money you can win with certainty, if you move first, assuming your opponent plays optimally.

Pull request description:
Day220
Resolves #453.

Patch:
diff --git a/README.md b/README.md
index 58b8fe3..3f1340d 100644
--- a/README.md
+++ b/README.md
@@ -229,4 +229,5 @@ problems from
 * [Day 216](https://github.com/vaskoz/dailycodingproblem-go/issues/445)
 * [Day 217](https://github.com/vaskoz/dailycodingproblem-go/issues/447)
 * [Day 218](https://github.com/vaskoz/dailycodingproblem-go/issues/449)
+* [Day 220](https://github.com/vaskoz/dailycodingproblem-go/issues/453)
 * [Day 221](https://github.com/vaskoz/dailycodingproblem-go/issues/454)
diff --git a/day220/problem.go b/day220/problem.go
new file mode 100644
index 0000000..e9085f4
--- /dev/null
+++ b/day220/problem.go
@@ -0,0 +1,41 @@
+package day220
+
+// AlternatingCoinsFirst solves the game using dynamic programming.
+// You and an opponent take turns choosing either the first or
+// last coin from the row, removing it from the row, and receiving the value of the coin.
+func AlternatingCoinsFirst(coins []int) int {
+	value := make([][]int, len(coins))
+	for i := range value {
+		value[i] = make([]int, len(coins))
+	}
+	for interval := range value {
+		for i, j := 0, interval; j < len(coins); i, j = i+1, j+1 {
+			var a, b, c int
+			if i+2 <= j {
+				a = value[i+2][j]
+			}
+			if i+1 <= j-1 {
+				b = value[i+1][j-1]
+			}
+			if i <= j-2 {
+				c = value[i][j-2]
+			}
+			value[i][j] = max(coins[i]+min(a, b), coins[j]+min(b, c))
+		}
+	}
+	return value[0][len(coins)-1]
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day220/problem_test.go b/day220/problem_test.go
new file mode 100644
index 0000000..35f3e9a
--- /dev/null
+++ b/day220/problem_test.go
@@ -0,0 +1,30 @@
+package day220
+
+import "testing"
+
+var testcases = []struct {
+	coins     []int
+	maxProfit int
+}{
+	{[]int{6, 9, 1, 2, 16, 8}, 23},
+	{[]int{8, 15, 3, 7}, 22},
+	{[]int{2, 2, 2, 2}, 4},
+	{[]int{20, 30, 2, 2, 2, 10}, 42},
+}
+
+func TestAlternatingCoinsFirst(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := AlternatingCoinsFirst(tc.coins); result != tc.maxProfit {
+			t.Errorf("Expected %v, got %v", tc.maxProfit, result)
+		}
+	}
+}
+
+func BenchmarkAlternatingCoinsFirst(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			AlternatingCoinsFirst(tc.coins)
+		}
+	}
+}