Skip to content

Instantly share code, notes, and snippets.

@ahmetb
Created September 30, 2021 19:04
Show Gist options
  • Save ahmetb/720a8fc3fbe4a9921965bc782fea3122 to your computer and use it in GitHub Desktop.
Save ahmetb/720a8fc3fbe4a9921965bc782fea3122 to your computer and use it in GitHub Desktop.
package main
import "fmt"
// [[1, 2, 7], [3, 6, 7]]
// given a src and dest stop, what is the minimum number of hops?
// src: 2 dst:3
// r0 8->3
// r1 7->8
// r2 1->2->7
// r3 3->6->7
// undirected graph search while keeeping cost min
// * loops
// * dfs/bfs
// 1--2--7*-8*-
// 3--6-/* |
// ^-----------
// rn -> rm N stops
// src: r1 r2 d: r3 .. r10
// [[1, 2, 7], [3, 6, 7]]
func f(routes [][]int, srcStop, dstStop int) int {
stopsToRoutes := make(map[int][]int)
for routeID , stops := range routes {
for _, stop := range stops {
stopsToRoutes[stop] = append(stopsToRoutes[stop], routeID)
}
}
connectingRoutes := make(map[int][]int)
for routeID, stops := range routes {
for _, stop := range stops {
routesOnThisStop := stops[stop]
for _, r := range routesOnThisStop {
if r != routeID {
connectingRoutes[routeID] = r
}
}
}
}
}
// min hops between srcRoutes and dstRoutes pairs
var minOut = math.MaxInt32
for _, srcRoute := range srcRoutes {
for _, dstRoute := range dstRoutes {
if srcRoute == dstRoute {
minOut = 0
break
}
minOut = min(minOut, minRouteHops(graph, srcRoute,dstRoute))
}
}
if minOut == math.MaxInt32 {
minOut = -1
}
return minOut
}
func min(a,b int)int{
if a<b{return a}
return b
}
func minRouteHops(graph make(map[int][]int), srcRoute, dstRoute int) int {
visited := make(map[int]bool)
return dfs(graph, dstRoute, srcRoute, visited, 0)
}
func dfs(graph make(map[int][]int), dst int, cur int, visited map[int]bool, hops int){
if cur == dst {
return hops
}
visited[cur]=true
defer visited[cur]=false
var minHop = math.MaxInt
for _, neighbor := range graph[cur] {
if visited[cur] {
continue
}
if gotHops := dfs(graph, dst, neighbor, visited, hops+1); gotHops != -1 {
minHop = min(minHop,gotHops)
}
}
return minHop
}
// stops --> []routes
// 3 -> r0, r3
// route --> set(route)
// r2 <> r1
// r1 <> r0
// r2 <> r3
// src: s2 dst: s3
// search src:r2 dst: r0
// search src:r2 dst: r3
// graph (src->dst) bfs
// 2 <--> 1 <--> 0
// ^
// v
// 3
func main() {
c1 := []int{[]int[1, 2, 7], []int[3, 6, 7]}
fmt.Println(f(c1,2,3))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment