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.
Premature optimisation was still premature, but probably worth it this
time.
Part A: yeah, I could count up individual cells, but the number of
blocks from element N is length (integer divide) N, so I'll just do
that.
Part B: OK, I do actually need a wall array for this. For each key
number N in ascending order, if index (N-1) is greater than zero, it
must be because N is in the recipe. So subtract 1 from all affected
locations in the wall array, increment N, and try again.
Part C starts with part B (to derive the recipe), then uses my
reasonably quick part A implementation to get a mapping from wall
length to blocks. Then I do a search, in three stages:
-
if the number of blocks is too loe, multiple the candidate length by
10.
-
binary search between the last two candidate lengths (one is too
low, one is too high) until we're nearly at the target.
-
start with the known too-high value from that, and drop it by 1
until the number of blocks is too low. That's the answer.
This one went interestingly sideways.
Part A: fairly straightforward; the grids are small enough to scan
cell by cell. (A custom subtraction function so that I can get
abs(usize - usize) without messing about. And a custom integer
exponentiation function for the squaring.)
Part B: again, once I'd worked out the trick of setting destroyed grid
values to zero so that they don't contribute to the next total, easy
enough.
Part C: all right I should have convered this to use my standard grid
and coordinate types. But I didn't. And I made an assumption which
didn't work on one test case, but did on my actual data.
How do I define "a loop" with specific points so that I can pathfind?
Well, all the examples hug the destroyed area as closely as possible
to west, south and east. And I can find those coordinates during the
destruction scan. So in the end I do four separate pathfinding
calculations: start to west, west to south, south to east, and east
back to start. (It is trivial to envision a grid layout in which this
doesn't give you the quickest overall loop.)
Then there's a custom "neighbours" function which avoids the cost zero
("destroyed") cells, and one thing that tripped me up is that the
start point is a cost zero cell, so there's an exception for that.
(Yeah, I should have used a separate HashSet of destroyed cells. Or
indeed put the whole grid in a HashSet as I usually do, instead of a
Vec<Vec>. But never mind, it works.)
So I do my four pathfindings, and if they all found paths and the
total cost is low enough, return the answer. As I say, this doesn't
work on testC3-3180 (giving 9 × 300 = 2700), but before I went to
track down the bug I thought I'd try it on the contest data, and that
worked. If you find out why it doesn't work on testC3-3180 feel free
to let me know.
Later, on reflection: I should have split the map into all but bottom
left, and all but bottom right, with the start column below the
volcano in common, then tone a dijkstra_all to the start point on each
side, then taken the lowest total to/from the same cell. But I didn't.
Too bad.
Fun in the end, but a bit of a slog. I found the description
remarkably unclear, or perhaps I was just tired. But realising that
this is a tree rather than a potentially looping network helped a lot.
As usual structures are important, and really getting the right one
for part A was most of the solution. The key is to reverse the links:
the link from A to B is listed under B, but I'll be using it when I've
got a value for A. (I seem to recall some dependency tree function in
the pathfinding crate which can automate this.)
Part B introduces a input mask, and I moved the energy field out of
the Node structure into a separate array since I'll be rebuilding it
for each mask.
For part C I cheated to find the maximum value. I'm not proud of it,
or of the problem that makes it amenable to this solution, but with 81
bits of input this obviously wouldn't be amenable to an exhaustive
search.
I did think about doing a limited depth-first search starting from
all-on and all-off configurations, but tried a short cut first: any
input node which produces at least one negative weight in its outgoing
links is set to off, and any other is set to on. This turns out to
produce the correct answer on the full data, though not on the test
data. It doesn't feel like a "fair" programming problem.
That was an interesting progression. The core of it was getting a
reasonably efficient calculation method for part A.
The order of individual flaps or not doesn't matter. There is a
diagonal up or down phase, and if the horizontal distance is long
enough, a bobbing-up-and-down phase.
For part A I built a struct of X offset and Y range (using
std::ops::Range as usual, though I didn't actually need the range
intersection tests this time).
Then I store a rolling list of heights and number of flaps taken to
each the latest gate at that height.
For each new gate, I double loop: the outer loop is the list of valid
entry heights (at the previous date), and the inner loop is the list of
possible exit heights (at the next gate). Half of those exit heights can be
thrown away because the absolute height gain over distance X, mod 2,
must be the same as distance X mod 2. Also only check reachable
heights: maximum height gain or loss is one per horizontal step.
Then the number of flaps taken to achieve that particular exit height
is the sum of:
- the maximum of 0 and the height gain (the diagonal upward or
downward phase of the flight)
- half the difference between the distance X and the absolute height
gain (the up-and-down phase of the flight).
(Plus the number of flaps needed to get to the starting height.)
A hash entry for each exit height holds the list of flaps needed, and
the rolling list is reinitialised with the minimum cumulative flap
value for each height.
The output is the minimum value in the final list of flaps, because
any valid height at the final gate is equally acceptable.
For part B I dropped the custom gate structure, because I realised I
was ending up with a HashMap. Key is the x value of the wall, and
value is the HashSet of Ranges indicating the holes in it.
Then we sort the keys and work as before, except that rather than
iterate over one range I'm pulling each one out of the inner HashSet
and working on it separately. Some of the gates are 1,500+ units high,
but the calculation I'm doing on each possible height is pretty quick.
As a result, I didn't need to modify part B at all to do the final
part in reasonable time. (About 0.8 seconds on my test machine.) I'm
sure this could be done more efficiently, but sub-second is certainly
Good Enough.
A frustrating final part, but I got it in the end.
A triangular grid is just the dual of a hex grid, and my usual
technique for pathfinding on those is to expand the coordinates. So
for example the cells in the first row would be assigned to
coordinates
(0, 0) (1, 1) (2, 0) (3, 1) ...
and the second row (noting that x=0 is unused) to
(1, 2) (2, 3) (3, 2) (4, 3) ...
etc. I drop these into a HashSet, and then finding neighbours is a
matter of scanning x = {-1, 0, 1}, y = {-1, 1} (half of which can
innately not exist anyway, and I could find out which half by looking
at coordinate values, but I don't).
Part A also ends up defining an ordering for coordinates so that I can
store unique pairs. HashSets are not innately hashable.
Part B throws that nonsense away and gets on with the pathfinding I
was expecting. Fairly straightforward.
Part C was more of a pain. This coordinate system is not readily
susceptible to rotation. (I suspect nothing with rational coordinates
would be, but my X and Y scales here are not only different but
non-uniform.)
So I ended up writing a rotate method for the Grid which iterates
over the whole space, working out old and new coordinate pairs; it's
inefficient, but it works.
Coordinates expand to three dimensions (with three layers, and each
layer can reach only to cells in the next), which accounts for one
grid rotation per step. The exit location rotates too (not in the
example but in my real data) so that becomes another HashSet with the
valid exit on each layer.
Conclusions
What I learned:
I still haven't got the hang of dynamic programming, but I didn't run
into any problems with inability to use Rust. I may of course be
missing tricks I could have used to make my code more efficient.
Crates used:
- pathfinding, three times
- regex, three times
- counter, twice
- permutator, once
If anything the parsing was easier than last year. Nothing that was a
challenge in regex. Not as much preponderance of pathfinding this year
as last, hurrah. (Not that I mind, but it started to feel a bit
samey.)
I'll be back next year.
Thanks to Emil
Kaczyński,
and the EC team.