I did Everybody Codes, a new set of programming challenges in the style of Advent of Code.

New challenges came out each weekday in November, but I only heard about this towards the end of the month, so from about day 10 I was doubling up with AoC problems (AoC is still going on as I write, and I'll blog that later.)

The style is very similar to AoC, a multi-part challenge each day with input customised for each user so that you don't necessarily get the same result as someone else who's playing. (This means that you have to log in via OAuth, and since the available options are Twitter, Google, Microsoft, Gitlab, Bitbucket and Github… well, these contests are one of the reasons I keep a Github account, even though all my code has moved over to Codeberg. Perhaps I should get a Gitlab account as the only one of these things that isn't actively in the business of Evil As A Service, but they're planning to sell out just like all the others.) The challenges aren't available without a login, so I shan't link them directly here.

I decided to work with Rust because I think I'm finally getting reasonably competent at it (though I still haven't done much with traits or lifetimes), I can write it reasonably effectively, and it runs fast.

I'll talk here about each day and my solutions. Should you want to follow along, my code is at Codeberg.

Day 1

An easy start is traditional with these things. I like the progression here: from 1 to 2 you have to consider a pair, easy enough, but from 2 to 3 gives multiple possibilities. I went along with counting characters rather than chunking the input list, and adding bonus potions at the end of the triplet.

Day 2

This one was briefly fiddly—mostly in terms of counting overlaps. (In part C, the wrap means that your unit might continue into the second copy of the string, but you need to score it as if it were in the first copy.)

Day 3

Nice and solid here. HashMap works well as a grid structure and means I don't have to worry about boundary conditions—if get returns a failure I can set a default value. Basically repeat until nothing moves.

My part A answer works for part B.

Day 4

Quite straightforward here too. For the first two parts I don't have to subtract individually, just take (sum of all heights) - (min height x count of nails). For part C I go O(N²) but N is only 499 in my individual data and I'm using a compiled language.

My part A answer works for part B.

Day 5

An enjoyable day with three different variants of the basic iteration engine: part B with a counter, and part C with a hashset so that I can detect the repetition of a state (which is of course a tuple of round % 4 and the actual columns list).

Day 6

Due to a misreading of the rules (I was searching for shortest path, not unique path length) I set up a breadth-first search when depth-first might have been more efficient.

Parts 1 and 2 were straightforward, but working out what was going on in part 3 required some inspection—at which point I hardcoded the relevant entries to remove.

A better approach might have been to look back down the path to find a duplicate node and prune at that point, but "Remember, you're solving puzzles, not finding general solutions".

Day 7

I built an over-sophisticated approach for part A, thinking in AoC terms ("now do it for many more cycles"), and then backed it out of part B when the problem went off in a different direction.

Part C was the most enjoyable; I wrote a track decoder (in Perl) to turn the track into a single string, then used standard permutations plus a set to avoid duplication. I was pondering further optimisation when my crude test code gave the right answer.(One might expect fewer cycles to be enough, since the track length is a multiple of the cycle length, but no.)

Day 8

A: got slightly too clever, calculating a total number of blocks all in one step. But it worked.

B: OK, have to count the hard way. Still basically works.

C: had to jump from u32 to u64 to avoid an overflow (fortunately I have that available, and even u128 if I want it). The removal algorithm generates too many removals on the innermost column on the first level.

Day 9

Part A: very straightforward as usual.

Part B: an on-demand hash table. Not very efficiently calculated, but it got the job done.

Not fast enough for part C, though, so I switched from hash table to vector, seeded with a maximum possible value. I think this is probably "dynamic programming" though I don't really know why.

Day 10

A and B were pretty straightforward. C was much harder going: the grid solver got extended with a re-solver, which if it had filled in a column then filled in the ? on the corresponding row and vice versa—but most crucially, if the subgrid remains unsolvable, the ? should be backed out before continuing.

Day 11

A is pretty straightforward of course. Rather than storing individual termites as implied, I store a hash of termite type and count.

B: basically the same, only with more generations.

C: the termite types no longer fit in a char, but rather than farting about with Rust's strings, I treat the character sequences as base-36 numbers using from_str_radix. Then it's just a matter of using each termite type (the keys of the progression hash) and taking min and max of the results.

Day 12

Fairly straightforward in the first two parts, with a big match to get the various coordinates in the right places. Then it's just a matter of tracing each shot path and seeing if it hits a target. (For part B, if we hit a double target, just score double points.)

