Gobbel2000

I don't think there are many significant optimizations with regards to reducing the search tree. It took me long enough to get behind it, but the "solution" (not saying there aren't other ways) to part 2 is to not calculate anything more than once. Instead put partial solutions in a dict indexed by the current state and use that cached value if you need it again.

It seems like you are actually constructing all rows with replaced ?. This won't be viable for part 2, your memory usage will explode. I have a recursive function that calls itself twice whenever a ? is encountered, once assuming it's a ., and once a #.

Rust

Took me way too long, but I'm happy with my solution now. I spent probably half an hour looking at my naive backtracking program churning away unsuccessfully before I thought of dynamic programming, meaning caching all intermediate results in a hashtable under their current state. The state is just the index into the spring array and the index into the range array, meaning there really can't be too many different entries. Doing so worked very well, solving part 2 in 4ms.

Adding the caching required me to switch from a loop to a recursive function, which turned out way easier. Why did no one tell me to just go recursive from the start?

Rust

I was unsure in Part 1 whether to actually expand the grid or just count the number of empty lanes in each ranges. I ended up doing the latter which was obviously the right choice for part 2, but I think it could have gone either way.

Rust

This one was tricky but interesting. In part 2 I basically did Breadth-First-Search starting at S to find all spots within the ring. The trick for me was to move between fields, meaning each position is at the corner of four fields. I never cross the pipe ring, and if I hit the area bounds I know I started outside the ring not inside and start over at a different corner of S.

Part 2 runs in 4ms.

Rust

Discrete derivatives!

I kind of agree, props for getting a general solution. I actually realized this issue only after I got both stars and didn't feel like changing it again.

Rust

As others have shown, part 2 can be pretty simple if you allow one assumption: The distance from a start point to the nearest end point is always the same as cycling from that nearest end point back to itself. Under that assumption you can just take the lowest common multiple of these distances. And honestly, who can claim to understand ghost navigation and what you can and can't assume? Empirical evidence suggests that this is how ghosts travel.

Rust:

Cannot move princess out of castle which is behind a shared reference

Governments trying to ban end-to-end encryption be like:

Indeed, my solution fails on this input (returns 10, which is the location to seed 0), but it can be easily solved by also adding the ends of each range as well.

Maybe the input was quite forgiving. Thinking about it more, reversing the mapping can get quite involved, because it is neither surjective nor injective, so the inverse can actually have any number of results.

In your example there is no input that maps to 0, but there are two inputs that map to 11 (1 and 11). If the seed-to-soil map also included 10 20 2, 21 would also map to 11.

Rust

Getting the count of each card, the two highest counts easily show what type of hand we have. For part 2 I just added the number of jokers to the highest count.

I spent some time messing around with generics to minimize code duplication between the solutions to both parts. I could have absolutely just copied everything and made small changes, but now my solution is generic over puzzle parts.

Oh yeah, that's clever. I'll remember that when it comes up again.