Solving https://github.com/trustbit/exercises/blob/master/transport-tycoon_21.md with Go

shortest-route-golang

package main

import (
	"bufio"
	"fmt"
	"os"
	"reflect"
	"strconv"
	"strings"
)

type Connection struct {
	Start    string
	Finish   string
	Distance uint16
}

type Waypoint struct {
	Location      string
	Route         []string
	TotalDistance uint16
}

func loadConnections(path string) ([]Connection, error) {
	readFile, err := os.Open(path)
	if err != nil {
		fmt.Println(err)
	}
	defer readFile.Close()
	fileScanner := bufio.NewScanner(readFile)
	fileScanner.Split(bufio.ScanLines)
	var connections []Connection
	// skip first row
	fileScanner.Scan()
	for fileScanner.Scan() {
		row := strings.Split(fileScanner.Text(), ",")
		distance, err := strconv.Atoi(row[2])
		if err != nil {
			return nil, err
		} else {
			items := []Connection{
				{Start: row[0], Finish: row[1], Distance: uint16(distance)},
				{Start: row[1], Finish: row[0], Distance: uint16(distance)},
			}
			connections = append(connections, items...)
		}
	}
	return connections, nil
}

func exists[T any](items []T, predicate func(T) bool) bool {
	for _, item := range items {
		if predicate(item) {
			return true
		}
	}
	return false
}

func filter[T any](items []T, predicate func(T) bool) []T {
	var output []T
	for _, item := range items {
		if predicate(item) {
			output = append(output, item)
		}
	}
	return output
}

func partition[T any](items []T, predicate func(T) bool) (matched []T, unmatched []T) {
	for _, item := range items {
		if predicate(item) {
			matched = append(matched, item)
		} else {
			unmatched = append(unmatched, item)
		}
	}
	return matched, unmatched
}

func (wp Waypoint) getUnvisited(possible []Connection) []Waypoint {
	var unvisited []Waypoint
	for _, cn := range possible {
		if !exists(wp.Route, func(v string) bool {
			return v == cn.Finish
		}) {
			newWp := Waypoint{Location: cn.Finish, Route: append(wp.Route, cn.Start), TotalDistance: wp.TotalDistance + cn.Distance}
			unvisited = append(unvisited, newWp)
		}
	}
	return unvisited
}

func getCurrentShortest(current Waypoint, candidates []Waypoint) Waypoint {
	candidate := current
	for _, wp := range candidates {
		if reflect.DeepEqual(candidate, Waypoint{}) || wp.TotalDistance < candidate.TotalDistance {
			candidate = wp
		}
	}
	return candidate
}

func findShortestRoute(start string, finish string, connections []Connection) Waypoint {
	var shortest Waypoint
	destinations := make(map[string][]Connection)
	for _, item := range connections {
		destinations[item.Start] = append(destinations[item.Start], item)
	}
	waypoints := []Waypoint{{Location: start, Route: []string{}, TotalDistance: 0}}
	for {
		if len(waypoints) == 0 {
			return shortest
		}
		var candidates []Waypoint
		for _, wp := range waypoints {
			unvisited := wp.getUnvisited(destinations[wp.Location])
			finished, possible := partition(unvisited, func(wp Waypoint) bool {
				return wp.Location == finish
			})
			shortest = getCurrentShortest(shortest, finished)
			possible = filter(possible, func(wp Waypoint) bool {
				return reflect.DeepEqual(shortest, Waypoint{}) || wp.TotalDistance < shortest.TotalDistance
			})
			candidates = append(candidates, possible...)
		}
		waypoints = candidates
	}
}

func getShortestRoute(filePath string, start string, finish string) {
	connections, err := loadConnections(filePath)
	if err != nil {
		fmt.Printf("Error loading connections: %q", err)
		os.Exit(1)
	}
	shortest := findShortestRoute(start, finish, connections)
	fmt.Printf("%q, %d", append(shortest.Route, shortest.Location), shortest.TotalDistance)
}

func main() {
	filePath := "data.csv"
	start := "Cogburg"
	finish := "Leverstorm"
	// filePath := os.Args[1]
	// start := os.Args[2]
	// finish := os.Args[3]
	getShortestRoute(filePath, start, finish)
}

// go run main.go
// go run main.go data.csv Cogburg Leverstorm

Solving https://github.com/trustbit/exercises/blob/master/transport-tycoon_21.md with Go