From 9dbfa20954bcc8f43d0440d68d5ddf221224887d Mon Sep 17 00:00:00 2001
From: Brian Chu <brianmchu42@gmail.com>
Date: Fri, 23 Dec 2022 21:51:18 -0800
Subject: solution for day 12

---
 AoC2022.fsproj     |  1 +
 Program.fs         |  2 ++
 solutions/day12.fs | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 51 insertions(+)
 create mode 100644 solutions/day12.fs

diff --git a/AoC2022.fsproj b/AoC2022.fsproj
index 13269ee..834144a 100644
--- a/AoC2022.fsproj
+++ b/AoC2022.fsproj
@@ -8,6 +8,7 @@
     <Compile Include="Program.fs" />
   </ItemGroup>
   <ItemGroup>
+    <PackageReference Include="astar-search" Version="1.0.2" />
     <PackageReference Include="FSharpPlus" Version="1.3.2" />
     <PackageReference Update="FSharp.Core" Version="6.0.6" />
   </ItemGroup>
diff --git a/Program.fs b/Program.fs
index 2b9fee8..f7c7db5 100644
--- a/Program.fs
+++ b/Program.fs
@@ -30,5 +30,7 @@ match (day, part) with
 | (10, 2) -> printf $"{Day10.part2 ()}\n"
 | (11, 1) -> printf $"{Day11.part1 ()}\n"
 | (11, 2) -> printf $"{Day11.part2 ()}\n"
+| (12, 1) -> printf $"{Day12.part1 ()}\n"
+| (12, 2) -> printf $"{Day12.part2 ()}\n"
 | (x, y) when (1 <= x && x <= 25) && (y = 1 || y = 2)  -> raise (NotImplemented("not implemented yet"))
 | _ -> raise (NotImplemented("invalid values"))
\ No newline at end of file
diff --git a/solutions/day12.fs b/solutions/day12.fs
new file mode 100644
index 0000000..d37d08a
--- /dev/null
+++ b/solutions/day12.fs
@@ -0,0 +1,48 @@
+module Solutions.Day12
+open System.IO
+open AStar
+
+let input = File.ReadAllLines("inputs/day12.txt") |> Array.map Array.ofSeq
+
+let findPoint ch =
+    let row = Array.findIndex (Array.contains ch) input
+    let col = Array.findIndex (fun x -> x = ch) input[row]
+    (row, col)
+
+let startCoord, endCoord = findPoint 'S', findPoint 'E'
+input[fst startCoord][snd startCoord] <- 'a'
+input[fst endCoord][snd endCoord] <- 'z'
+
+let height, width = input.Length, input[0].Length
+
+let neighbors (row, col) =
+    [|(row-1, col); (row+1, col); (row, col-1); (row, col+1)|]
+    |> Seq.filter (fun (nRow, nCol) -> nRow >= 0 && 
+                                       nRow < height && 
+                                       nCol >= 0 && 
+                                       nCol < width &&
+                                       input[nRow][nCol] <= input[row][col] + char 1)
+
+let gScore _ _ = 1.0
+
+let fScore (x, y) (dx, dy) =
+    sqrt ((float dx - float x) ** 2.0 + (float dy - float y) ** 2.0)
+
+let getPathLength start finish =
+    match search start finish {neighbours = neighbors; gCost = gScore; fCost = fScore; maxIterations = None} with
+    | Some path -> Seq.length path - 1
+    | None -> -1
+
+let part1 () =
+    getPathLength startCoord endCoord    
+
+let part2 () = 
+    seq {
+        for row in 0 .. height - 1 do
+        for col in 0 .. width - 1 do
+        if input[row][col] = 'a' then 
+            getPathLength (row, col) endCoord
+    }
+    |> Seq.filter (fun x -> x > 0)
+    |> Seq.sort
+    |> Seq.head
-- 
cgit 1.4.1-2-gfad0