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
- 2025: Rust, completed
As last year, this year's problems didn't seriously expand my Rust
knowledge the way 2023's did, though I did pick up a few new things.
Again, I just used regexps for parsing more sophisticated than string
splits, and most days didn't even need that.
The big news this year was that it was down to just 12 problems rather
than the previous years' 25. I can see the reasoning; it is clearly
not at all easy to put these things together, even with an
infrastructure that doesn't need much tweaking at this point. More
significantly for me, the global leaderboard (fastest solvers from the
moment the problem is released) is gone; since problems are revealed
at 5am for me, I generally didn't compete anyway, but now that people
are prepared to use genAI tools and shotgun possible solutions it's
meaningless anyway. (The point of the thing is to learn to program,
and speed solving isn't that, even if you don't cheat and get a
machine to do it for you.)
I'll talk here about each day and my solutions. Should you want to
follow along, my code is at
Codeberg.
An interesting variant on a standard modulus problem; part 1 was
simple enough, and I used a usual modification to keep all numbers
positive.
That wouldn't work in part 2, and I end up using both the standard
modulus operator (which can give negative values) and the rem_euclid
method (which can't).
Probably there are too many special cases in my code and this could be
optimised further, but hey, it works.
I like Everybody Codes. I enjoy it. But there's a subtlety to Advent
of Code puzzles that I very much appreciate.
Obviously I'm not going to convert the numbers to strings like an
animal. Instead, I'm going to generate all the possible invalid IDs
inside each range.
First I need to segment the input range by length. For example, in the
range 95-115, I want to look separately at 95-99 and 100-115. (And for
part 1 I only want to look at the even-numbered lengths.)
For that I'll use range-ext which I discovered a couple of years
ago; it'll compare two ranges and list which specific mode of overlap
they have (entirely within, overlapping on the low end, etc.) I move
that out into my range_intersection function, which will return a
range that is the true intersection of two input ranges. (Yeah,
there's a simpler way to do this, a new range of max(a start, b start) to min(a end, b end), but this way I could rely on known
working code.)
So I'll compare the ranges 10 - 99, 1000 - 9999, etc., with the input
range, and process any overlaps until my test range start is higher
than the sample range end.
But how to generate the IDs? I'll generate a multiplier value; any
invalid ID must be an integer multiple of this. For the range starting
at 10 it's 11; for the range starting at 1000 it's 101; etc. Then I'll
divide the range endpoints by that, rounding so that I slop over
rather than miss a value, and scan across those: so for my range 95 ..
99, dividing by 11, I'd be looking at 8, 9 and 10, generating 88, 99,
and 110. Each of those gets tested for whether it's inside the range
(only 99 is), and if so it's scored.
The short cut, of course, is that I'm keeping my half-length parameter
as a separate variable. We start at 10 .. 99 where half length is 10;
1000 .. 9999 has half length 100, and so on, and the multiplier is
always one more than that. Which comes back to bite me in part 2.
Now I need to generate more multipliers. For example, in thee
six-digit range, I'll need to test: 111111 (six units of length 1),
10101 (three units of length 2) and 1001 (2 units of length 3). For
each possible length from 1 to (one less than digits) I take digits %
length to see if it's an even repeat; then I generate the multiplier.
One last potential problem: for example, the value "23232323" will hit
as a repeat length 2 and as a repeat length 4. Rather than get sneaky,
I just stick the results in a HashSet for automatic deduplication, and
take the sum of the entries.
My first version of this used iterator.position but I realised,
after solving the puzzle but before uploading the results to Codeberg,
that I'd be embarrassed to publish such inefficient code so I rewrote
it.
For part 1, a two-digit answer can be found by taking the highest
digit that isn't the last, then taking the highest digit in what's
left. In each case, I iterate over the relevant range, latching each
time I find a higher value, and use the position of the first value to
define the second range.
For part 2 I roll that pair of operations into a loop. I take a slice
of the input (cut at the start by the position of what's been found so
far, cut at the end by the need for exactly 12 digits in the output)
and search it; then take the first occurrence of the highest value,
and use its position to define the next search range, and so on.
A relatively straightforward start, using one of my standard patterns
of expressing sparse grid locations as (x, y) tuples rather than
vectors. Turn the problem inside out to generate the neighbour
locations of each set cell and add one to each one's count. But the
count has to be initialised to zero, because a cell with no neighbours
won't otherwise show up. Then it's a matter of fiddling about with
Rust's HashMap Entry syntax, which has the exact thing I want (add one
to this entry if it already exists, otherwise ignore it) but I don't
know it well enough to do that without the documentation.
Part 2 cycles the process, so I generate the new field from the map of
neighbour values, check for no change, and start again.
Hmm, another range problem. Well, I suppose day 2 could be solved by
exhaustive testing; I've read solutions that did. But this one is
definitely going to need actual ranges.
This makes part 1 almost trivial; make a list of ranges, then check
the individual numbers for intersection with any range.
Part 2 needs me to collapse intersecting ranges into single ranges,
and while it's fairly easy to work out which case is which I like to
use range-ext to keep a check on myself. First I sort the ranges (by
starting point, then by ending point if those are equal), then the
first one becomes the accumulator ro. Each in sequence is tested
against ro, and either coalesces into it (if there's an overlap) or
causes the old ro to go onto the output list and becomes the new
ro.
Then it's just a matter of adding up the range lengths to get the
answer.
A rare day in which my part 1 and part 2 code are entirely distinct.
Obviously if I'm parsing line by line a list of rows is the obvious
way to store the output. But it works better to set up a column for
each problem, split on whitespace to fill them, and then iterate
through them.
Which leaves me ready to think about part 2, most readily viewed if
rotated anticlockwise as:
4
431
623 +
175
581
32 *
etc. and so the storage is a grid of chars rather than a grid of
numbers. Each value goes on a stack, and if there's an operator the
stack is multiplied or added to get an output value, then cleared.
(Not using .clear() since I've converted it into an iterator, so I
just throw it away and set up a new Vec.)
Yeah, I should perhaps have set up an enum for operator types, but in
a problem this size it didn't seem worth it.
More to follow…