Daily Coding Problem #294: Smallest Weight Strictly Ascending Then Descending Path

Problem Definition

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.

Solution using BackTracking

To solve this problem we need to go through all possible valid paths and determine the minimum weight path.

It can be solved easily with Back Tracking using recursive method.

Solution Overview

• Start from the starting node which is 0.
• For each of the path that can be explored from current node, travel along that path if it is valid i.e. Elevation must be valid since we must travel strictly uphill and then downhill only. Anytime we encounter invalid node, we back track and follow different path. Also if node which has already been visited in given path is encountered we should back track since it will give cycle.
• If we can safely reach final destination node which is 0 again, we store the path summation in a list (OR update miniumum weight)
• After we have found a path, we need to back track again since there may be many possible paths and we need to find the optimal path.

Java Implementation

Following is implementation in Java. This prints lightest weight and the path. (GoLang version solution, below prints all valid paths with their weights.)

	/* File: ShortestPath294.java
	* Created: 2019-05-08
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2019 Hogwart Inc.
	*/
	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	//=================================================================================================
	public class ShortestPath294 {
	public static void main(String[] args) {
	Map<Integer, Integer> elevations = new HashMap<>();
	elevations.put(0, 5);
	elevations.put(1, 25);
	elevations.put(2, 15);
	elevations.put(3, 20);
	elevations.put(4, 10);
	int[][] weights = {
	{0, 1, 10},
	{0, 2, 8},
	{0, 3, 15},
	{1, 3, 12},
	{2, 4, 10},
	{3, 4, 5},
	{3, 0, 17},
	{4, 0, 10},
	{4, 2, 1}
	};
	findPath(elevations, weights);
	elevations.clear();
	elevations.put(0, 5);
	elevations.put(1, 15);
	elevations.put(2, 10);
	elevations.put(3, 25);
	elevations.put(4, 10);
	elevations.put(5, 20);
	elevations.put(6, 0);
	int[][] weights2 = {
	{0, 1, 3},
	{0, 2, 1},
	{1, 5, 5},
	{2, 4, 1},
	{2, 6, 1},
	{4, 0, 0},
	{4, 5, 1},
	{5, 0, 5},
	{5, 4, 1},
	{6, 0, 2},
	};
	findPath(elevations, weights2);
	} // main
	/**
	* Finds smallest weight path that ascends and then descends
	* @param elevations
	* @param weights
	*/
	public static void findPath(Map<Integer, Integer> elevations, int[][] weights) {
	Map<String, Integer> pathsWeight = new HashMap<>();
	Map<Integer, List<Integer>> neighbors = new HashMap<>();
	for(int[] path : weights) {
	pathsWeight.put(path[0] + "-" + path[1], path[2]);
	if(!neighbors.containsKey(path[0])) {
	neighbors.put(path[0], new ArrayList<>());
	}
	neighbors.get(path[0]).add(path[1]);
	}
	List<Integer> bestPath = new ArrayList<>();
	List<Integer> currentPath = new ArrayList<>();
	currentPath.add(0);
	int bestWeight = findPathHelper(elevations, pathsWeight, neighbors, new HashSet<Integer>(), false, 0, currentPath, 0, bestPath, Integer.MAX_VALUE);
	System.out.println(bestWeight);
	System.out.println(bestPath);
	} // findPath
	//---------------------------------------------------------------------------------------------
	/**
	* Helper method that recursively traverses all valid paths and identifies the lightest path.
	*
	* @param elevations node to elevation map
	* @param pathsWeight path to path weight map
	* @param neighbors node to neighbors map
	* @param visited visited nodes in a path
	* @param descending are we currently descending
	* @param current current node being explored
	* @param currentPath nodes in current path so far
	* @param currentPathSum current path sum so far
	* @param bestPath best path so far
	* @param bestWeight best weight so far
	* @return best weight along current node
	*/
	public static int findPathHelper(Map<Integer, Integer> elevations, Map<String, Integer> pathsWeight, Map<Integer, List<Integer>> neighbors,
	Set<Integer> visited, boolean descending, int current, List<Integer> currentPath, int currentPathSum, List<Integer> bestPath, int bestWeight) {
	int currentBestWeight = bestWeight; // multiple path can exist from a node. So we cannot return as soon as we find a path.
	// explore current node
	for(int neighbor : neighbors.get(current)) {
	String weightKey = current + "-" + neighbor;
	if(neighbor == 0) { // we are back to source i.e Destination
	if(elevations.get(neighbor) < elevations.get(current)) { // path should descend at end
	if(currentPathSum + pathsWeight.get(weightKey) < currentBestWeight) { // is the path best path than already found?
	bestPath.clear();
	bestPath.addAll(currentPath);
	bestPath.add(neighbor);
	currentBestWeight = currentPathSum + pathsWeight.get(weightKey);
	}
	}
	} else {
	boolean isPathValid = elevations.get(neighbor) != elevations.get(current); // Path should ascend or descend
	boolean expectDescend = elevations.get(neighbor) < elevations.get(current);
	isPathValid = isPathValid && (!descending || descending && expectDescend); // If we are ascending next can be either ascend or descend.
	// But if we are descending, it must not ascend again.
	if (isPathValid) {
	visited.add(neighbor);
	currentPath.add(neighbor);
	currentBestWeight = findPathHelper(elevations, pathsWeight, neighbors, visited, expectDescend, neighbor, currentPath, currentPathSum + pathsWeight.get(weightKey), bestPath, currentBestWeight);
	currentPath.remove(currentPath.size() - 1);
	visited.remove(neighbor);
	} else {
	// Path is not valid. IGNORE
	}
	}
	}
	return currentBestWeight;
	} // findPathHelper
	} // ShortestPath294

