blob: 02e028cec6eac01b83077a45cb0419b0b1caf473 (
plain)
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
|
module Day14
open System.IO
open FParsec
open Common
let sandSpawnPos = Vec2(500, 0)
let sandMoveOffsets =
[ Vec2.down
Vec2.downLeft
Vec2.downRight ]
let notIn set element = not <| Set.contains element set
let buildCaveScan =
let parsePath =
let py = pint32 |>> (~-) // mirror Y coordinate
let ppoint = pint32 .>> (pchar ',') .>>. py |>> Vec2
let ppath = sepBy ppoint (pstring " -> ")
Util.parse ppath
let pathToPositions =
Seq.pairwise
>> Seq.collect Vec2.lineBetween
>> Set
Seq.map (parsePath >> pathToPositions)
>> Seq.reduce (+)
let solution1 input =
let initialCaveScan = buildCaveScan input
let voidY = initialCaveScan |> Seq.map Vec2.y |> Seq.min
let settleNewUnit caveScan =
let rec fall pos =
if Vec2.y pos <= voidY then
None
else
sandMoveOffsets
|> Seq.map ((+) pos)
|> Seq.tryFind (notIn caveScan)
|> function
| Some (nextPos) -> fall nextPos
| None -> Some(pos)
caveScan
|> match fall sandSpawnPos with
| Some (settledPos) -> Set.add settledPos
| None -> id
initialCaveScan
|> Seq.unfold (fun caveScan -> Some(caveScan, settleNewUnit caveScan))
|> Seq.pairwise
|> Seq.takeWhile (fun (a, b) -> a <> b)
|> Seq.length
let solution2 input =
let caveScan = buildCaveScan input
let floorY = caveScan |> Seq.map Vec2.y |> Seq.min |> (+) -2
let neighbours pos =
sandMoveOffsets
|> List.map ((+) pos)
|> List.filter (fun pos -> notIn caveScan pos && Vec2.y pos <> floorY)
let rec dfs stack visited =
match stack with
| h :: t -> dfs (List.filter (notIn visited) (neighbours h) @ t) (Set.add h visited)
| [] -> Set.count visited
dfs [ sandSpawnPos ] Set.empty
let test = File.ReadLines("test.txt")
assert (solution1 test = 24)
assert (solution2 test = 93)
let input = File.ReadLines("input.txt")
printfn "%d" <| solution1 input
printfn "%d" <| solution2 input
|
