Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 230
Good morning! Here's your coding interview problem for today.

This problem was asked by Goldman Sachs.

You are given N identical eggs and access to a building with k floors. Your task is to find the lowest floor that will cause an egg to break, if dropped from that floor. Once an egg breaks, it cannot be dropped again. If an egg breaks when dropped from the xth floor, you can assume it will also break when dropped from any floor greater than x.

Write an algorithm that finds the minimum number of trial drops it will take, in the worst case, to identify this floor.

For example, if N = 1 and k = 5, we will need to try dropping the egg at every floor, beginning with the first, until we reach the fifth floor, so our solution will be 5.

Pull request:
Day230
Resolves #473.

Patch:
diff --git a/README.md b/README.md
index c1adf43..c8f04d7 100644
--- a/README.md
+++ b/README.md
@@ -238,3 +238,4 @@ problems from
 * [Day 225](https://github.com/vaskoz/dailycodingproblem-go/issues/465)
 * [Day 226](https://github.com/vaskoz/dailycodingproblem-go/issues/467)
 * [Day 228](https://github.com/vaskoz/dailycodingproblem-go/issues/470)
+* [Day 230](https://github.com/vaskoz/dailycodingproblem-go/issues/473)
diff --git a/day230/problem.go b/day230/problem.go
new file mode 100644
index 0000000..215f62e
--- /dev/null
+++ b/day230/problem.go
@@ -0,0 +1,56 @@
+package day230
+
+// EggDropDP answers the egg drop question using dynamic programming.
+// Consumes O(eggs*floors) additional memory.
+func EggDropDP(eggs, floors int) int {
+	if floors < 0 || eggs < 0 {
+		panic("floors or eggs cannot be negative")
+	}
+	dp := make([][]int, eggs+1)
+	for i := range dp {
+		dp[i] = make([]int, floors+1)
+		dp[i][0] = 1
+	}
+	for i := 1; i < floors+1; i++ {
+		dp[1][i] = i
+	}
+	for i := 2; i < eggs+1; i++ {
+		for j := 2; j < floors+1; j++ {
+			dp[i][j] = int(^uint(0) >> 1)
+			for k := 1; k < j+1; k++ {
+				res := 1 + max(dp[i-1][k-1], dp[i][j-k])
+				if res < dp[i][j] {
+					dp[i][j] = res
+				}
+			}
+		}
+	}
+	return dp[eggs][floors]
+}
+
+// EggDropRecursive answers the egg drop question
+// recursively.
+func EggDropRecursive(eggs, floors int) int {
+	if floors < 0 || eggs < 0 {
+		panic("floors or eggs cannot be negative")
+	}
+	if floors < 2 || eggs == 1 {
+		return floors
+	}
+	min := int(^uint(0) >> 1)
+	for floor := 1; floor <= floors; floor++ {
+		result := max(EggDropRecursive(eggs-1, floor-1),
+			EggDropRecursive(eggs, floors-floor))
+		if result < min {
+			min = result
+		}
+	}
+	return min + 1
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day230/problem_test.go b/day230/problem_test.go
new file mode 100644
index 0000000..756d5ab
--- /dev/null
+++ b/day230/problem_test.go
@@ -0,0 +1,65 @@
+package day230
+
+import "testing"
+
+var testcases = []struct {
+	eggs, floors int
+	minimum      int
+}{
+	{1, 5, 5},
+	{2, 10, 4},
+}
+
+func TestEggDropDP(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := EggDropDP(tc.eggs, tc.floors); result != tc.minimum {
+			t.Errorf("Expected %d, got %d", tc.minimum, result)
+		}
+	}
+}
+
+func TestEggDropDPPanic(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("expected a panic for negative values")
+		}
+	}()
+	EggDropDP(-1, 0)
+}
+
+func BenchmarkEggDropDP(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			EggDropDP(tc.eggs, tc.floors)
+		}
+	}
+}
+
+func TestEggDropRecursive(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := EggDropRecursive(tc.eggs, tc.floors); result != tc.minimum {
+			t.Errorf("Expected %d, got %d", tc.minimum, result)
+		}
+	}
+}
+
+func TestEggDropRecursivePanic(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("expected a panic for negative values")
+		}
+	}()
+	EggDropRecursive(-1, 0)
+}
+
+func BenchmarkEggDropRecursive(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			EggDropRecursive(tc.eggs, tc.floors)
+		}
+	}
+}