I also struggle to think of the need for DP, even in a more “elegant” approach. Maybe if you wanted to do an O(n) memory solution instead of n^2, or something. Not saying this out of derision. I do like looking at elegant code, sometimes you learn something.

I feel like there’s an unreadable Perl one line solution to this problem, wanna give that a go, @gerikson?

I read the problem as follows: for N galaxies, find N/2 pairings such that the sum of distances is minimal.

At this point, I was like, wow, the difficulty has ramped up. A DP? That will probably run out of memory with most approaches, requiring a BitSet. I dove in, eager to implement a janky data structure to solve this humdinger.

I wrote the whole damn thing. The bitset, the DP, everything. I ran the code, and WOAH, that number was much smaller than the sample answer. I reread the prompt and realised I had it all wrong.

It wasn't all for naught, though. A lot of the convenience stuff I'd written was fine. Also, I implemented a sparse parser, which helped for b.

b: I was hoping they were asking for what I had accidentally implemented for a. My hopes were squandered.

Anyway, this was pretty trivial with a sparse representation of the galaxies.

a) I used a regex to do some parsing because I haven't looked at dart regex much and wanted to dip my toes a little.

I considered doing this "properly" with OO classes and subclasses for the different rules. I felt that it would be too difficult and just wrote something janky instead. In hindsight, this was probably the wrong choice, especially since grappling with all the nullable types I had in my single rule class became a little too complex for my melting brain (it is HOT in Australia right now; also my conjunctivae are infected from my sinus infection. So my current IQ is like down 40 IQ points from its normal value of probably -12)

b) There may have been a trick here to simplify the programming (not the processing). Again, I felt that directly implementing the specified algorithm was the only real way forward. In brief:

1. Start with an "open" set containing a part with 4 ranges from [1, 4001) and an "accepted" set that is empty.
2. Start at the workflow "in"
3. For each rule in the current workflow:

• If the rule accepts part of the ranges in the open set, remember those ranges in a closed set and remove them from the open set.
• Remove anything the rule rejects from the open set.
• If the rule redirects to a different workflow W, split off the applicable ranges and recurse at 3 with the current workflow as W.
• Keep in the open set anything the rule doesn't consider.

Because this is AOC, I assumed that the input would be nice and wouldn't have anything problematic like overlapping ranges, and I was right. I had a very stupid off by one error that took me a while to find as well.

This problem was mainly testing:

• Are you a bad enough dude to formulate this DP correctly?
• Are you a bad enough dude to choose a good DP state storage schema?
• Is your computer a bad enough dude to store all the DP states if you choose a bad storage schema?

...which is true of all DP problems, honestly. So given you know and understand how to approach DP problems, this would be more an engineering issue than anything.

Completed when waiting for the second leg of my Christmas holidays flight. (It was a long wait, can I blame jet-lag?).

Have a more compact implementation of LCM/GCD, something tells me it will come in handy In future editions. (I’ve also progressively been doing past years)