Every December since 2015, software engineer and puzzle enthusiast Eric Wastl has created an Advent Calender of code challenges called Advent of Code. These puzzles can be solved in any programming language, since you are only required to submit a string or integer solution, and tend to increase in difficulty over the course of the 25 days. Each puzzle has two parts each using the same input (which is different for each user), the second part being revealed only after the first part is solved.
I started participating in this puzzle challenge in 2021 and I like to solve them using Maple right when they are unlocked at 12am EST each day. I post my my solutions to my github as Maple worksheets, and (usually) later as cleaned up Maple text files: https://github.com/johnpmay/AdventOfCode2024
I typically work in a Maple worksheet since I find the worksheet interface ideal to quickly play with an evolving piece of code to solve a puzzle (it is kind of a race if you want it to be, Advent of Code tells you your place every day and gives you "points" if you are one of the first 100). Also I find the nature of the Maple language and its variety of libraries pretty ideal for approaching these problems.
Today, I am writing about this because 2025 Day 5 was a cool puzzle that really asked to be analyzed further in Maple. (Note, if you are participating in Advent of Code and haven't solved Day 5, there are heavy spoilers ahead).
Once you decypher the silly story about the elves, the problem comes down to a set of pairwise ordering rules, and a collection of lists (called updates) that need to be checked if they are sorted according to the rule. This seems straightforward, but as always you have a (big!) input file to handle. In this case the input looks like this (the actual input not included here, but it's much much longer)
75|13
53|13
[...elided...]
75,47,61,53,29
97,61,53,29,13
[...elided...]
For this step, StringTools is your best friend (I typically read in the whole input as a string using FileTools:-Text:-ReadFile). I first use StringSplit on the double line break "\n\n" to seperate the rules from the updates. Then I map an ordinary Split over those to make everything into nested lists of integer.
(rules, updates) := StringSplit(Trim(input), "\n\n")[]:
rules := map(s->map(s2i,Split(s,"|")), Split(rules,"\n")):
rules := [[75, 13], [53, 13], ...]
updates := map(s->(map(s2i,Split(s,","))), Split(updates, "\n")):
updates := [[75, 47, 61, 53, 29], [97, 61, 53, 29, 13], ...]
(the function s2i is a "string to integer" helper function since it's considered bad practice to just call parse on input handed to you by a stranger on the internet. In older version of maple I used: s2i := s->sscanf(s,"%d")[1] in newever versions you can use the way less cryptic s2i := s->convert(s,'integer') )
Okay, now that we have two nice lists, it's easy to check which of the updates is sorted according to the rules with a simple nested loop.
goodups := DEQueue():
for u in updates do
for r in rules do
if member(r[1],u,'i') and member(r[2],u,'j') then
if j < i then next 2; end if;
end if;
end do;
push_back(goodups, u);
end do:
For each update, check that if a rule applies to it then that rule is obeyed. If the rule r is violated, advance the outer loop with the relatively new and useful next 2; syntax (it also works with break #) and if not check the next rule. If no rules were violated then push u into our stack of Good Updates. This is a perfectly fine solution to part 1 of the puzzle, but if you thing about it a little why not just use sort with a custom comparision function built from the rules?
V := ListTools:-MakeUnique(map2(op,1,rules)): # all the numbers that can appear
N := [seq(map2(op,2,select(n->m=n[1], rules)), m in V)]: # all their neighbors in the graph induced by rules
T := table([seq(V[i]={N[i][]}, i=1..nops(V))]): # table of neighbors
comp := (x,y)->evalb(y in T[x]): # "less than" according the rules
Now with that comp function we can just do
goodups := select(u->sort(u, comp)=u, updates);
to find all the correctly sorted updates, this will seem like a better idea when you get the [SPOILER] part 2 of the problem which is to sort all the incorrectly sorted updates.
NOW WAIT A MINUTE. If you look at the fine help page for ?sort you'll see it very clearly says about the comp function F (emphasis added):
custom boolean procedure
When F does not match one of the symbols listed above, it must be a Boolean-
valued function of two arguments. Specifically, F(a,b) returns false if and
only if b must precede a in the sorted output. That is F(a,b) is a non-
strict less than comparison function. In addition, F(a,b) must be defined
for all pairs a for a and b in the input structure and F(a,b) must be
transitive, that is, if F(a,b) = true and F(b,c) = true then F(a,c) = true.
Dear reader, I guess we should check if our rules from the puzzle create a relation that is transitive. The good news is that the sample input given in the problem description is indeed transitive. The easiest way I could think to check that was to use GraphTheory and see if there were any cycles in the directed graph given by the rules. So, let's make a graph with an edge for every comparison rule a<b, b<c, etc. If there is a cycle in the graph, that will be a case where a < b < c < a in our rules and therefore non-transitivity in the comparison. When we do that, we see it's cycle-free.
with(GraphTheory):
G := Graph({rules[]});
FindCycle(G); # returns []
That graph is really nice, it looks like this:
If you count the in-degree of each vertex, you can see it actually induced a total order on the numbers going linearly from smallest to largest numbers.
So, is that also true of the actual input you are given? Of course not. When you create the graph of your actual puzzle input you find there is a 3-cycle.
with(GraphTheory):
G := Graph({rules[]});
FindCycle(G); # returns a 3-cycle
seq(FindCycle(G,v),v in Vertices(V)); # returns a 3-cycle for every v!
In fact, there is a 3-cycle from every single vertex. But at least the graph is pleasing to contemplate. Let it calm you:
So, does this mean sort with out comp function doesn't work? Is all lost? In fact, I solved both parts of the puzzle using a custom comparision for sort before stopping to consider that maybe the comparison wasn't transitive. And... it just works! So, WHY does it work? (the comparison is very very non-transitive). The answer is of course that the lists you need to sort don't contain all of the numbers covered by the rules. In fact, your clever/cruel puzzlemaster has in fact constructed each of those (200 or so) lists so that it misses every one of the 3-cycles in the above graph. You can carefully check that by restricting the relation graph to the subset of numbers in each list and check for cycles:
G := Graph({rules[]});
H := InducedSubgraph(G, updates[i]); # try for i=1..nops(updates)
FindCycles(H); # returns [] for every element of update
In fact, each of those induced subgraphs looks like this
and you can maybe observe that this induced a total order on the numbers in the problem. Or if you are not careful, and you didn't bother to check, you would get the right answer anyway. Because it's only Day 5, and Eric Wastl hasn't decided to make thing really challenging yet.
I hope you've enjoyed my deep dive into this problem. And I hope it's inspired you to go try out Advent of Code. It's a fun challenge. Let me know in a comment if you're participating! Maybe we can start a leaderboard for MaplePrimes folks working on the puzzles.
