I did Advent of Code again, and had a
really good time again. Spoilers.
Language choices:
- 2018: very beginner Rust, floundered a lot, gave up after five days.
- 2019: Perl, completed
- 2020: Rust, but switching to Perl after two days; completed
- 2021: Rust, completed
- 2022: PostScript, not quite completed
- 2023: Rust, completed
- 2024: Rust, completed
Although there are some fairly core bits of Rust I still don't
understand, this year I felt comfortable with it more than I was
learning new things; it remains the language I most enjoy writing in,
especially when a program is more than trivial. (And I've taken to
doing Weekly Challenges solutions in it first, then translating them
to other languages.)
I didn't use winnow for parsing this time since I hadn't touched it
since last year and when I started these I was also doing the last few
Everybody Codes challenges too. Some days needed regexp parsing; most
worked simply on string splitting.
I'll talk here about each day and my solutions. Should you want to
follow along, my code is at
Codeberg.
A fairly straightforward start; the multiple spaces in the input
surprised me slightly, but no problem parsing. I'm a little surprised
to see a hash (hashmap, dict, associative array) needed on day 1, but
I'm old enough in wickedness that they still seem like a neat new
thing to me.
The first approach that came to mind was to establish a set of
differences between adjacent entries. Then check all diffs for
possible failure states:
- abs(diff) < 1
- abs(diff) > 3
- diff × (first diff) < 1
the last one picking up a change in direction.
Part 2 still needs to check the full report, because a report that's
safe in full may not be safe with one entry removed. So I moved the
checker out into a function.
Well, I'm glad I'm not doing this in PostScript this year. Yeah, it's
obviously possible to do this kind of thing without regular
expressions, but it's very tedious.
And I know, I should write a regexp engine in PostScript.
I don't know the Rust regexp library as well as I might, so part 2
ended up being in two stages: one to match a valid operator definition
(do, don't, or mul), the second to extract the parameters from the
mul.
I was able to recycle code for part 1 from a The Weekly Challenge
problem that hadn't been published yet when this came out. (Though
having to stick to a single direction, and a guarantee of no repeated
letters in a word, meant I could remove many of the checks.)
Then for part 2 it got simpler again. Rather than run the part 1 code
and analyse the results, I just look for each A, then examine its
diagonal neighbours in clockwise order. If there are four of them,
then a valid set will be MMSS, SMMS, etc.; so I double the string and
search for MMSS in it.
"Aha", I thought, "topological
sorting, I know
this". But actually no, because at least my main puzzle input has
cycles in it if you try to resolve it completely (e.g. A before B, B
before C, C before A), which is fine if you never have all of A, B and
C in the same update (as you don't here), but if you do a full
toposort on the input, it can't complete.
So instead a priority pair is a Map of earlier to a Set of later. (I
used this pattern quite a bit this year, for many to many mappings.)
For part 1, I check each pair of pages in the update for orderedness:
if the later one doesn't appear in a priority list, or the earlier one
doesn't appear in the later one's priority list, they are at least not
out of order.
For part 2, I write a custom sort function. checking both page numbers
and returning any ordering information we can find.
Part 1: I had some direction code from last year's day 21, so I
recycled some of that.
Part 2: the only places I try obstacles are on the traversed path, and
then it's just a matter or storing (location, direction) tuples to
find a repeat.
That was rather fun. Though I confess I stumbled a bit in implementing
an operator priority order version first, rather than left to right.
Part 1 was obviously a job for a bitmask (each interstitial place
holds either a * or a +), but for part 2 I used the excellent
multi_cartesian_product in itertools, which seems built for
situations like this. Then all that was needed was a reasonably
effective concatenation function; even "0" should produce a ×10 for
the first operand, because 12 || 0 would be 120.
I'm starting to think that the most important thing about parsing a
grid input is that one doesn't necessarily put it into a list of
lists. Today it was a HashMap of char to Vec of coordinates, thus for
the test input:
{'0': [(8, 1), (5, 2), (7, 3), (4, 4)], 'A': [(6, 5), (8, 8), (9, 9)]}
Then it's a matter of taking every pair of coordinates in each
frequency set and extending (and checking that they lie inside the
grid).
Part 2 is much the same, only with a two-sided "repeat until you fall
off the edge".
Part 1 uses a pair of moving pointers, stopping when they cross over.
For part 2 I went for Range rather than tracking each individual
block, which worked reasonably well. I know that removing an entry
from a Vec is expensive, but it looks as though this was slightly
faster than leaving an empty range to be tested against each future
file.
Then it's just a matter of checking for the case where the start of
the file is already earlier than the block it might fit into. (Grr.)
Several people accidentally solved part 2 while writing a naïve
solution to part 1. Not I: I threw part 1 at a standard Dijkstra,
which worked beautifully, but the implementation I'm using doesn't
give you all the distinct paths, only one shortest path. (The
pathfinding crate can actually do this, but not in its dijkstra
function.) I could have dug into the details for part 2, but it seemed
easier to write a
DFS.
Now that's a classic AoC. Part 1 is a nice solid list manipulator, and
obviously I think about maybe using linked lists (this is usually an
error, as in this case) but a standard vector will handle it no
problem.
Then part 2 will clearly explode, but… I don't need to do the
calculations repeatedly. Each separate "1000" will become a separate
"10 00" pair. So I just need a count of how many 1000s I had…
This is basically the same solution as 2021 day 6, "Lanternfish".
First one this year for which part 1 seemed more than trivial, though
of course I may be misremembering. My algorithm, given the grid, is:
-
initialise startpoints to all valid locations
-
infinite loop while startpoints is non-empty
-
start at a random point in startpoints
-
find all its neighbours with same letter
-
put all of these in region set
-
for each point in region, in all directions, add 1 to Perimeter
if there is no member of region in that direction.
-
area is number of points in region
-
delete region from startpoints
For part 2 obviously I remove the perimeter code, Instead, file each
failing edge (what could previously have been a perimeter segment)
under the direction I was traversing in.
Then for east- and west-facing edges, segment the list by equal X
coordinate (these edges might in theory form a single side), sort by Y
coordinate, and scan the list for gaps, which add to the side count.
Similarly for north and south with X and Y reversed.
This is not a computing problem, it's a maths problem. It looks like
an exhaustive search BUT.
Known values:
- (ax, ay) are the numbers for button A.
- (bx, by) are the numbers for button B
- (x, y) are the numbers for the prize
Unknown values:
- (a, b) are the number of presses of a and b respectively
so the result at prize point is:
- x = a * ax + b * bx (1)
- y = a * ay + b * by (2)
And everything except a and b are known.
So we have two equations in two variables. Which means there is only
one solution. Let's rearrange:
x * ay = a * ax * ay + b * bx * ay (3) (1) * ayy * ax = a * ay * ax + b * by * ax (4) (2) * axx * ay - y * ax = b * (bx * ay - by * ax) (5) (3) - (4)b = (x * ay - y * ax) / (bx * ay - by * ax) (6) rearrange (5)a = y - b * by / ay (7) rearrange (2)cost = 3 * a + b (8)
Never mind the minimum, there is only one value for costxs for each
machine. (Visually, consider the construction of a vector from zero to
the desired endpoint using only the vectors A and B; the counts of
each must be fixed, and the order won't matter. If any parameter could
e negative, that would be another matter.)
However a and b can only have integer values, so I undo each division
to make sure it gets the right result.
For part 1 it seemed most straightforward to build a position output
for N cycles rather than traversing one at a time. (Note that Rust has
the rem_euclid() method for a non-negative modulus.)
For part 2 I found the image crate and generated a series of images
to skim through. It became clear that there were two repeating
elements: several horizontal elements appeared every 103 frames (not starting
at zero, of course) and several vertical elements every 101 frames.
That let me generate formulae for a frame number in which each type of
element would occur, and finally I brute-force intersect those to get
a valid answer.
Nice to see a grid problem that isn't pathfinding. Part 1 was fairly
straightforward, particularly once I noticed I only had to change
three cells (where the robot was, where the robot will be, the empty
space at the end of the row).
Part 2 threw away that optimisation of course, and I ended up building
a stack of "movers", spaces from which a move will be made. Items are
added to the stack based on contents of this space and, potentially,
contents of the next space (but avoiding duplicate entries); there is
probably a better way to do this than the one I found, which seems
inefficient. Then I run over the movers list in reverse to copy their
contents to the destination space.
Part 1 can be handled by extending the grid into the third dimension:
direction on entry is part of the node identifier. (I did something
similar for 2023 day 17 "Clumsy Crucible".) So from a node where
you're facing east you can move east (cost 1), turn north (cost 1000)
or turn south (cost 1000). but to the pathfinding algorithm these are
all separate nodes.
For part 2, horrors, Dijkstra doesn't have a way of outputting all
best paths. But A* does. So all I need is a heuristic (Manhattan
distance is fine, I ignore directions here), then I simply extract all
best paths and count the distinct node coordinates (ignoring
direction).
I liked Intcode. (It was in my first successful Advent of Code in
2019.) This was less fun but still good.
Part 1 is a fairly straightforward interpreter.
Part 2 is obviously a bit more work but after inspecting the program I
solved it with an incremental search. The last value depends only on
the top (most significant) three-bit tuple of the input. The
next-to-last value depends on those and the next three. And so on.
So I build the input from a notional vector of 3-bit numbers. First
search 0 to 7 for a match in the last place of the output to get the
last three bits. Then multiply that by 8, and search that plus 0 to 7
to get the next three, And so on.
I was expecting this to be a path traversal problem with a changing
graph: take one step, a block falls, etc. But it wasn't that at all.
Might be fun though.
Part 1: I build a full grid, take out the relevant number of nodes,
then Dijkstra what's left.
Part 2: I move the Dijkstra into the grid loop and break when it
fails. This takes a bit longer, but still only about three seconds so
it doesn't seem worth optimising further. (The obvious approach would
be a binary chop: the grid at time 0 is passable, at time 2000 it
isn't, so try it at time 1000, etc.)
This was clearly a memoisation problem. Rust has memoize for this,
but I had great trouble getting it to work at first, so for part 1 I
did it by hand.
Part 2 choked up with that; I ported my code to Perl, added Memoize,
and it worked perfectly. So then I worked back and removed all the
things that seemed to be giving Memoize trouble until it finally
worked. (Oh boy a global static variable for towels would have been
easier, though.)
This was quite tricky, firstly because I misunderstood part 1 to mean
that you could remove two walls in succession. Originally I was
going to re-Dijkstra each case to look for savings. But since there is
only one possible path, any cheat must start and end on that path… so
I don't need to search the whole grid.
But with a lot of flailing around my correct part 1 is more
complicated than it needs to be. Take every point on the path, find
the neighbours that are walls, find the neighbours of that that are on
the path, make sure they are later on the path, make sure we haven't
seen them before, then calculate the saving.
Part 2, with a bit more thought, came out much more cleanly: take
every ordered pair of path points (and their indices in the path).
Calculate the Manhattan distance between them. If it's less then the
difference in indices, and no higher than 20, that's a valid saving.
Total enthusiasm failure on this one (it happens sometimes). Lots of
flailing about with special cases. I thought I was being so clever
setting both incomplete rows to be row 0, but one is at the top and
the other is at the bottom of the pad…
But at least my part 2 only needed me to change one parameter from
part 1 and memoise it.
Ah now that's a bit more like it.
Part 1 is a fairly straightforward shift-mod sequence.
Then part 2 is an exhaustive search, but I save some time by only
storing the information I need: for each starting number, the first
time I see a particular changeset, I add its value to the total for
that changeset. Then it's just a matter of pulling out the highest
total. For later calculations, it doesn't matter which or how many
changesets participate, so I don't store that information.
Quite a lot of false starts on this one; for part 1, I thought the
question was asking for sets of three that weren't connected to the
larger network and tried to use graph partitioning.
Then for part 2 it became clear that pathfinding wasn't going to be a
consideration, but my order-free sets turned out to be the wrong
approach. In the end I work internally on the node indices (assigned
ad-hoc as they come up in the connection list), and when considering
something to add to an existing set only look at nodes with higher
indices than any of those already in the set.
(In fact this is the clique
problem and there are
better algorithms for it than the one I invented.)
Also it's much easier in Rust to encode the node names as base-36
numbers, which can be transparently copied, than to work with strings,
which can't.
Ooh, now this was a really enjoyable one.
Part 1 was quite fun in itself, mostly in terms of deriving a
reasonably efficient data structure. (All right, I'm not sure I might
not have done better by deleting gates after they were activated. Or
built a queue. Or something.)
Part 2 came apart into three programs.
Given that this is a reasonably efficient binary adder, any Z value
must be the result of an XOR. Any gate that doesn't produce a Z value,
and doesn't take an X or Y value as input, cannot be a XOR. So any
gate that doesn't satisfy those constraints is clearly dodgy. ba
lists those. I note that I have six wrong nodes out of the eight I
need. With a bit more analysis I could have sorted out these pairs
automatically, but…
bb takes the input, applies any swaps, and produces a GraphViz file
which I then plot with neato. Given those swappablel nodes from ba,
I can see by looking at the output which nodes are near each other and
therefore need to be exchanged. (Populating swaps lets me redraw the
diagram to check.)
Just one more swap to find. bc steps through possible input values:
in binary, 1 + 1 = 10, 10 + 10 = 100, etc. It stops when it gets a
wrong answer. (I might have used more complex patterns involving the
incoming carry, e.g. 11 + 11 = 110, but at least with my input I
didn't have to.) That shows me where in the diagram I need to look,
and thus what the fourth swap pair should be. And the first thing bc
does is check that the official inputs add up correctly, so it's a
verifier for the final pair too.
Well, clearly this is more a parsing problem than a coding problem.
But it's a sort of parsing problem I've done a lot before.
Conclusions
I didn't end up using flashy new techniques this year, just built with
the Rust I already had. Mostly the hard bits were writing a good
algorithm; days 15 and 21 involved lots of worrying away at special
cases.
Crates used:
- regex (5 times, input parsing)
- pathfinding (4 times)
- counter (3 times, not a necessary crate but a handy one)
- radix_fmt (twice, for turning numbers back to base-36 strings)
- memoize (twice)
- itertools (once)
- image (once)
(I've written Dijkstra before. I've written it in PostScript! So I'm
happy to use a library for it now.)
My revised list of things to be able to do in your language of choice
if preparing for an AoC or Everybody Codes:
-
string parsing, with regexps or combinators or whatever works,
especially breaking down a string into specific arguments;
-
multidimensional arrays (or whatever your language uses to
substitute for them);
-
more generally than that, coordinates. Yeah, a basic list of rows
each containing a list of cells will work, but it would have been
handy to have a prepared way of dealing with directions, direction
changes, bounds checking, and so on. I still haven't actually
written a Grid class, because it gets tweaked quite a bit for each
puzzle;
-
depth-first and breadth-first search;
-
Dijkstra or A* pathfinding including edge cases like multiple best
paths. Probably graph theory in general really.
-
General algebra, usually seems to come up at least once.
Some regulars that haven't been about this year or last:
Puzzles sorted by Part 2 difficulty: this percentage is the proportion
of people who have successfully solved part 1, but not part 2, which
is the only public information about completion rates. (Based on a
snapshot at the time of writing, so values may have changed.)
- 10: 2%
- 18: 2%
- 8: 4%
- 7: 5%
- 1: 7%
- 4: 8%
- 14: 10%
- 19: 10%
- 3: 10%
- 13: 11%
- 23: 12%
- 5: 12%
- 11: 14%
- 20: 15%
- 22: 15%
- 9: 16%
- 16: 18%
- 2: 20%
- 12: 21%
- 21: 22%
- 15: 23%
- 6: 26%
- 17: 30%
- 24: 47%
(Day 25 doesn't count, as part 2 is essentially "have the other 49
stars".)
That was not entirely consistent with my experience; 17 and 24 were
good fun though I grant 24 was a bit of work, and 6 didn't trouble me
much, while 21 was the one I found hardest. (For me "hard" means
"I don't really know what to do next" rather than "I know what to do
but it'll take a while".)
Thanks as always to Eric Wastl and the AoC team.