Everybody Codes is now in its
third year, and I've been doing it again, though I started a little late.
All of my code is on Codeberg.
As one would expect, a nice easy start. My approach overall is to
generate a list of valid target numbers, until the highest equals or
exceeds the highest input number; then for each input number, find the
lowest target that equals or exceeds that input, and add the
difference between target and input to the total.
Part A: this is perfect squares, and since I feel like it I use the
double-addition progression (initial value = 1, initial delta = 3,
delta goes up by 2 each step). (Or calculate n².)
Part B: value = 4 × n.
Part C: this is mostly perfect squares, but missing out half of them.
Basically the same code as part A, but initial value = 8, delta = 16,
delta goes up by 8 each step. (Or calculate n²-1 and increment n by 2
of course.)
Well now. This is a case in which recognising the nature of the
problem solved it for me.
And the reason I was familiar with it comes from 2020, when for a few
months I was doing the shopping, with a list supplied to me by my
wife. Because, well, because I am me, I wanted to optimise the order
in which I passed through the shop; I was fairly sure there must be a
standard way of taking a set of information about how to order pairs
of members of a set and turning that into an overall order. Sure
enough, it's called topological
sorting, and I
implemented it in Perl to put my shopping lists into the most
efficient order.
So I've done that before, and here I use the topological-sort
module for Rust rather than doing it again. But that solves the entire
problem all the way down to part 3; the only reason I changed my code
at all was that I started with 32-bit integers, and that wasn't large
enough for a checksum number for part 2.
As for parsing, I did it the lazy way: split each measurement on "<"
or ">", parse the numbers on either side, and if it's "<" reverse
them.
(I was expecting to discover in later parts that one measurement in
the set was inconsistent, and I'd have to exclude each one in turn to
find out which it was.)
Ah, now that's an enjoyable three-parter!
The core of it is in part 1: parse the line, extract the digit
sequences, and convert them to a final value. I use regular
expressions, then split the captured strings to characters, convert
those to digits, and reverse them (because I assume that standard
number and number of digits won't always be the same length, and this
way all the numbers at index 0 in the sequences are the ones dealing
with position 0 (rightmost) in the input).
Then combine them. I borrow some standard integer exponentiation code,
which as it turns out does the right thing for 0 to the power 0.
For part 2, rather than worry about wrapping the pointer into the
standard, I simply double the standard's length until it is no shorter
than the count. (Also go up to u64 integers from my initial u32.)
For part 3, there's probably a means of calculating the minimal
representation, but I used a brute-force method. Build a sequence of
digits of length equal to the count, then run through it, 0000, 0001,
0002, etc., checking for each one whether I have a value equal to the
decoded count value. If I do, and the sequence is not the same as the
count sequence, this number is invalid.
Three quite distinct problems here, and the id value only ever got used as
a key, not in the output.
Part 1: just extract id and time, and I can safely assume no
duplicates.
Part 2: now I'm counting by parts, but again assuming no duplicates I
don't actually have to parse them, just count them. Then a two-stage
sort.
Part 3: a bit more chunky here, not to mention that I have to write a
"places" function that caters for ties, such that I can for example
assign [100, 100, 101] the place values [1, 1, 3]. Broadly:
Filter by quest and part.
Take each time, add it to previous times within this quest.
Assign points only to those who completed this part (not to everyone
who has previously participated in this quest).
Rank those scores and assign points (based on the place value).
Next part, next quest.
Finally, rank the total points.
I like to see problems that are like a well-known problem, but
different. So if I had a high-level library for solving the well known
thing, it wouldn't help; but knowing how that solution works does
help.
In this case it's basically cellular automata and my main error was to
use a vec of vecs as my grid structure. Better, as I've done before
and as I did in part 3, to use a hashmap of i32 coordinate pairs.
Part 1: single growth loop, putting out land where (existing land +
map shade) indicates it until it reaches stability.
Part 2: add a second growth loop, putting out sand.
Part 3: add an initial tree placement loop, and then two growth
passes on that.
For each part I'm counting a different sort of cell value to get the
final result.
The part 3 final layout is quite attractive:
