1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
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
|
