gistfile1.ml

#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]