GoLang solution for Daily Coding Problem #294

shortest_path.go

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