Finish day 16

4 files changed, 82 insertions, 68 deletions

diff --git a/README.md b/README.md
index 39d8232..89970d1 100644
--- a/README.md
+++ b/README.md
@@ -10,7 +10,7 @@ Repository storing my solutions to Advent of Code. See other people's solutions
 
 ### [2022](aoc-2022-dotnet)
 ![F#](https://img.shields.io/badge/F%23-grey?logo=.NET)
-![Stars](https://img.shields.io/badge/🌟%20stars-31/50-orange)
+![Stars](https://img.shields.io/badge/🌟%20stars-32/50-orange)
 
 [awesome]: https://github.com/Bogdanp/awesome-advent-of-code
 [aoc]: https://adventofcode.com
diff --git a/aoc-2022-dotnet/Common/Util.fs b/aoc-2022-dotnet/Common/Util.fs
index 436e9a0..acf89af 100644
--- a/aoc-2022-dotnet/Common/Util.fs
+++ b/aoc-2022-dotnet/Common/Util.fs
@@ -42,11 +42,9 @@ module Util =
 
     let notIn set element = not <| Set.contains element set
 
-    let maxOrZero seq =
-        if Seq.isEmpty seq then
-            0
-        else
-            Seq.max seq
+    let updateMax key newValue map =
+        map
+        |> Map.add key (max newValue (map |> Map.tryFind key |> Option.defaultValue 0))
 
     let rec insertSorted x =
         function
diff --git a/aoc-2022-dotnet/Day16/Program.fs b/aoc-2022-dotnet/Day16/Program.fs
index a2c4b2e..87b0ffa 100644
--- a/aoc-2022-dotnet/Day16/Program.fs
+++ b/aoc-2022-dotnet/Day16/Program.fs
@@ -10,86 +10,102 @@ 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 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 node = (Map.find node 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 valveMap = input |> Seq.map parseValve |> Map.ofSeq
 
     let flows =
-        valves
+        valveMap
         |> Map.map (fun _ v -> v.Flow)
         |> Map.filter (fun v f -> f > 0 || v = "AA")
 
     let distances =
-        valves
+        valveMap
         |> Map.keys
-        |> Seq.collect (distancesFrom valves)
+        |> Seq.collect (distancesFrom valveMap)
         |> Map.ofSeq
         |> Map.filter (fun (f, t) _ ->
             f <> t
             && Map.containsKey f flows
             && Map.containsKey t flows)
 
-    flows, distances
+    let valves = flows |> Map.keys |> Set.ofSeq
+
+    valves, flows, distances
 
 let solution input =
-    let (flows, distances) = buildGraph input
+    let (valves, flows, distances) = buildGraph input
+
+    let findBestFlow time =
+        let rec explore current time visited flow results =
+            if time <= 0 then
+                results
+            else
+                let visited' = visited |> Set.add current
+                let results' = results |> Util.updateMax visited' flow
 
-    let rec findMaxPressure current remainingTime closedValves =
-        let closedValves = closedValves |> Set.remove current
+                Seq.fold
+                    (fun acc next ->
+                        let time' = time - (distances[(current, next)] + 1)
+                        let flow' = flow + flows[next] * time'
+                        explore next time' visited' flow' acc)
+                    results'
+                    (valves - visited')
 
-        closedValves
-        |> Seq.choose (fun t ->
-            let remainingTime = remainingTime - (distances[(current, t)] + 1)
+        explore "AA" time Set.empty 0 Map.empty
 
-            if remainingTime > 0 then
-                Some(
-                    flows[t] * remainingTime
-                    + findMaxPressure t remainingTime closedValves
-                )
-            else
-                None)
-        |> Util.maxOrZero
+    let part1 = findBestFlow 30 |> Map.values |> Seq.max
+    let paths = findBestFlow 26
+
+    let part2 =
+        Seq.max
+        <| seq {
+            for selfPath in paths do
+                for elephantPath in paths do
+                    if Set.intersect selfPath.Key elephantPath.Key = Set.singleton "AA" then
+                        yield selfPath.Value + elephantPath.Value
+        }
 
-    findMaxPressure "AA" 30 (flows |> Map.keys |> Set.ofSeq)
+    part1, part2
 
 let test = File.ReadLines("test.txt")
-assert (solution test = 1651)
+assert (solution test = (1651, 1707))
 
 let input = File.ReadLines("input.txt")
-printfn "%d" <| solution input
+printfn "%A" <| solution input
diff --git a/aoc-2022-dotnet/README.md b/aoc-2022-dotnet/README.md
index 4b49309..506101c 100644
--- a/aoc-2022-dotnet/README.md
+++ b/aoc-2022-dotnet/README.md
@@ -1,6 +1,6 @@
 # Advent of Code 2022 in F#
 ![F#](https://img.shields.io/badge/F%23-grey?logo=.NET)
-![Stars](https://img.shields.io/badge/🌟%20stars-31/50-orange)
+![Stars](https://img.shields.io/badge/🌟%20stars-32/50-orange)
 
 |  Day   | Problem Name                                                    | Part 1 | Part 2 | Practiced Concepts                                   |
 | :----: | --------------------------------------------------------------- | :----: | :----: | ---------------------------------------------------- |
@@ -19,8 +19,8 @@
 | **13** | [Distress Signal](https://adventofcode.com/2022/day/13)         | :star: | :star: | `IComparable`, ADTs, patterns, FParsec               |
 | **14** | [Regolith Reservoir](https://adventofcode.com/2022/day/14)      | :star: | :star: | `Seq.unfold`, `Seq.pairwise`, functional DFS         |
 | **15** | [Beacon Exclusion Zone](https://adventofcode.com/2022/day/15)   | :star: | :star: | ranges, mahattan distance, parallel computing        |
-| **16** | [Proboscidea Volcanium](https://adventofcode.com/2022/day/16)   | :star: |        |                                                      |
-| **17** | ???                                                             |        |        |                                                      |
+| **16** | [Proboscidea Volcanium](https://adventofcode.com/2022/day/16)   | :star: | :star: | graphs, dynamic programming, `Seq`                   |
+| **17** | [Pyroclastic Flow](https://adventofcode.com/2022/day/17)        |        |        |                                                      |
 | **18** | ???                                                             |        |        |                                                      |
 | **19** | ???                                                             |        |        |                                                      |
 | **20** | ???                                                             |        |        |                                                      |