I've been doing Everybody Codes,
a set of programming challenges in the style of Advent of
Code, now in its second year.
All of my code is on
Codeberg.
Parts A and B are pretty straightforward, with no memory bombs or
similar.
Part C gets more interesting. Obviously I'm not going to repeat a
thing a thousand times. But can I repeat it at all?
I'll make an assumption: the maximum range is less than the length of
the sequence. (This is true of my input data, but may not be for
yours. It's specifically not true for the third test setup. The fix
should be obvious, but since I haven't done it I won't claim that it
is.)
I end up looking for three different sorts of potential pairs of mentor
index m and pupil index p:
-
|m - p| <= limit (add one to the "middle" count)
-
p >> m but m + size <= p (add one to "right" count)
-
m >> p but p + size <= m (add one to "left" count)
The "left" count is the number of cases in which the pupil lies in the
repeat before the mentor, and the "right" count similarly in which the
pupil is in the next repeat. "middle" is the count of pairs that don't
cross boundaries.
With one repeat, the result is "middle". With two, it's middle + right
for the mentors in the first repeat, middle + left for those in the
second. Adding a third repeat in the middle adds (middle + left +
right).
So the total is middle * repeats + (left + right) * repeats - 1.
Starting to get a little meaty here, and as often the answer is in the
correct choice of data structures. Specifically, the chain is stored
in a map of primary characters to sets of secondary characters, which
gives me a quick lookup.
Part A: get the basics up and running.
Part B: more or less the same as A, only wrapped in a loop.
Part C: well, we still need the validator (something I missed on my
first pass). Then for each prefix it's a search, which I chose to do
as breadth-first, following my usual pattern for these things: when a
value comes to the front of the stack, stick it in the results list if
it's valid. (And use another set for that, for automatic
deduplication.) Then if it's short enough to be extended create all
the possible extended versions and push them onto the end of the
stack. This did get run in --release mode, and takes about 3.7
seconds on my reference machine.
Part A got me looking at index values: if the difference between high
and low is exactly half the circumference, it crosses the centre.
For part B, a line crosses another if the index values are
interleaved. Thus if line x runs from x0 to x1, and line y runs from
y0 to y1, each anchor point of y can be defined as "inside" x if
x0 < yN < x1
or "outside" x if
yN < x0 || yN > x1
One end of the y line might match an x anchor, which is neither inside
nor outside and we'll ignore it. If one of y's anchors is inside x
and the other is outside, the lines cross.
And part C goes on similarly: I build up the list of lines from part
B, then for each possible cut synthesise another line and see how many
lines it crosses. Here I add some special case code for the two lines
being identical.
I particularly appreciate the logical flow of the parts in this
question. It's fair enough when a puzzle asks you to do a completely
different thing in a later part, but here I can see the thought
leading between them, and I rather enjoy that.
Definitely meaty now.
Rather than keep track of the official index numbers, I just error out
if they're not monotonically increasing. My indices start at zero
because my subscripts start at zero.
For part A I abuse the Counter crate (I like this crate more than is
reasonable). For each place, if there's a pair and a singleton, the
singleton cannot be the child. Once there's only one possible child
left, break out of the loop and calculate the similarities.
For part B each individual gets a Vec of possible parent pairs,
which are winnowed as in part A. Then I go through what's left,
looking for the individuals that have any possible parents (as opposed
to ones that are only parents), and work out their matches again as
in part A.
For part C the match calculation code goes away. A "family" is a set
of individuals; we don't care about parental relationships or
relationship paths except that they exist. Then I should have used the
connected_components functions in the pathfinding crate to
coalesce the 3-individual groups into families, but by the time I'd
remembered what it was called I'd already written one myself.
A partial solution today. I uploaded to document the first parts, but
I suffered a total enthusiasm failure for part C. I may eventually
come back to this.
Part A is all about sets. Generate the set of all dragon moves,
intersect it with the set of sheep.
For part B timing matters. At each turn, use only the set of possible
dragon moves at this point, then intersect it with the sheep at this
point. Them move the sheep, and do the same thing.
But for part C I need to work it out in detail, and this is where my
standard stack-based approach to depth- and breadth-first searches
falls down; I need to memoise based on the board state, but because
memoisation works at a function level that means I need to use a
function that takes a game state and generates the outcomes, and so
I'd need to rewrite my code recursively. (Or memoise it myself, in
some other way.) THe code here works on the smaller examples (up to
4406, though it takes a while), but I haven't been in the mood to
transform it in the way I can see it needs.
I do this stuff for fun first.