view raw ShortestPath294.java hosted with ❤ by GitHub

GoLang Implementation

Following is implementation in GoLang. This solution actually prints all valid paths with their path weight. It can be easily modified to return the minimum weight path.

	package main
	import "fmt"
	// TestShortestPath solves sample examples
	func TestShortestPath() {
	elevations := map[int]int{
	0: 5,
	1: 25,
	2: 15,
	3: 20,
	4: 10,
	}
	paths := [][3]int{
	{0, 1, 10},
	{0, 2, 8},
	{0, 3, 15},
	{1, 3, 12},
	{2, 4, 10},
	{3, 4, 5},
	{3, 0, 17},
	{4, 0, 10},
	{4, 2, 1},
	}
	findPath(elevations, paths)
	elevations = map[int]int{
	0: 5,
	1: 15,
	2: 10,
	3: 25,
	4: 10,
	5: 20,
	6: 0,
	}
	paths = [][3]int{
	{0, 1, 3},
	{0, 2, 1},
	{1, 5, 5},
	{2, 4, 1},
	{2, 6, 1},
	{4, 0, 0},
	{4, 5, 1},
	{5, 0, 5},
	{5, 4, 1},
	{6, 0, 2},
	}
	findPath(elevations, paths)
	} // TestShortestPath
	//-------------------------------------------------------------------------------------------------
	type path struct {
	weight int
	path []int
	}
	func (p *path) String() string {
	return fmt.Sprintf("Weight: %d Path: %v\n", p.weight, p.path)
	}
	//-------------------------------------------------------------------------------------------------
	// findPath initializes necessary data structures to call findPathHelper
	func findPath(elevations map[int]int, paths [][3]int) {
	neighborsMap := make(map[int]*[]int)
	weights := make(map[string]int)
	for _, path := range paths {
	neighbors, ok := neighborsMap[path[0]]
	if !ok {
	newNeighbors := make([]int, 0)
	neighbors = &newNeighbors
	neighborsMap[path[0]] = neighbors
	}
	*neighbors = append(*neighbors, path[1])
	weightKey := fmt.Sprintf("%d-%d", path[0], path[1])
	weights[weightKey] = path[2]
	}
	var resultPaths = make([]*path, 0)
	var currentPath = make([]int, 0, 1)
	currentPath = append(currentPath, 0) // 0 is starting node of path
	var visited = make(map[int]bool)
	findPathHelper(elevations, neighborsMap, weights, visited, &resultPaths, &currentPath, 0, 0, false)
	fmt.Println(resultPaths)
	} // findPath
	//-------------------------------------------------------------------------------------------------
	// findPathHelper recursively finds all the paths and their sum
	func findPathHelper(elevations map[int]int, neighbors map[int]*[]int, weights map[string]int, visited map[int]bool, paths *[]*path, currentPath *[]int, current int, pathSum int, descending bool) {
	for _, neighbor := range *neighbors[current] {
	weightKey := fmt.Sprintf("%d-%d", current, neighbor)
	if neighbor == 0 {
	if elevations[current] > elevations[neighbor] {
	cpath := make([]int, len(*currentPath), len(*currentPath)+1)
	copy(cpath, *currentPath)
	cpath = append(cpath, neighbor)
	*paths = append(*paths, &path{
	weight: pathSum + weights[weightKey],
	path: cpath})
	} else {
	// Path didn't descend. Path is not valid. Do nothing
	}
	} else { // THIS BLOCK HAS REAPEATED CODE BLOCK. CAN BE MERGED AS IN JAVA VERSION. BUT THIG MIGHT CLARIFY THE SOLUTION.
	if !descending {
	if elevations[current] < elevations[neighbor] {
	visited[neighbor] = true
	*currentPath = append(*currentPath, neighbor) // add neighbor to current path
	findPathHelper(elevations, neighbors, weights, visited, paths, currentPath, neighbor, pathSum+weights[weightKey], false)
	*currentPath = (*currentPath)[:len(*currentPath)-1] // remove neighbor from current path
	visited[neighbor] = false
	} else if elevations[current] > elevations[neighbor] {
	visited[neighbor] = true
	*currentPath = append(*currentPath, neighbor) // add neighbor to current path
	findPathHelper(elevations, neighbors, weights, visited, paths, currentPath, neighbor, pathSum+weights[weightKey], true)
	*currentPath = (*currentPath)[:len(*currentPath)-1] // remove neighbor from current path
	visited[neighbor] = false
	} else {
	// Path didn't strictly = ascend or descend. Path not valid. ignore this neighbor
	}
	} else { // descending
	if elevations[current] > elevations[neighbor] {
	visited[neighbor] = true
	*currentPath = append(*currentPath, neighbor) // add neighbor to current path
	findPathHelper(elevations, neighbors, weights, visited, paths, currentPath, neighbor, pathSum+weights[weightKey], true)
	*currentPath = (*currentPath)[:len(*currentPath)-1] // remove neighbor from current path
	visited[neighbor] = false
	} else {
	// Path didn't descend. Path is not valid. Ignore this neighbor
	}
	}
	}
	}
	} // findPathHelper

