Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 245
Good morning! Here's your coding interview problem for today.

This problem was asked by Yelp.

You are given an array of integers, where each element represents the maximum number of steps that can be jumped going forward from that element. Write a function to return the minimum number of jumps you must take in order to get from the start to the end of the array.

For example, given `[6, 2, 4, 0, 5, 1, 1, 4, 2, 9]`, you should return `2`, as the optimal solution involves jumping from `6` to `5`, and then from `5` to `9`.

Pull request description:
Day245
Resolves #506.

Patch:
diff --git a/README.md b/README.md
index 45a2c09..5e736ac 100644
--- a/README.md
+++ b/README.md
@@ -256,3 +256,4 @@ problems from
 * [Day 242](https://github.com/vaskoz/dailycodingproblem-go/issues/498)
 * [Day 243](https://github.com/vaskoz/dailycodingproblem-go/issues/502)
 * [Day 244](https://github.com/vaskoz/dailycodingproblem-go/issues/503)
+* [Day 245](https://github.com/vaskoz/dailycodingproblem-go/issues/506)
diff --git a/day245/problem.go b/day245/problem.go
new file mode 100644
index 0000000..460cbe7
--- /dev/null
+++ b/day245/problem.go
@@ -0,0 +1,38 @@
+package day245
+
+import "errors"
+
+var errImpassable = errors.New("impossible to reach the end")
+
+// ErrImpassable returns the error associated with an impassable
+// route.
+func ErrImpassable() error {
+	return errImpassable
+}
+
+// MinimumJumps returns the minimum steps to reach the end.
+// Each element contains the max steps that can be taken
+// in a single jump.
+// Returns an error if impassable.
+func MinimumJumps(maxSteps []int) (int, error) {
+	if len(maxSteps) < 2 {
+		return 0, nil
+	}
+	minJumps := int(^uint(0) >> 1)
+	if maxSteps[0] == 0 { // can't jump from this cell
+		return 0, errImpassable
+	}
+	impassable := true
+	for jump := maxSteps[0]; jump > 0; jump-- {
+		if jump < len(maxSteps) {
+			if result, impass := MinimumJumps(maxSteps[jump:]); impass == nil && result < minJumps {
+				impassable = false
+				minJumps = result
+			}
+		}
+	}
+	if impassable {
+		return 0, errImpassable
+	}
+	return minJumps + 1, nil
+}


Test patch:
diff --git a/day245/problem_test.go b/day245/problem_test.go
new file mode 100644
index 0000000..46d5683
--- /dev/null
+++ b/day245/problem_test.go
@@ -0,0 +1,35 @@
+package day245
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	maxSteps      []int
+	expectedJumps int
+	impassable    error
+}{
+	{[]int{6, 2, 4, 0, 5, 1, 1, 4, 2, 9}, 2, nil},
+	{[]int{9}, 0, nil},
+	{[]int{}, 0, nil},
+	{nil, 0, nil},
+	{[]int{1, 1, 1, 1, 1, 1, 1}, 6, nil},
+	{[]int{1, 1, 0, 1, 1}, 0, ErrImpassable()},
+	{[]int{1, 2, 0, 1, 1}, 3, nil},
+}
+
+func TestMinimumJumps(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if jumps, impassable := MinimumJumps(tc.maxSteps); impassable != tc.impassable || jumps != tc.expectedJumps {
+			t.Errorf("Expected (%v,%v), got (%v,%v)", tc.expectedJumps, tc.impassable, jumps, impassable)
+		}
+	}
+}
+
+func BenchmarkMinimumJumps(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinimumJumps(tc.maxSteps) //nolint
+		}
+	}
+}