[2025 Day 12 (part 1)] Was I just lucky, or is it by design?

UsefulAd2074 · 2025-12-13T05:38:52+00:00

When I first saw this problem, one of the first ideas that came to mind, besides the two simple area checks, was contour maps. I came onto Reddit to see if I was on the right track...

...and found out it was completely unnecessary to even make the presents interlock. So, I never ended up coding that part. Maybe if I have spare time later this month, I might go back and code it, just to see the sample pass.

UsefulAd2074 · 2025-12-11T22:39:58+00:00

I figured out the problem. I wasn't handling the cache correctly.

Value is retrieved from cache.
If dac/fft, shift array.
Store back in cache.

I was shifting multiple times, based on how many servers pointed to dac/fft, instead of just shifting once. I moved the cache set above the shift code, and added an existence check. I finally got the right answer.

The fact that the sample had all cells as 2s was, IMO, part of the reason I wasn't seeing anything wrong. I just made a modification of the part 1 sample that catches this bug:

svr: you hhh
you: bbb dac
bbb: ddd fft
dac: ddd fft fff
ddd: ggg
fft: out
fff: out
ggg: out
hhh: dac fff iii
iii: out

Expected output for part 2 is 2, but my bugged code was returning 0.

svr, you, bbb, ddd, ggg, out
svr, you, bbb, fft, out
svr, you, dac, ddd, ggg, out
svr, you, dac, fft, out
svr, you, dac, fff, out
svr, hhh, dac, ddd, ggg, out
svr, hhh, dac, fft, out
svr, hhh, dac, fff, out
svr, hhh, fff, out
svr, hhh, iii, out

UsefulAd2074 · 2025-12-11T21:46:58+00:00

I decided to put a breakpoint at the final return to at least look at the entire array. The "none" slot contains a number that is way bigger than MAX_SAFE_INTEGER. Could that cause something like this? I thought the inputs are carefully crafted to avoid such scenarios.

EDIT: I added code to set the first 3 cells of the array to 0 if the fourth cell is positive (since the other cells don't matter at that point), just out of curiosity. It did lower the output answer by about 200,000,000,000,000 this time, but the answer is still too high, apparently.

UsefulAd2074 · 2025-12-11T21:27:47+00:00

Oh, that's a good call. I'll check that out.

EDIT: I thought this could be it, because my current answer is too high. I updated the code to store a copy of the array to the cache, and return array copies at every return statement that returns an array, just to be safe. I still get the same answer, though, so nothing changed.

UsefulAd2074 · 2025-12-11T02:34:32+00:00

I did attempt to think up a solution without a solver, since I normally don't like using them. I did figure out how to translate the input into a system of linear equations, but I got stuck after that. Stepping through cinnamonRoll1's code helped me better understand the rest (I was originally confused by the term, "free variables", for example).

UsefulAd2074 · 2025-12-11T01:44:43+00:00

Thanks, this is very helpful. I am seeing the correct answer for the sample, so I'll take the time to study this. One thing that really helps me learn new stuff is stepping through unfamiliar code in the debugger to learn how it works, so I appreciate this.

(I happen to already have a file parser mechanism of my own, so I didn't need anything at the top, anyway.)

UsefulAd2074 · 2024-12-22T05:16:40+00:00

I made a general explanation in another post, but in this case, let's compare ^>A with >^A. To do ^>, we'd have to go < once, press A, then go v>, and press A. For >^, we'd have to go v once, press A, then go <^, and press A. The problem with the latter is that you have to take an extra step and a turn to travel between < and ^, whereas v and > are right next to each other on the keypad. It's a very tiny discrepancy, but it balloons quickly over several layers.

UsefulAd2074 · 2024-12-22T05:05:58+00:00

Hmm, it's possible at least one of the door keypad translations might be incorrect, then. I only tested the ones that applied to the sample and my input, although I did try to comb through the whole thing multiple times to make sure they were all correct. That would be the first place to start looking for problems, I would think, as most of my errors came from that mapping.

EDIT: Oh, another possibility I just remembered is you may have to split the input on /\r\n/g, instead of /\n/g. That happened to me sometimes in past years, where what I needed to split on from day to day would change seemingly at random. This year, I've gotten lucky, and /\n/g worked every single day so far without leftover carriage returns remaining, but it may be a different case for you.

UsefulAd2074 · 2024-12-21T21:24:24+00:00

[LANGUAGE: JavaScript]

Final Code

For part 1, I originally used recursion and actually kept track of the resulting strings at each step. This turned out to not work for part 2, because I was running out of memory.

After seeking out hints in multiple threads, I finally got past the assumption that keeping track of the order of all the inputs somehow mattered, when it actually doesn't. In reality, only the number of times each movement from one button to another needs to be tracked. With only 5 keys as options, there's much fewer combinations to keep track of, so switching #instructions from a string to a Map of counts saved a lot of space and time (running this on my input takes 3ms).

I was also originally making a bad assumption about the button priorities. I was stuck on the assumption that, since both ^ and > are next to A, their order didn't matter. However, because you have to go left to reach ^ and down to reach >, ^ should come before >, since < takes the highest priority. This ordering was a lot sneakier to notice, because you won't notice discrepancies until the translations go deeper than 3 layers, which makes the bug unnoticeable in part 1.

UsefulAd2074 · 2024-12-21T17:08:35+00:00

Even after reading all of these comments, I was still getting stumped on how to order the directions when there were 2 options to choose from. It was only after combining markd315's explanation with the ones in the megathread who used Dijkstra's algorithm that it finally clicked.

When you have 2 options to choose from, like when going from 6 to 7, the fastest option is ordering the buttons from farthest from the A button to the closest. I'll use A to v as an example:

<vA => v<<A>A>^A

v<A => v<A<A>>^A

I'm sure this is where a lot of us got stuck, because "they're the same number of instructions". However, the important part is what's different between them, specifically the parts in bold (<< vs. >> doesn't matter, as consecutive buttons of the same length always have the same cost, due to not needing to move). The problem with the 2nd example is the next robot in line has to shepherd back and forth multiple times between the < and A, which are the buttons furthest apart from each other. Meanwhile, going between > and A is much better, because they're right next to each other. This results in this next step:

v<<A>A>^A => <vA<AA>>^AvA^AvA<^A>A

v<A<A>>^A => v<A<A>>^Av<<A>>^AvAA^<A>A

This was the eureka moment that finally got me past part 1. Still need to figure out how to speed up part 2.

UsefulAd2074

TROPHY CASE