view raw shortest_path.go hosted with ❤ by GitHub

Complexity

This solves the problem by traversing every possible paths. So the theoretical time complexity is $O(2^n)$.

However since the question has restriction that the path has to strictly ascend and then descend, we are returning path as invalid as soon as we encounter invalid path. Because of this restriction, in practice the time complexity will be $O(n).$

Alternative Solution with Memoization

In the previous solution, we start from first node 0 and keep on exploring all possible paths all the way to destination. During the exploration we keep updating track of path sum for all paths and update the best path.

In this solution, we compute the best path and best path weight that can be attained from given node. We cache this result and use it later when we encounter the same node in other path.

This solution does not require to pass currentPath, currentPathSum, bestPath and bestWeight to findPathHelper()

Computation is done from the end. Idea is lightest tail path will be part of the solution path.

Following in implementation.

	/* File: ShortestPath294.java
	* Created: 2019-05-08
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2019 Hogwart Inc.
	*/
	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	//=================================================================================================
	/**
	* Daily coding problem #294
	*
	* Computes shortest path that starts from 0 and ends in 0 again, strictly ascends and then descends.
	*
	*/
	public class ShortestPath294 {
	public static void main(String[] args) {
	Map<Integer, Integer> elevations = new HashMap<>();
	elevations.put(0, 5);
	elevations.put(1, 25);
	elevations.put(2, 15);
	elevations.put(3, 20);
	elevations.put(4, 10);
	int[][] weights = {
	{0, 1, 10},
	{0, 2, 8},
	{0, 3, 15},
	{1, 3, 12},
	{2, 4, 10},
	{3, 4, 5},
	{3, 0, 17},
	{4, 0, 10},
	{4, 2, 1}
	};
	findPath(elevations, weights);
	elevations.clear();
	elevations.put(0, 5);
	elevations.put(1, 15);
	elevations.put(2, 10);
	elevations.put(3, 25);
	elevations.put(4, 10);
	elevations.put(5, 20);
	elevations.put(6, 0);
	int[][] weights2 = {
	{0, 1, 3},
	{0, 2, 1},
	{1, 5, 5},
	{2, 4, 1},
	{2, 6, 1},
	{4, 0, 0},
	{4, 5, 1},
	{5, 0, 5},
	{5, 4, 1},
	{6, 0, 2},
	};
	findPath(elevations, weights2);
	} // main
	/**
	* Finds smallest weight path that ascends and then descends
	* @param elevations
	* @param weights
	*/
	public static void findPath(Map<Integer, Integer> elevations, int[][] weights) {
	Map<String, Integer> pathsWeight = new HashMap<>();
	Map<Integer, List<Integer>> neighbors = new HashMap<>();
	for(int[] path : weights) {
	pathsWeight.put(path[0] + "-" + path[1], path[2]);
	if(!neighbors.containsKey(path[0])) {
	neighbors.put(path[0], new ArrayList<>());
	}
	neighbors.get(path[0]).add(path[1]);
	}
	Object[] best = findPathHelper(elevations, pathsWeight, neighbors, new HashSet<Integer>(), false, 0, new HashMap<>(), new HashMap<>());
	System.out.println(best[0]);
	System.out.println(best[1]);
	} // findPath
	//---------------------------------------------------------------------------------------------
	/**
	* Helper method that recursively traverses all valid paths and identifies the lightest path. It computes from the end and uses memoization.
	*
	* @param elevations node to elevation map
	* @param pathsWeight path to path weight map
	* @param neighbors node to neighbors map
	* @param visited visited nodes in a path
	* @param descending are we currently descending
	* @param current current node being explored
	* @param weightCache cache for weights holding best weight that can be achieved from a node
	* @param pathCache cache for paths holding best weight that can be achieved from a node
	* @return array of best weight and best path from current node
	*/
	public static Object[] findPathHelper(Map<Integer, Integer> elevations, Map<String, Integer> pathsWeight, Map<Integer, List<Integer>> neighbors,
	Set<Integer> visited, boolean descending, int current, Map<Integer, Integer> weightCache, Map<Integer, List<Integer>> pathCache) {
	if (weightCache.containsKey(current)) {
	return new Object[]{weightCache.get(current), pathCache.get(current)};
	}
	int bestWeightFromCurrent = Integer.MAX_VALUE;
	List<Integer> bestPathFromCurrent = new ArrayList<>();
	// explore current node
	for(int neighbor : neighbors.get(current)) {
	String weightKey = current + "-" + neighbor;
	if(neighbor == 0) { // we are back to source i.e Destination
	if(elevations.get(neighbor) < elevations.get(current)) { // path should descend at end
	if (bestWeightFromCurrent > pathsWeight.get(weightKey)) {
	bestWeightFromCurrent = pathsWeight.get(weightKey);
	bestPathFromCurrent.add(neighbor);
	}
	}
	} else {
	boolean isPathValid = elevations.get(neighbor) != elevations.get(current); // Path should ascend or descend
	boolean expectDescend = elevations.get(neighbor) < elevations.get(current);
	isPathValid = isPathValid && (!descending || descending && expectDescend); // If we are ascending next can be either ascend or descend.
	// But if we are descending, it must not ascend again.
	if (isPathValid) {
	visited.add(neighbor);
	Object[] pathDetails = findPathHelper(elevations, pathsWeight, neighbors, visited, expectDescend, neighbor, weightCache, pathCache);
	int pathWeightFromNeighbor = (int) pathDetails[0];
	if(pathWeightFromNeighbor != Integer.MAX_VALUE) {
	int weightWithNeighbor = pathsWeight.get(weightKey) + pathWeightFromNeighbor;
	if (bestWeightFromCurrent > weightWithNeighbor) {
	bestWeightFromCurrent = weightWithNeighbor;
	bestPathFromCurrent.clear();
	bestPathFromCurrent.addAll((List)pathDetails[1]);
	}
	}
	visited.remove(neighbor);
	} else {
	// Path is not valid. IGNORE
	}
	}
	}
	weightCache.put(current, bestWeightFromCurrent);
	bestPathFromCurrent.add(0, current);
	pathCache.put(current, bestPathFromCurrent);
	return new Object[]{bestWeightFromCurrent, bestPathFromCurrent};
	} // findPathHelper
	} // ShortestPath294

view raw ShortestPath294.java hosted with ❤ by GitHub

Complexity

The time complexity will be $O(n).$

---

---

---