-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day08.fs
150 lines (109 loc) · 3.69 KB
/
Day08.fs
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
module aoc23.Day08
open System.Collections
module Parser =
open FSharp.Text.RegexProvider
type DirectionsRegex = Regex< @"[LR]+" >
type NodeRegex = Regex< @"(?<a>[A-Z0-9]+) = \((?<b>[A-Z0-9]+), (?<c>[A-Z0-9]+)\)" >
let directions text =
DirectionsRegex().Match(text).Value |> Array.ofSeq
let nodes text =
NodeRegex().TypedMatches(text)
|> Seq.map (fun m -> (m.a.Value, m.b.Value, m.c.Value))
let part1 text =
let infiniteDirections =
let directions = text |> Parser.directions
Seq.initInfinite (fun i -> directions[i % directions.Length])
let nodeMap =
text |> Parser.nodes |> Seq.map (fun (a, b, c) -> (a, (b, c))) |> Map.ofSeq
let nextNodeF =
function
| 'L' -> fst
| 'R' -> snd
| d -> failwith $"unknown direction {d}"
let rec findZZZ i (directions: Generic.IEnumerator<char>) =
function
| "ZZZ" -> i
| node ->
directions.MoveNext() |> ignore
let nextNode = nodeMap[node] |> (directions.Current |> nextNodeF)
findZZZ (i + 1) directions nextNode
findZZZ 0 (infiniteDirections.GetEnumerator()) "AAA"
type BreakCondition =
| BreakCondition_ZZZ
| BreakCondition_xxZ
type Solver(text) =
let directions = text |> Parser.directions
let directionAt (i: int64) =
directions[(i % directions.LongLength) |> int]
let nodeMap =
text |> Parser.nodes |> Seq.map (fun (a, b, c) -> (a, (b, c))) |> Map.ofSeq
let sortedNodes =
nodeMap
|> Map.keys
|> Seq.sortByDescending (fun node -> node[^0])
|> Seq.toArray
// give each node a number, put **Z to the beginning and **A to the end
let nodeIdMap = sortedNodes |> Seq.indexed |> Seq.map TupleEx.swap |> Map.ofSeq
let zCount =
nodeMap |> Map.keys |> Seq.filter (fun node -> node[^0] = 'Z') |> Seq.length
let left, right =
(fst, snd)
|> TupleEx.map (fun chooser ->
sortedNodes
|> Array.map (fun node ->
let nextNode = nodeMap[node] |> chooser
nodeIdMap[nextNode]))
member _.indexOf breakCondition firstNode =
let mutable state = nodeIdMap |> Map.find firstNode
let mutable i = 0
let loopWhile =
match breakCondition with
| BreakCondition_ZZZ ->
let zzzId = nodeIdMap["ZZZ"]
fun () -> state <> zzzId
| BreakCondition_xxZ -> fun () -> state > zCount - 1
while loopWhile () do
let lookup = if (directionAt i = 'L') then left else right
state <- lookup[state]
i <- i + 1
i
member _.aNodes = sortedNodes |> Array.filter (fun node -> node[^0] = 'A')
let part1_fast text =
let solver = Solver text
solver.indexOf BreakCondition_ZZZ "AAA"
let part2 text =
let solver = Solver text
let zNodesIterations =
solver.aNodes |> Array.map (solver.indexOf BreakCondition_xxZ)
zNodesIterations
|> Array.map int64
|> MathNet.Numerics.Euclid.LeastCommonMultiple
let run = runReadAllText part1_fast part2
module Tests =
open Xunit
open Swensen.Unquote
let example =
"""LLR
AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)
"""
let example2 =
"""LR
11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)
"""
[<Fact>]
let ``example part 1`` () = part1 example =! 6
[<Fact>]
let ``example part 1 fast`` () = part1_fast example =! 6
[<Fact>]
let ``example part 2`` () = part2 example =! 6
[<Fact>]
let ``example2 part 2`` () = part2 example2 =! 6