Part 1 of day 17 was easy. So easy that I almost didn’t start. When I read that part 2 was unexpected, I completed part 1, then failed at part 2. Bruteforce nor general search seemed a possibility, so my strategy was to disassemble the program (seems more people did that) and then solve it backwards. But somewhere along the way, the reverse operation influences something it had already resolved. Bit of a failure.
Day 18, part 1, was a very straight-forward shortest path. I opted for two boolean matrices, and a list of paths with the same distance, which gets expanded every step. Part 2 had a huge search space. If I’m not mistaken there are (140 over 70) = 9.4e40 shortest paths in an empty matrix, so any form of enumeration is out of the question. My first idea was to progress until the shortest path was corrupted, then recompute, and procede until all were blocked, but my initial code didn’t store the actual path, so instead I opted for a binary search. That ran pretty quick, actually. The shortest-path code runs in 10ms or so, and there are 13 steps at most.
I was glad my first thought when reading the problem was wrong. After reading “but you’re faster”, I imagined the corruptions showing up as you walked along and there was a shorter path if you took advantage of that. But fortunately not.
Today, I started of with a primitive, recursive algorithm that removes a possible prefix, and then searches the rest. That was way too slow. Then I remembered there was a regular expression module. So I built a /^(ddf|nwu|wbww|ww|rbbu|…)*$/ pattern. However, the implementation of Regpat is probably a backtracker, so it couldn’t even get past line 2 within a minute. Then I implemented a trie, and treated it as an NFA. That runs fast, and uses little memory. A simple counter then got me the unexpectedly large answer for part 2.
I must say that it seems impossible to find any decent documentation for GNAT.Regpat. Most of the search results had a one or two line description of the module, and the best one was the .ads file, from which I had to guess how to use it.
Day 17: I “cheated” and used z3 for part 2 initially, but I spent a bit of time thinking about what the disassembled program is actually doing and went back and implemented a search that works solving 3 bits of A at a time starting at A’s MSB, only moving onto the next group of 3 bits when the corresponding digit matches in the program. The program shifts 3 bits out of A and carries no other state forward between loop iterations, and those 3 bits solely determine the digit it outputs. Since the output is 16 digits, A must be 46-48 bits long.
Day 18: the puzzle had poor phrasing (maybe to confuse LLMs? well it confused me too). I also thought the obstacles would move and started picking data structures to deal with that which wasted some time.
Day 19: I had a solution that would have worked within ~15 minutes, but only if I could have identified the problem as memoization I ended up switching to python to explore ideas for part 2 and wasted a bunch of time with one that I decided wouldn’t work before rethinking my approach. It turned out all I needed to do was port my original Ada part 2 to python and add @functools.cache…
Day 17: sort of like @jcmoyer’s solution, except that I didn’t think in terms of bits. I did it by hand a bit, then realized that:
The last value in register Amust be 0, otherwise the JNZ will keep jumping over and over.
For any value in registers A at iteration’s end, the value in register A at iteration’s beginning must be a number whose quotient from dividing by 8 gives the value at the end. That means only 8 possible values of A at iteration’s beginning could produce the value at the end, and most of those won’t work.
Note: This assumes that your program, like mine, modifies register A only by dividing by 8 on each iteration. Registers B and C aren’t red herrings (B produces the output, and C is used to monkey with B) but their values don’t affect Register A.
From that I realized I could just start with a queue containing 0, and for each value in the queue, multiply by 8, add each of 0…7, and test each of the sums against the desired output, re-enqueuing only the good ones.
Day 17: I ended translating the program into an Ada one, for running it quickly! For part 2, each output digit (with my input) depends on 10 bits (9 to 0, then 12 to 3 for the second digit, etc.). So I have brute-forced those 1024 possibilities per digit. Due to the overlap (I guess) the algorithm gets quickly looking for the possibilities of matching the last few digits.
Day 18: luckily I understood the game correctly, but so I re-read the text many times to find a possible trap that wasn’t…
Day 19: For part 1, I have done a memoization on the start index for matching the rest of the design with towels: type Possible is (no, yes, unknown); memo : array (1 .. max_len_design) of Possible := (others => unknown); The array is quickly filled with yes’es or no’s. For solving part 2, I turned the use of the ternary type into integers, with unknown = -1, then the actual counts for the values 0, 1, 2, ....
The structure of my problem was the same (B and C for computation, div 8, jnz at the end), and I made the same assumptions as you; also translated it to Ada for faster iteration. However, there was an expression which involved shifting A maximally 7 bits right before adding it to B
B := (A mod 8) xor Shift_Right (A, (A mod 8) xor 5) xor 3;
That means adding 0…127 to A on every round, but that messed up something further down. I didn’t see any use in brute-forcing it, nor could I think of another easy way, so I left the problem.
Interesting, I assumed there was only one possible structure for the program but looking at other inputs now I see that’s not the case. Mine has adv 3 right before the jump, but some programs have it before out 5.
EDIT: Here are some programs I collected in case anyone is trying to implement the correct general solution:
For Day 18, I also used a binary search, but (since it’s not clear from OP) you know that the first 1024 bytes do provide a solution, so you can start the search from byte 1025. After that, you once again
Not seeing anyone say anything close to this for day 19: think backwards.
I’ll elaborate using one of the puzzle description’s examples, rrbgbr.
From position 6, there’s only 1 pattern match, r. That translates to 1 arrangement.
From position 5, there are two pattern matches, b_ and br. Each corresponds to 1 arrangement: one carried over from position 6, and one here. That sums to 2 arrangements.
From position 4, there are 2 pattern matches: g__ and gb_. The first corresponds to 2 arrangements at position 5, and the second to 1 arrangement at position 6. That sums to 3 arrangements.
From position 3, only b___ matches, corresponding to the 3 arrangements at position 4. We’re still at 3 arrangements.
From position 2, there are 2 pattern matches: r____ and rb___. Each corresponds to 3 arrangements: the former at position 3, the latter at position 4. This now sums to 6 arrangements.
From position 1, there is only 1 pattern match: r_____. That corresponds to the 6 arrangements at position 2. We conclude with 6 arrangements.
If someone did say something to this effect and I missed it, I apologize! I also apologize for all the blurring, which requires more clicking, but the spoiler tag dies with each new paragraph.
Added in edit: Hmm, even the Reddit solutions I glanced through don’t seem to have thought of this. Or, maybe I’m unfamiliar with the vocabulary they’re using.
Possibly many people used recursion which does exactly that (perhaps “recursion” is the keyword to look for).
function Count_Options (design : VString; first, length_design : Positive) return Integer_64 is
last : Natural;
options : Integer_64;
begin
if memo (first) >= 0 then
return memo (first);
end if;
options := 0;
for i in 1 .. nt loop
last := first + Length (towel (i)) - 1;
if last <= length_design and then Slice (design, first, last) = towel (i) then -- Match
if last = length_design then
options := options + 1;
else
options := options + Count_Options (design, last + 1, length_design);
end if;
end if;
end loop;
memo (first) := options;
return options;
end Count_Options;
I considered that, but while I agree that the summands will be the same, I think my approach is more akin to a Fibonacci sequence calculator that retains previous values precisely to avoid recursing. You can see that, unlike the code you showed, this function never recurses:
function Arrangements (Design : Pattern_Vector) return Value is
Results : array (Design.First_Index .. Design.Last_Index + 1) of Value :=
[others => 0];
begin
Results (Design.Last_Index + 1) := 1;
for Ith in reverse Design.First_Index .. Design.Last_Index loop
for Pattern
of Redirects (Design (Ith))
when Matches (Design, Ith, Pattern)
loop
Results (Ith) := @ + Results (Ith + Natural (Pattern.Length));
end loop;
end loop;
return Results (Design.First_Index);
end Arrangements;
Could we call it an example of non-recursive memoization? I did see references to memoization (including your discussion) but most of the Redditors said they gave up on it. (Maybe all of them did.)
I did try recursion at first. In Part 1 I made it work by pruning the input words – only 29 of my original 447 are necessary – but even that didn’t work for Part 2: not even the first design would complete in a reasonable amount of time.
)
– but even that didn’t work for Part 2: not even the first design would complete in a reasonable amount of time.