From dffde08c3fc0da933d597ccc907aa2e1186222db Mon Sep 17 00:00:00 2001
From: Brian Chu <brianmchu42@gmail.com>
Date: Sun, 9 Jan 2022 17:24:29 -0800
Subject: solution for day 24

---
 day24.fsx | 82 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 82 insertions(+)
 create mode 100644 day24.fsx

diff --git a/day24.fsx b/day24.fsx
new file mode 100644
index 0000000..47c76d2
--- /dev/null
+++ b/day24.fsx
@@ -0,0 +1,82 @@
+open System.IO
+open System.Collections.Generic
+
+let input = File.ReadAllLines "day24.txt"
+
+type Tile = Wall | Space | Number of int
+
+let width, height = input.[0].Length, input.Length
+let grid = Array2D.init width height (fun x y -> 
+  match input.[y].[x] with
+  | '#' -> Wall
+  | '.' -> Space
+  | num -> num |> string |> int |> Number)
+
+
+let findShortestPath start target =
+  let cache = new HashSet<int*int>([start])
+  [| (start, 0) |]
+  |> Seq.unfold (fun paths ->
+    paths
+    |> Seq.collect (fun ((x, y), moves) -> 
+      [ x-1, y; x+1, y; x, y-1; x, y+1 ]
+      |> Seq.filter (fun (x', y') -> grid.[x', y'] <> Wall && cache.Add(x', y'))
+      |> Seq.map (fun (x', y') -> (x', y'), moves+1))
+    |> Seq.toArray
+    |> function
+      | [||] -> None
+      | newStates -> Some(newStates, newStates)
+  )
+  |> Seq.collect id
+  |> Seq.pick (fun (pos, moves) -> if pos = target then Some moves else None)
+
+let numbers = 
+  [|
+    for y = 0 to height-1 do
+      for x = 0 to width-1 do
+        match grid.[x, y] with
+        | Number n -> yield n, (x, y)
+        | _ -> ()
+  |]
+  |> Map.ofArray
+
+let pairDistances =
+  [|
+    for src = 0 to 6 do
+      for dest = src + 1 to 7 do
+        let distance = findShortestPath numbers.[src] numbers.[dest]
+        yield (src, dest), distance
+        yield (dest, src), distance
+  |]
+  |> Map.ofArray
+
+let part1 = 
+  let rec traverse current (nodes : Set<int>) acc =
+    if nodes.Count = 0 then acc
+    else
+      nodes
+      |> Seq.map (fun next -> 
+        let left = nodes.Remove next
+        let dist = pairDistances.[current, next]
+
+        traverse next left (acc + dist))
+      |> Seq.min
+
+  traverse 0 (set [1..7]) 0
+
+let part2 = 
+  let rec traverse current (nodes : Set<int>) finalDest acc =
+    if nodes.Count = 0 then acc + pairDistances.[current, finalDest]
+    else
+      nodes
+      |> Seq.map (fun next -> 
+        let left = nodes.Remove next
+        let dist = pairDistances.[current, next]
+
+        traverse next left finalDest (acc + dist))
+      |> Seq.min
+      
+  traverse 0 (set [1..7]) 0 0
+
+part1 |> printfn "%d"
+part2 |> printfn "%d"
\ No newline at end of file
-- 
cgit 1.4.1-2-gfad0