This was far too slow for part C, so I took an algebraic approach. The highest interception point for a meteor starting at (X, Y) will be at coordinates (X / 2, Y - (X - X / 2). Also subtract the shooter's height from the y coordinate. Call those coordinates (x, y).

Now we have to solve for three possible intercept modes: on the climb, on the flat, or on the fall.

• Intercepting on the climb: x == y, power y. Failing that,
• Intercepting on the flat: y > 0, x falls between y and y * 2 inclusive, power y. Failing that,
• Intercepting on the fall: (x + y) % 3 = 0, and y < x. Power (x + y) / 3.

Day 13

This was more a two-parter than a three-parter, but it was rather pleasing.

Part 1 could be done by exhaustive search, but it would be pretty hard work; if it smells of pathfinding I reach for Dijkstra, and in Rust I use the pathfinding crate. Remembering last year's Advent of Code day 21, I create a Grid class and define the neighbours method within that rather than mucking about with a global static grid.

Part 2 is basically the same but bigger, but since I'm using Dijkstra I can just throw the same code at it.

Part 3 could be done with individual paths, but that crate offers me the dijkstra_all function, which gives me all reachable nodes from a single starting point. So I start at "E", filter the results for border nodes, and take the minimum cost.

Day 14

Part 1 is a pretty straightforward regex parser; all I care about is the maximum Z value.

Part 2 is a three-dimensional grid fill.

Part 3 fooled me at first by the worked example not demonstrating that it did actually need pathfinding, not just a Manhattan distance. But given that, throw it at Dijkstra and extract the results.

Day 15

Part 1 is a fairly straightforward full Dijkstra (i.e. get the cost to every grid square, not much more compute than the cost to just one square).

Part 2 was the pain for this one. What it came down to was:

Calculate all costs between significant points (e.g. from each 'A' to each 'B, etc.).

Take every permutation of herbs (with entry point at start and end).

For each adjacent pair of herbs in that permutation, work out a cost to travel between every possible combination (e.g. every 'A' to every 'B') and store that indexed by the 'B'. If there was already a cost to get to the starting herb (i.e. this isn't the first pass) add that to the cost to get to the ending point.

The lowest cost in the store when we get back to the starting point is the lowest cost path for that permutations.

The minimum value for all permutations is the answer.

Part 3 is a thing I dislike in AoC too: the problem is only practically soluble if you make assumptions about the puzzle structure. In this case, there were three vertical segments which could be solved separately and added together.

If applying my part 3 solution to your problem, note that the values for "herbset" must start with the entry point to that set: my left column contained A to E, and E was the entry point. Also, each entry point had a twin in the far corner, and I simply remove those by hardcoded list before starting the calculations.

Day 16

Getting quite tough now.

Well, part 1 was easy enough, just parse the reels (probably the hardest bit), step them with modulus, and see what we've got.

Part 2 starts to get tricky. I bring in my favourite Counter class for scoring. But mostly this is a cycle problem: I can work out a grand cycle length for the machine (the lcm of all reel lengths), so I segment the earnings into:

(earnings for a grand cycle) * (total cycles / grand cycle length)

(With integer division of course, I haven't used a float type in one of these problems yet.)

plus

(earnings for total cycles % grand cycle length)

Code duplication because I was feeling lazy; obviously I could en-function this.

Then part 3, which clearly wants to be a combinatorial explosion. My solution is not fast (over a minute on my relatively old machine) but it works.

First, enumerate all possible machine states (and encode them as integers). From these derive two lists indexed by machine state:

• the payoff for that state
• the three succeeding states (left lever 0, -1 or +1 and then right lever)

That's the bit that takes a while.

Then build a hashmap of state to (min, max). For each cycle:

• look at each state
  • look at each successor
    • add pay to incoming (min, max)
    • if this state has already occurred this cycle, cap (min, max) by the (min, max) we already have
    • insert that in the next states list
  • copy the list of next states to the list of states for the next cycle

The overall answer is the min of all the mins, and the max of all the maxes, of the final state list.

Day 17

For me this is more a "recognise the class of problem and deploy the right algorithm" problem than a "derive from first principles" problem.

Part 1 is a spanning tree, and since I have the pathfinding crate ready to hand I have two algorithms. Kruskal and Prim. I picked Kruskal mostly at random, and this worked well, for part 2 as well.

Part 3 needs me to segment a set of nodes, and it turns out that pathfinding can do this too. So I establish the connections, throw the set at connected_components, then get a Kruskal spanning tree on each set.

Day 18

Another relatively easy one thanks to pathfinding and dijkstra_all.

Part 1: find the cost from start to each P node, return the highest.

Part 2: for each start, find the cost from start to each P node, storing by P node the lowest value found. Return the highest of those.

Part 3: N to N Dijkstra. For each start point, get the costs to each P node and add the results. Return the lowest of all of these.

(Would probably be quicker to dijkstra_all from each P node to all possible start points, but then the results would need more processing, and food was imminent.)

Day 19

Harsh but fair. Rust is fast enough that part 2 is basically part 1, but for part 3 I needed to get cleverer.

This ends up building a map of transformations over one full processing pass, then building a list of the cycles (loops) to be found within that. Then any given grid entry will follow the cycle it's on for effectively (passes % cycle length) steps.

Day 20

Three quite different pieces of code in this one.

Part 1 is basically a dynamic programming problem: in each cycle, generate a new set of (position, direction) tuples we can reach. For any given tuple, keep only the one with the greatest heiht.

Part 2 similarly, but it's a (position, direction, flags) tuple, incrementing flags as we pass through the gates. (This one took me a while; my earlier attempts found the shortest route from each flag to the next, but that's not necessarily the shortest route overall, e.g. if it's worth gaining some height between B and C because the route from C to end doesn't allow it as readily.)

And Part 3 I solved mostly by inspection: looking outward from the centre line, find the column that's most +-ful (e.g 4 to the right in the test data). Then encode the sideways shift to get there, and the trip down that column. Much simpler than a general-purpose solution (even if you exclude the possibility of going north).

Conclusions

What I learned:

I seem to have got more generally fluent in Rust since last year, so that's good. I didn't feel anything was an entirely new idea to me, except perhaps some of the finickiness of dynamic programming (and I'm still not really sure what that means as such).

Crates used:

• pathfinding, five times
• itertools, three times
• counter, twice
• regex, once

Yes, a lot of pathfinding here, five of twenty days, and I'd hope to see some more diverse problems next year. None of the inputs needed serious parsing, and I didn't resort to winnow.

In spite of some hiccups I'll be back next year.

Thanks to Emil Kaczyński, and the EC team.