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)

import re

pattern = '\d'
cmp = re.compile(pattern)

# extremely lazy, of the ungood kind
datapath = 'data'
lines = open(datapath, 'r').read().split('\n')
candidates = []
values = []
for l in lines:
    if l != '':
        r = cmp.findall(l)
        candidates.append(r)
        values.append(int(''.join([r[0], r[-1]])))

print(candidates)
print(values)
print(sum(values))

changes:

mapping = {...} # name/int pairs
pattern = f'(?=(\d|{"|".join(mapping.keys())}))'
lines = open(datapath, 'r').read().split('\n').remove('')
values = []
for l in lines:
    r = cmp.findall(l)
    equivs = [str(mapping.get(x, x)) for x in r]
    head, tail = [equivs[0], equivs[-1]]
    values.append(int(f"{head}{tail}"))
print(sum(values))

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.

part b: Before diving into the discussion, I timed how long 1000 cycles takes to compute, and apparently, it would take 1643175 seconds or just over 19 days to compute 1 billion cycles naively. How fun!

So, how do you cut down that number? First, that number includes a sparse map representation, so you can tick that box off.

Second is intuiting that the result of performing a cycle is cyclical after a certain point. You can confirm this after you've debugged whatever implementation you have for performing cycles- run it a few times on the sample input and you'll find that the result has a cycle length of 7 after the second interaction.

Once you've got that figured out, it's a matter of implementing some kind of cycle detection and modular arithmetic to get the right answer without having to run 1000000000 cycles. For the record, mine took about 400 cycles to find the loop.

a. was a fun coding exercise. Not much more to say.

b. I lucked out by making a recursive traversal function for a), which let me specify the entry and direction of where my traversal would start. Besides that, similar to a., this was a fun coding exercise. I was surprised that my code (which just ran the function from a) on every edge tile) It only took 2s to run; I thought I might need to memoize some of the results.