Advent of Code 2024, Day 5
Part One
There is a list of printing updates that are lists of page numbers indicating the order in which the pages must be printed. There is also a list of page ordering rules of the form X|Y, which means that page number X must be printed before page number Y, but it does not need to be immediately before Y. Puzzle input is a list of rules followed by a list of updates.
My first 5 rules and first 5 updates are presented below. There was a total of 1176 rules and 190 updates.
32|86
27|29
27|46
29|68
29|74
79,64,35,74,22,94,19
35,31,68,42,96,74,47,44,18,84,21,22,45,19,95,65,27
94,76,47,44,18,87,86,95,84,35,74,73,68,19,42,15,65
52,46,12,61,51,29,83,59,23,13,39,79,64,86,35,73,31,69,68,15,42,87,96
19,69,92,18,27,74,44,88,21,68,45,47,22,42,54,76,65,84,15,94,31
They ask you to determine if the updates are in the right order, i.e., they satisfy all the applicable rules. If a rule’s numbers don’t appear in a given update, that rule is not applicable to the update, so the rule is ignored for that update. Once you identify the correctly-ordered updates, you must find their middle page number and sum them.
First, reading the input file was very easy. I used the Table format with | and , as field separators. Since there is an empty line between rules and updates, I use that as a criterion to separate the sections. Note that I read the updates from the end of file in reverse order.
input = Import["input.txt", "Table", "FieldSeparators" -> {"|", ","}]
rules = TakeWhile[input, Length[#] > 0&]
updates = TakeWhile[Reverse[input], Length[#] > 0&]
Then, to determine if an update is correctly ordered or not, I coded the following functions. They check if the rule numbers are present in the update or not, later they check the page positions in the update.
satisfyRuleQ[update_, {x_, y_}] :=
With[{getPosition = First[Flatten[Position[update, #]]]&},
If[SubsetQ[update, {x, y}],
getPosition[x] < getPosition[y]
,
True
]
]
rightOrderQ[update_, rules_] :=
rules // AllTrue[satisfyRuleQ[update, #]&]
Finally, the sum of the middle numbers of correctly-ordered updates is simply:
sumMiddleNumbers =
updates //
Map[
If[rightOrderQ[#, rules],
#[[Floor[Length[#] / 2] + 1]]
,
0
]&
] //
Total
This results in 4637.
As a commentary, using the built-in Total function, instead of a helper iterative function (or recursion) as I did for Day 4, is much more expressive. In Day 4 I was foolishly concerned about machine efficiency. One does not need to be concerned about such things unless it is really necessary, especially if optimizing the code compromises its readability. Now I realize that I could have written the XMAS and X-MAS summations similarly as I did in the code above. I could have used the Table function to generate a grid with cell counts, then applied Total with LevelSpec argument set to 2.
Part Two
The second part requires you to actually order the updates that were not correctly ordered. The expected result is the sum of the middle numbers of these now-correct updates.
I defined a function that swaps update elements that don’t meet the given rule. I also coded a function that applies the previous function recursively for all rules. This recursive application is obtained with Fold. For example, Fold[f, x, {a, b, c}] computes f[f[f[x, a], b], c].
applySingleRule[update_, {x_, y_}] :=
If[satisfyRuleQ[update, {x, y}],
update
,
update //
Map[
Switch[#,
x, y
,
y, x
,
_, #
]&
]
]
applyAllRules[update_, rules_] :=
Fold[applySingleRule, update, rules]
The mere evaluation of applyAllRules, however, does not enforce the rules. My code worked seamlessly with the given example, but my input was much more complex. I was stuck at this point for a couple of days until someone’s comment on the internet shed light on my issue. I could run applyAllRules recursively until all rules were met for a given update. Eventually, I came up with the following function:
enforceRules[update_, rules_] :=
NestWhile[
applyAllRules[#, rules]&,
update,
!rightOrderQ[#, rules]&
]
As the reader may suspect, the function above is slow. One may use imperative programming to code a more machine efficient solution, but my journey in Wolfram Language is not about writing efficient code (which I learned back in the day with Fortran and Julia). With Wolfram Language I want to practice functional programming and writing more elegant, declarative code. See, again, what I did on Day 4…
The sum of the middle numbers is:
sumOrderedMiddleNumbers =
updates //
Map[
If[rightOrderQ[#, rules],
0
,
enforceRules[#, rules][[Floor[Length[#] / 2] + 1]]
]&
] //
Total
This yields 6370.