Created
May 9, 2019 16:33
-
-
Save leosabbir/78b9d5088beaf25100e179d91f9e36c0 to your computer and use it in GitHub Desktop.
daily coding problem 294 alternative solution using memoization
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment