Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 294
Good morning! Here's your coding interview problem for today.

This problem was asked by Square.

A competitive runner would like to create a route that starts and ends at his house, with the condition that the route goes entirely uphill at first, and then entirely downhill.

Given a dictionary of places of the form `{location: elevation}`, and a dictionary mapping paths between some of these locations to their corresponding distances, find the length of the shortest route satisfying the condition above. Assume the runner's home is location 0.

For example, suppose you are given the following input:
```
elevations = {0: 5, 1: 25, 2: 15, 3: 20, 4: 10}
paths = {
    (0, 1): 10,
    (0, 2): 8,
    (0, 3): 15,
    (1, 3): 12,
    (2, 4): 10,
    (3, 4): 5,
    (3, 0): 17,
    (4, 0): 10
}
```
In this case, the shortest valid path would be `0 -> 2 -> 4 -> 0`, with a distance of `28`.

Pull request:
Day294
Resolves #600.

Patch:
diff --git a/README.md b/README.md
index 6c9d998..70851d2 100644
--- a/README.md
+++ b/README.md
@@ -301,4 +301,5 @@ problems from
 * [Day 288](https://github.com/vaskoz/dailycodingproblem-go/issues/590)
 * [Day 290](https://github.com/vaskoz/dailycodingproblem-go/issues/594)
 * [Day 291](https://github.com/vaskoz/dailycodingproblem-go/issues/596)
+* [Day 294](https://github.com/vaskoz/dailycodingproblem-go/issues/600)
 * [Day 295](https://github.com/vaskoz/dailycodingproblem-go/issues/601)
diff --git a/day294/problem.go b/day294/problem.go
new file mode 100644
index 0000000..6cdbb04
--- /dev/null
+++ b/day294/problem.go
@@ -0,0 +1,81 @@
+package day294
+
+import (
+	"errors"
+)
+
+// Elevation is a map of locations to their elevations.
+type Elevation map[int]int
+
+// PathDistance represents the distance for a particular path.
+type PathDistance map[int]map[int]int
+
+// MaxInt is the largest int.
+const MaxInt = int(^uint(0) >> 1)
+
+var errNotPossible = errors.New("no path possible")
+
+// ErrNotPossible is the error returned if a path doesn't exist.
+func ErrNotPossible() error {
+	return errNotPossible
+}
+
+// ShortestRunnerPath with the condition that the route goes entirely
+// uphill at first, and then entirely downhill.
+// Always starts at location 0 and end at location 0.
+func ShortestRunnerPath(elevations Elevation, paths PathDistance) (int, error) {
+	min := MaxInt
+	startElev := elevations[0]
+	for next, distance := range paths[0] {
+		nextElev := elevations[next]
+		if nextElev > startElev {
+			dist, err := shortestRunnerPath(elevations, paths, map[int]struct{}{}, true, next)
+			if err == nil && dist+distance < min {
+				min = dist + distance
+			}
+		}
+	}
+	if min == MaxInt {
+		return 0, ErrNotPossible()
+	}
+	return min, nil
+}
+
+func shortestRunnerPath(
+	elevations Elevation,
+	paths PathDistance,
+	visited map[int]struct{},
+	up bool,
+	n int) (int, error) {
+	if n == 0 {
+		return 0, nil
+	}
+	min := MaxInt
+	currentElevation := elevations[n]
+	for next, distance := range paths[n] {
+		if _, visit := visited[next]; !visit {
+			nextElevation := elevations[next]
+			if up && nextElevation > currentElevation {
+				visited[next] = struct{}{}
+				dist, err := shortestRunnerPath(elevations, paths, visited, true, next)
+				totalDist := dist + distance
+				if err == nil && totalDist < min {
+					min = totalDist
+				}
+				delete(visited, next)
+			} else if nextElevation < currentElevation {
+				visited[next] = struct{}{}
+				dist, err := shortestRunnerPath(elevations, paths, visited, false, next)
+				totalDist := dist + distance
+				if err == nil && totalDist < min {
+					min = totalDist
+				}
+				delete(visited, next)
+			}
+		}
+	}
+	if min == MaxInt {
+		return 0, ErrNotPossible()
+	}
+	return min, nil
+}


Test patch:
diff --git a/day294/problem_test.go b/day294/problem_test.go
new file mode 100644
index 0000000..7647754
--- /dev/null
+++ b/day294/problem_test.go
@@ -0,0 +1,144 @@
+package day294
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	elevations    Elevation
+	paths         PathDistance
+	shortestRoute int
+	err           error
+}{
+	{
+		Elevation{
+			0: 15,
+			1: 10,
+			2: 25,
+		},
+		PathDistance{
+			0: {
+				2: 5,
+			},
+			1: {
+				0: 1,
+			},
+			2: {
+				1: 7,
+			},
+		},
+		0,
+		ErrNotPossible(),
+	},
+	{
+		Elevation{
+			0: 10,
+			1: 25,
+			2: 15,
+		},
+		PathDistance{
+			0: {
+				1: 15,
+				2: 5,
+			},
+			1: {
+				0: 1,
+			},
+			2: {
+				1: 7,
+				0: 30,
+			},
+		},
+		13,
+		nil,
+	},
+	{
+		Elevation{
+			0: 10,
+			1: 5,
+			2: 7,
+		},
+		PathDistance{
+			0: {
+				1: 5,
+				2: 10,
+			},
+			1: {
+				0: 5,
+			},
+			2: {
+				0: 10,
+			},
+		},
+		0,
+		ErrNotPossible(),
+	},
+	{
+		Elevation{
+			0: 10,
+			1: 5,
+			2: 15,
+		},
+		PathDistance{
+			0: {
+				1: 5,
+				2: 10,
+			},
+			1: {
+				0: 5,
+			},
+			2: {
+				0: 10,
+			},
+		},
+		20,
+		nil,
+	},
+	{
+		Elevation{
+			0: 5,
+			1: 25,
+			2: 15,
+			3: 20,
+			4: 10,
+		},
+		PathDistance{
+			0: {
+				1: 10,
+				2: 8,
+				3: 15,
+			},
+			1: {
+				3: 12,
+			},
+			2: {
+				4: 10,
+			},
+			3: {
+				4: 5,
+				0: 17,
+			},
+			4: {
+				0: 10,
+			},
+		},
+		28,
+		nil,
+	},
+}
+
+func TestShortestRunnerPath(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := ShortestRunnerPath(tc.elevations, tc.paths); result != tc.shortestRoute || err != tc.err {
+			t.Errorf("Expected (%v,%v), got (%v,%v)", tc.shortestRoute, tc.err, result, err)
+		}
+	}
+}
+
+func BenchmarkShortestRunnerPath(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ShortestRunnerPath(tc.elevations, tc.paths) // nolint
+		}
+	}
+}