Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#light
[<AutoOpen>]
module Operators =
let (||>) (x, y) f = f x y
module Map =
let transposeCombine m =
(m, m) ||> Map.fold_left (fun acc k1 m' ->
(acc, m') ||> Map.fold_left (fun acc' k2 v ->
acc'
|> Map.add k2 (Map.add k1 v (defaultArg (acc' |> Map.tryfind k2) Map.empty))
))
type City =
| Boise | LosAngeles | NewYork | Seattle
| StLouis | Phoenix | Boston | Chicago
| Denver
let distanceBetweenCities =
Map.of_list
[
(Boise, Map.of_list [(Seattle, 496);(Denver, 830);(Chicago, 1702)]);
(Seattle, Map.of_list [(LosAngeles, 1141);(Denver, 1321)]);
(LosAngeles, Map.of_list [(Denver, 1022);(Phoenix, 371)]);
(Phoenix, Map.of_list [(Denver, 809);(StLouis, 1504)]);
(Denver, Map.of_list [(StLouis, 588);(Chicago, 1009)]);
(Chicago, Map.of_list [(NewYork, 811);(Boston, 986)]);
(StLouis, Map.of_list [(Chicago, 300)]);
(Boston, Map.of_list [(StLouis, 986)]);
(NewYork, Map.of_list [(Boston, 211)])
]
|> Map.transposeCombine
let shortestPathBetween startCity endCity =
let rec searchForShortestPath currentCity distanceSoFar citiesVisitedSoFar accMap =
let visitDestinations m =
(m, distanceBetweenCities.[currentCity])
||> Map.fold_left
(fun acc city distance ->
searchForShortestPath city (distance + distanceSoFar) (citiesVisitedSoFar @ [city]) acc)
match Map.tryfind currentCity accMap with
| None -> accMap |> Map.add currentCity (distanceSoFar, citiesVisitedSoFar) |> visitDestinations
| Some x ->
let (shortestKnownPath, _) = x
if distanceSoFar < shortestKnownPath then
accMap |> Map.add currentCity (distanceSoFar, citiesVisitedSoFar) |> visitDestinations
else accMap
let shortestPaths = searchForShortestPath startCity 0 [] Map.empty
shortestPaths.[endCity]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment