Submit part 1 of day 16

2 files changed, 121 insertions, 0 deletions

diff --git a/aoc-2022-dotnet/Day16/Day16.fsproj b/aoc-2022-dotnet/Day16/Day16.fsproj
new file mode 100644
index 0000000..358ef88
--- /dev/null
+++ b/aoc-2022-dotnet/Day16/Day16.fsproj
@@ -0,0 +1,26 @@
+<Project Sdk="Microsoft.NET.Sdk">
+
+  <PropertyGroup>
+    <OutputType>Exe</OutputType>
+    <TargetFramework>net7.0</TargetFramework>
+  </PropertyGroup>
+
+  <ItemGroup>
+    <Content Include="test.txt">
+      <CopyToOutputDirectory>Always</CopyToOutputDirectory>
+    </Content>
+    <Content Include="input.txt">
+      <CopyToOutputDirectory>Always</CopyToOutputDirectory>
+    </Content>
+    <Compile Include="Program.fs" />
+  </ItemGroup>
+
+  <ItemGroup>
+    <PackageReference Include="FParsec" Version="1.1.1" />
+  </ItemGroup>
+
+  <ItemGroup>
+    <ProjectReference Include="..\Common\Common.fsproj" />
+  </ItemGroup>
+
+</Project>
diff --git a/aoc-2022-dotnet/Day16/Program.fs b/aoc-2022-dotnet/Day16/Program.fs
new file mode 100644
index 0000000..a2c4b2e
--- /dev/null
+++ b/aoc-2022-dotnet/Day16/Program.fs
@@ -0,0 +1,95 @@
+module Day16
+
+open System.IO
+open FParsec
+open Common
+
+type ValveName = string
+
+type Valve =
+    { Flow: int
+      Neighbours: ValveName list }
+
+let parseValve =
+    let pSingleOrMulti str = pstring str .>>. opt (pchar 's')
+    let pValveName: Parser<ValveName, _> = anyString 2
+
+    let pValve =
+        pstring "Valve " >>. pValveName
+        .>> pstring " has flow rate="
+        .>>. pint32
+        .>> pstring "; "
+        .>> pSingleOrMulti "tunnel"
+        .>> pchar ' '
+        .>> pSingleOrMulti "lead"
+        .>> pstring " to "
+        .>> pSingleOrMulti "valve"
+        .>> pchar ' '
+        .>>. sepBy1 pValveName (pstring ", ")
+        |>> (fun ((name, flow), neighbours) -> (name, { Flow = flow; Neighbours = neighbours }))
+
+    Util.parse pValve
+
+let distancesFrom valves start =
+    let neighbours v = (Map.find v valves).Neighbours
+
+    let rec bfsExplore visited acc =
+        function
+        | (v, depth) :: queue ->
+            bfsExplore
+                (Set.add v visited)
+                (((start, v), depth) :: acc)
+                (queue
+                 @ (neighbours v
+                    |> List.filter (Util.notIn visited)
+                    |> List.map (fun n -> (n, depth + 1))))
+        | [] -> acc
+
+    bfsExplore Set.empty [] [ (start, 0) ]
+
+let buildGraph input =
+    let valves = input |> Seq.map parseValve |> Map.ofSeq
+
+    let flows =
+        valves
+        |> Map.map (fun _ v -> v.Flow)
+        |> Map.filter (fun v f -> f > 0 || v = "AA")
+
+    let distances =
+        valves
+        |> Map.keys
+        |> Seq.collect (distancesFrom valves)
+        |> Map.ofSeq
+        |> Map.filter (fun (f, t) _ ->
+            f <> t
+            && Map.containsKey f flows
+            && Map.containsKey t flows)
+
+    flows, distances
+
+let solution input =
+    let (flows, distances) = buildGraph input
+
+    let rec findMaxPressure current remainingTime closedValves =
+        let closedValves = closedValves |> Set.remove current
+
+        closedValves
+        |> Seq.choose (fun t ->
+            let remainingTime = remainingTime - (distances[(current, t)] + 1)
+
+            if remainingTime > 0 then
+                Some(
+                    flows[t] * remainingTime
+                    + findMaxPressure t remainingTime closedValves
+                )
+            else
+                None)
+        |> Util.maxOrZero
+
+    findMaxPressure "AA" 30 (flows |> Map.keys |> Set.ofSeq)
+
+let test = File.ReadLines("test.txt")
+assert (solution test = 1651)
+
+let input = File.ReadLines("input.txt")
+printfn "%d" <| solution input