Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 229
Good morning! Here's your coding interview problem for today.

This problem was asked by Flipkart.

Snakes and Ladders is a game played on a 10 x 10 board, the goal of which is get from square 1 to square 100. On each turn players will roll a six-sided die and move forward a number of spaces equal to the result. If they land on a square that represents a snake or ladder, they will be transported ahead or behind, respectively, to a new square.

Find the smallest number of turns it takes to play snakes and ladders.

For convenience, here are the squares representing snakes and ladders, and their outcomes:

snakes = `{16: 6, 48: 26, 49: 11, 56: 53, 62: 19, 64: 60, 87: 24, 93: 73, 95: 75, 98: 78}`
ladders = `{1: 38, 4: 14, 9: 31, 21: 42, 28: 84, 36: 44, 51: 67, 71: 91, 80: 100}`

Pull request description:
Day229
Resolves #472.

Patch:
diff --git a/README.md b/README.md
index f389e11..9188c9f 100644
--- a/README.md
+++ b/README.md
@@ -239,6 +239,7 @@ problems from
 * [Day 226](https://github.com/vaskoz/dailycodingproblem-go/issues/467)
 * [Day 227](https://github.com/vaskoz/dailycodingproblem-go/issues/469)
 * [Day 228](https://github.com/vaskoz/dailycodingproblem-go/issues/470)
+* [Day 229](https://github.com/vaskoz/dailycodingproblem-go/issues/472)
 * [Day 230](https://github.com/vaskoz/dailycodingproblem-go/issues/473)
 * [Day 231](https://github.com/vaskoz/dailycodingproblem-go/issues/475)
 * [Day 232](https://github.com/vaskoz/dailycodingproblem-go/issues/477)
diff --git a/day229/problem.go b/day229/problem.go
new file mode 100644
index 0000000..e90e09e
--- /dev/null
+++ b/day229/problem.go
@@ -0,0 +1,42 @@
+package day229
+
+// Jump represents the movement that happens either up or down.
+// Ladders give you a boost up, while a Snake lowers your position.
+type Jump struct {
+	From, To int
+}
+
+// SnakesAndLaddersFewestTurns by playing all games.
+func SnakesAndLaddersFewestTurns(ladders, snakes []Jump, maxDepth int) int {
+	jumps := make(map[int]int, len(ladders)+len(snakes))
+	for _, j := range ladders {
+		jumps[j.From] = j.To
+	}
+	for _, j := range snakes {
+		jumps[j.From] = j.To
+	}
+	return snakesAndLaddersFewestTurns(jumps, 0, 0, int(^uint(0)>>1), maxDepth)
+}
+
+func snakesAndLaddersFewestTurns(jumps map[int]int, pos, depth, bestSoFar, maxDepth int) int {
+	if pos == 100 {
+		return depth
+	} else if depth > maxDepth || depth > bestSoFar {
+		return bestSoFar
+	}
+	for roll := 6; roll >= 0; roll-- {
+		next := pos + roll
+		if jumpPos, found := jumps[next]; found && jumpPos < pos { // avoid all snakes
+			continue
+		} else if found && jumpPos > pos {
+			next = jumpPos
+		}
+		if next > 100 {
+			break
+		}
+		if turns := snakesAndLaddersFewestTurns(jumps, next, depth+1, bestSoFar, maxDepth); turns < bestSoFar {
+			bestSoFar = turns
+		}
+	}
+	return bestSoFar
+}


Test patch:
diff --git a/day229/problem_test.go b/day229/problem_test.go
new file mode 100644
index 0000000..dc20c4f
--- /dev/null
+++ b/day229/problem_test.go
@@ -0,0 +1,15 @@
+package day229
+
+import "testing"
+
+func TestSnakesAndLaddersFewestTurns(t *testing.T) {
+	t.Parallel()
+	fewestTurns := SnakesAndLaddersFewestTurns(
+		[]Jump{{1, 38}, {4, 14}, {9, 31}, {21, 42}, {28, 84}, {36, 44}, {51, 67}, {71, 91}, {80, 100}},
+		[]Jump{{16, 6}, {48, 26}, {49, 11}, {56, 53}, {62, 19}, {64, 60}, {87, 24}, {93, 73}, {95, 75}, {98, 78}},
+		6,
+	)
+	if fewestTurns != 7 {
+		t.Errorf("on the original game board best is 7, got %v", fewestTurns)
+	}
+}