Shortest Uphill-Downhill Route for a Competitive Runner

Problem

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.

Examples

Example 1:

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
}
Output: 28
Explanation: The shortest path is 0 -> 2 -> 4 -> 0. 
Elevations during the run 5 -> 15 -> 10 -> 5, distance is:
0 -> 2 = 8, 2 -> 4 = 10, 4 -> 0 = 10 = 8 + 10 + 10 = 28.

Solution

Method 1 - DFS

Here's an overall approach to solve the problem:

1. Graph Representation:
   • Use the elevations dictionary to store the elevation of each location.
   • Use the paths dictionary to represent edges between the locations with their distances.
2. Finding Valid Paths:
   • Use Depth-First Search (DFS) to explore possible uphill routes from the home location 0.
   • For each uphill path found, use DFS to search for a valid downhill path back to the home location 0.
3. Tracking the Shortest Path:
   • Track the shortest valid path satisfying the constraints.

Code

Java

public class KnightsTourRoute {

	private int shortestDistance = Integer.MAX_VALUE;

	private List<Integer> shortestPath = new ArrayList<>();

	public void computeShortestRoute(Map<Integer, Integer> elevations, Map < int[], Integer > paths) {
		Set<Integer> visited = new HashSet<>();
		visited.add(0);
		List<Integer> path = new ArrayList<>();
		path.add(0);
		dfsUpHill(0, paths, elevations, visited, 0, path);
	}

	private void dfsUpHill(int current, Map < int[], Integer > paths, Map<Integer, Integer> elevations, Set<Integer> visited, int totalDistance, List<Integer> path) {
		if (current != 0 && elevations.get(current) < elevations.get(0)) {
			dfsDownHill(current, paths, elevations, visited, totalDistance, path);
			return;
		}

		for (Map.Entry < int[], Integer > entry: paths.entrySet()) {
			int start = entry.getKey()[0];
			int end = entry.getKey()[1];
			int distance = entry.getValue();

			if (start == current && !visited.contains(end) && elevations.get(end) > elevations.get(current)) {
				visited.add(end);
				path.add(end);
				dfsUpHill(end, paths, elevations, visited, totalDistance + distance, path);
				path.remove(path.size() - 1);
				visited.remove(end);
			}
		}
	}

	private static void dfsDownHill(int current, Map <int[], Integer> paths, Map<Integer, Integer> elevations, Set<Integer> visited, int totalDistance, List<Integer> path) {
		if (current == 0) {
			if (totalDistance < shortestDistance) {
				shortestDistance = totalDistance;
				shortestPath = new ArrayList<>(path);
			}

			return;
		}

		for (Map.Entry < int[], Integer > entry: paths.entrySet()) {
			int start = entry.getKey()[0];
			int end = entry.getKey()[1];
			int distance = entry.getValue();

			if (start == current && !visited.contains(end) && elevations.get(end) < elevations.get(current)) {
				visited.add(end);
				path.add(end);
				dfsDownHill(end, paths, elevations, visited, totalDistance + distance, path);
				path.remove(path.size() - 1);
				visited.remove(end);
			}
		}
	}
}

Python

def find_shortest_route(
    elevations: dict[int, int], paths: dict[tuple[int, int], int]
) -> tuple[list[int], int]:
    def dfs_uphill(
        current: int, visited: set, path: list[int], total_dist: int
    ) -> None:
        nonlocal shortest_path, shortest_distance

        # Once we reach the downhill part, start checking downhill paths
        if current != 0 and elevations[current] < elevations[home]:
            dfs_downhill(current, visited, path, total_dist)
            return

        for (start, end), dist in paths.items():
            if (
                start == current
                and end not in visited
                and elevations[end] > elevations[current]
            ):
                visited.add(end)
                path.append(end)
                dfs_uphill(end, visited, path, total_dist + dist)
                path.pop()
                visited.remove(end)

    def dfs_downhill(
        current: int, visited: set, path: list[int], total_dist: int
    ) -> None:
        nonlocal shortest_path, shortest_distance

        if current == home:
            if total_dist < shortest_distance:
                shortest_distance = total_dist
                shortest_path = list(path)
            return

        for (start, end), dist in paths.items():
            if (
                start == current
                and end not in visited
                and elevations[end] < elevations[current]
            ):
                visited.add(end)
                path.append(end)
                dfs_downhill(end, visited, path, total_dist + dist)
                path.pop()
                visited.remove(end)

    home = 0
    shortest_path: list[int] = []
    shortest_distance: int = float("inf")

    visited: set = set([home])
    dfs_uphill(home, visited, [home], 0)

    if shortest_path:
        return shortest_path, shortest_distance
    else:
        return [], -1

Complexity

• ⏰ Time complexity: O(E.V), where E is number of edges, and V is number of vertices
  • In the worst case, the algorithm explores all possible paths from the home location. Given that there are V locations (vertices) and E paths (edges), the DFS explores each edge multiple times.
  • For each node, we examine all edges, leading to a complexity component of O(E).
• 🧺 Space complexity: O(V), for using recursion stack and for using visited set.