I almost wonder if I would have had a quicker solution time on Advent of Code's Day 24 puzzle if I had tried to do it while distracted with holiday celebrations, instead of deciding there was no way I could attempt it without clear focus time. I spun my wheels for a long time overengineering part of the solution, because I had convinced myself after a first, quick, read that this problem was reversing a hash, and so its search space would be huge, even after I figured out the "trick". It's not pencil-and-paper small with my final technique, but it is still milliseconds-of-computer-time small all the same.
-record(reg, {w=0, x=0, y=0, z=0}).
exec(Instructions, Inputs) ->
exec(Instructions, #reg{}, Inputs).
exec([{inp, Reg}|Rest], State, [I|Input]) ->
exec(Rest, set_reg(Reg, State, I), Input);
exec([{Op, Reg, Arg}|Rest], State, Input) ->
Val1 = get_reg(Reg, State),
Val2 = get_val(Arg, State),
exec(Rest, set_reg(Reg, State, apply_op(Op, Val1, Val2)), Input);
exec([], State, Input) ->
{State, Input}.
apply_op(Op, A, B) when is_integer(A), is_integer(B) ->
case Op of
add -> A + B;
mul -> A * B;
dib -> A div B;
mod -> A rem B;
eql ->
case A == B of
true -> 1;
false -> 0
end
end;I started with a simple implementation of the ALU that could run both the example and full code with a given input. I don't think I even bothered trying fourteen 9's in a row, just in case that was the answer, at this point.
%%% symbolic op implementations
apply_op(add, A, B) ->
case {A, B} of
{_, 0} -> A;
{0, _} -> B;
{_, _} when is_integer(A), is_integer(B) ->
A + B;
{_, _} ->
{add, A, B}
end;Instead I moved on immediately to giving the ALU support for "symbolic" operations. That is, instead of integers, I could also pass atoms, and the ALU would give me back exentially the s-expression representing the algebraic formula for the ending state of each register. I included some basic identity operations, so that it could replace things like {mul, x, 0} with just 0, but the resulting s-expression was still a partial binary tree with maximum depth of 170. The Erlang shell did not like printing that result.
apply_op(mul, A, B) ->
case {A, B} of
{_, 0} -> 0;
{0, _} -> 0;
{_, 1} -> A;
{1, _} -> B;
{_, _} when is_integer(A), is_integer(B) ->
A * B;
{_, _} when is_integer(B)->
case value_range(A) of
List=[H|_] when is_integer(H) ->
[X*B || X <- List];
_ ->
{mul, A, B}
end;
{_,_} when is_integer(A) ->
case value_range(B) of
List=[H|_] when is_integer(H) ->
[X*A || X <- List];
_ ->
{mul, A, B}
end;
{_, _} ->
{mul, A, B}
end;Turning to code inspection, a hand-run of the first few operations initially led me to believe that there was a comparison that could never be true. But I could only tell that because I knew that the inputs would never be outside of 1..9 in the real problem. To get my ALU to recognize the same, it needed to know that too. I decided to add one more input type: lists of possible values.
apply_op(eql, A, B) when is_integer(A), is_integer(B) ->
case A == B of
true -> 1;
false -> 0
end;
apply_op(eql, A, B) ->
case A == B of
true -> 1;
false ->
AllA = value_range(A),
AllB = value_range(B),
case {lists:all(fun erlang:is_integer/1, AllA),
lists:all(fun erlang:is_integer/1, AllB),
ordsets:intersection(AllA, AllB)} of
{true, true, []} ->
%% can never be equal
0;
_ ->
{eql, A, B}
end
end.But, while teaching the mathematical operations to add a number to a list of numbers was easy, comparing lists proved too complex, except for the specific case where they were exactly equal. This was wheel-spinning spot number one. Did I need to start a branched search here? Did partial overlap mean something specific?
I went back to the puzzle code to have another look. I had tried hand-evaluation, both forward from the beginning, and backward from the end. Both quickly ended up with growing formulas, like my symbolic evaluation had returned. Finally, looking at the rest of the file, I noticed that it's not 200-something lines of code. It's 14 repetitions of 18 lines of code. Each repetition starts with reading the next digit, and then runs an identical set of operations, except with different constant values.
split_instructions([{inp, w}|Rest]) ->
{Inst, RestB} = lists:splitwith(fun(I) -> I =/= {inp, w} end, Rest),
[[{inp, w}|Inst]|split_instructions(RestB)];
split_instructions([]) ->
[].
[D1, D2, D3, D4, D5, D6, D7, D8, D9, D10, D11, D12, D13, D14] =
puzzle24:split_instructions(Instructions).
puzzle24:exec(D1, [lists:seq(1,9)]).
% {{reg,[1,2,3,4,5,6,7,8,9],
% 1,
% [14,15,16,17,18,19,20,21,22],
% [14,15,16,17,18,19,20,21,22]},
% []}Above is a run of the first 18 line section, with all possible first digits. The output is a record named reg with fields for the ending values of each register (w,x,y,z), in order. What this shows is that the first block of code will produce a 14 in register z if the first input digit is 1. It will produce a 15 in z if the digit is a 2. Sixteen for three, and so on. Neat, what happens with the next block?
puzzle24:exec(D1++D2, [lists:seq(1,9), lists:seq(1,9)]).
% {{reg,[1,2,3,4,5,6,7,8,9],
% 1,
% [11,12,13,14,15,16,17,18,19],
% [375,376,377,378,379,380,381,382,383,401,402,403,404,405,
% 406,407,408,409,427,428,429,430,431|...]},
% []}I've appended repetition 2 to repetition 1, and added another 1..9 input for it to try. The result of running each of the 14..22 input z values against each of the 1..9 input digits is is 81 possible output z values. If this keeps up, we could have 22,876,792,454,961 (=914) output values to check! Let's go look at the last block.
puzzle24:exec(D14, [lists:seq(1,9)]).
% {{reg,[1,2,3,4,5,6,7,8,9],
% 1,
% [10,11,12,13,14,15,16,17,18],
% [10,11,12,13,14,15,16,17,18]},
% []}The last block's output is very similar to the first block. But, none of those output values would cause MONAD to consider the input model number valid. We need this block to produce 0 for that to be the case. What input would cause this block to be zero?
inp w mul x 0 add x z mod x 26 div z 26 add x -5 eql x w eql x 0
This is how the block starts. It's clear that we care whether the value we have accumulated in z, which has been copied to x (mul x 0, add x z), is equal to the final digit (inp w, eql x w), after some math (mod x 26, add x -5). What value(s) would make that true?
puzzle24:exec([{inp, z}|D14], [lists:seq(1,9), lists:seq(1,9)]).
% {{reg,[1,2,3,4,5,6,7,8,9],
% {eql,{eql,[-4,-3,-2,-1,0,1,2,3,4],[1,2,3,4,5,6,7,8,9]},0},
% {mul,[10,11,12,13,14,15,16,17,18],
% {eql,{eql,[-4,-3,-2,-1,0,1,2,3,4],[1,2,3,4,5,6,7,8,9]},0}},
% {add,{mul,[0,0,0,0,0,0,0,0,0],
% {add,{mul,25,
% {eql,{eql,[-4,-3,-2,-1,0,1,2,3,4],[1,2,3,4,5,6,7,8|...]},0}},
% 1}},
% {mul,[10,11,12,13,14,15,16,17,18],
% {eql,{eql,[-4,-3,-2,-1,0,1,2,3,4],[1,2,3,4,5,6,7,8,9]},0}}}},
% []}I've prepended an {inp, z} instruction here, so I can pass z's initial value in as input. The puzzle code sets the x and y registers get set to zero (mul x 0, mul y 0) before using them, so their input state can remain arbitrary. Giving z the same 1..9 value that the next digit will have produces the above "mess". But in that mess lies the confirmation that the math on z is simple: {eql,[-4,-3,-2,-1,0,1,2,3,4],[1,2,3,4,5,6,7,8,9]} is the comparison of our input z to our input w, after z has been shifted down -5, just as add x -5 says.
puzzle24:exec([{inp, z}|D14], [lists:seq(6,14), lists:seq(1,9)]).
% {{reg,[1,2,3,4,5,6,7,8,9],0,0,[0,0,0,0,0,0,0,0,0]},[]}If we pre-shift our input z up to 6..14, that add x -5 produces 1..9, and the whole block collapses to produce 0 for every input digit! This is progress. We just need to figure out how to tell the previous block, D13, to produce an output z value in the range 6..14.
inp w mul x 0 add x z mod x 26 div z 26 add x -3 eql x w eql x 0
Block 13 starts the same way as block 14, but with a -3 being added to x instead of -5. Our trick will work to get us a zero value. How do we get up to 6..14 though?
puzzle24:exec([{inp, z}|D13], [lists:seq(4,12), lists:seq(1,9)]).
% {{reg,[1,2,3,4,5,6,7,8,9],0,0,[0,0,0,0,0,0,0,0,0]},[]}
puzzle24:exec([{inp, z}|D13], [lists:seq(30,38), lists:seq(1,9)]).
% {{reg,[1,2,3,4,5,6,7,8,9],0,0,[1,1,1,1,1,1,1,1,1]},[]}
puzzle24:exec([{inp, z}|D13], [lists:seq(56,64), lists:seq(1,9)]).
% {{reg,[1,2,3,4,5,6,7,8,9],0,0,[2,2,2,2,2,2,2,2,2]},[]}
puzzle24:exec([{inp, z}|D13], [lists:seq(160,168), lists:seq(1,9)]).
% {{reg,[1,2,3,4,5,6,7,8,9],0,0,[6,6,6,6,6,6,6,6,6]},[]}
puzzle24:exec([{inp, z}|D13], [lists:seq(368,376), lists:seq(1,9)]).
% {{reg,[1,2,3,4,5,6,7,8,9],0,0,[14,14,14,14,14,14,14,14,14]},[]}The key is two lines before the addition: mod x 26. This means that an input 26 higher than our zero output will have the same result in terms of the eql x w comparison. The useful part is that bumping input z up 26 bumps output z up one! We can get output z into the range we need by giving input z any value in 160..168 (=6*26 + 4..12), 186..194 (=7*26 + 4..12), … 368..376 (=14*26 + 4..12). That's great …
… except it means we have the same 9N growth as from the top down. I spun wheels here again for a long time, trying to figure out a compact way to express a growing pattern of steps and strides. One of the things that made that concept complicated is something I've glossed over a little: one of the constants that changes between blocks is the div z … operation. The two I've shown so far both say div z 26. But the first block says div z 1. In fact, all blocks uses either 26 or 1 on this line, and that groups them into two categories:
function_shape([{inp, w}, {mul, x, 0}, {add, x, z}, {mod, x, 26},
{dib, z, Z}, %% indicator
{add, x, X}, %% value 1
{eql, x, w}, {eql, x, 0}, {mul, y, 0}, {add, y, 25},
{mul, y, x}, {add, y, 1}, {mul, z, y}, {mul, y, 0},
{add, y, w},
{add, y, Y}, %% value 2
{mul, y, x},
{add, z, y}]=I) ->
function_shape(I, Z, X, Y).
function_shape(_I, 26, X, _Y) ->
ZeroMin = -X + 1,
%% if input Z is ZeroMin, input W==1 will give output Z=0
%% if input Z is ZeroMin+1, input W==2 will give output Z=0
%% if input Z is ZeroMin+2, input W==3 will give output Z=0
%% if input Z is N*26+ZeroMin, input W==1 will give output Z=N
{add_out, lists:seq(ZeroMin, ZeroMin+8)};
function_shape(I, 1, _X, _Y) ->
{ZeroReg, _} = exec(I, [lists:seq(1,9)]),
%% if input Z is 0, input W==1 will give output 1
%% if input Z is 0, input W==2 will give output 2
%% if input Z is N, input W==1 will give (output 1)+N*26
{mult_out, ZeroReg#reg.z}.I've discussed only the first shape so far, the one that will give us z=N output for a z=26*N+c input. The second shape does the opposite - it gives us z=26*N+c output for a z=N input. The inscrutable names I've given them here (add_out and mult_out), reflect how I was missing the point of this duality. I nearly named them generically shape_a and shape_b just to move on.
input_domains_for({add_out, ZeroOuts}, ValidOuts) ->
lists:flatten([[ZO+VO*26 || ZO <- ZeroOuts] || VO <- ValidOuts]);
input_domains_for({mult_out, ZeroOuts}, ValidOuts) ->
Base = hd(ZeroOuts),
lists:usort(
lists:filtermap(
fun(VO) ->
case (VO - Base) rem 26 of
N when N >= 0, N < 9 ->
{true, (VO - Base) div 26};
_ ->
false
end
end,
ValidOuts)).It wasn't until I put in significant work trying to come up with a compact representation of the combination of these two "functions" that I finally gave up and decided to just let the exponential explosion run wild. And that's when I finally saw it: one shape increases the number of valid inputs (add_out), and the other shape decreases it (mult_out). I hadn't seen it before, because in the forward direction, input-shrinking is output-growing, and the program begins with output-growing in the direction I hand-simulated.
Starting from the last block and working backward, there are only five input-growing blocks in a row. The fifth power of nine is "only" 59,049 - too many options for me to consider by hand, but trivial for a computer. After that, there is some interleaving of input-growing and -shrinking blocks, before a final string of three input-shrinking blocks at the start. This implementation could work!
highest_valid_value([Inst|Rest], ZOuts) ->
io:format("Inst~p: length(ZOuts)=~p~n",
[1+length(Rest), length(ZOuts)]),
Shape = function_shape(Inst),
Domains = input_domains_for(Shape, ZOuts),
{ZInput, RevDigits} = highest_valid_value(Rest, Domains),
Digit = highest_digit_for(Shape, ZInput, ZOuts),
{Reg,_} = exec([{inp, z}|Inst], [ZInput, Digit]),
io:format("Inst~p: ZInput=~p Digit=~p Zout=~p~n",
[1+length(Rest), ZInput, Digit, Reg#reg.z]),
{Reg#reg.z,[Digit|RevDigits]};
highest_valid_value([], _) ->
{0, []}.My solver starts from the end, where we know the output value must be 0, and then works backward through the blocks, passing block N's valid inputs to block N-1 as valid outputs. Once it reaches block 1, we have no choice in z input, so given that input z will be 0, it selects the largest input digit that will cause the function to produce one of the valid z outputs that were passed up. It passes the choice of digit and the z output it produced back through the stack, where each block does the same.
highest_digit_for({add_out, ZeroOuts}, ZInput, _ZOuts) ->
((ZInput - hd(ZeroOuts)) rem 26) + 1;
highest_digit_for({mult_out, ZeroOuts}, ZInput, ZOuts) ->
Base = ZInput * 26 + hd(ZeroOuts),
lists:foldl(fun(W, undefined) ->
case lists:member(Base+W-1, ZOuts) of
true ->
W;
false ->
undefined
end;
(_, Found) ->
Found
end,
undefined,
lists:reverse(lists:seq(1,9))).Interestingly, it's only the input-shrinking (output-growing) blocks that have a choice in which digit they should use. The input-growing (output-shrinking) blocks have to use the digit that matches the z input they were given.
SplitInst = puzzle24:split_instructions(puzzle24:load_file()).
puzzle24:highest_valid_value(lists:reverse(SplitInst), [0]).
% Inst14: length(ZOuts)=1
% Inst13: length(ZOuts)=9
% Inst12: length(ZOuts)=81
% Inst11: length(ZOuts)=729
% Inst10: length(ZOuts)=6561
% Inst9: length(ZOuts)=59049
% Inst8: length(ZOuts)=6561
% Inst7: length(ZOuts)=729
% Inst6: length(ZOuts)=81
% Inst5: length(ZOuts)=729
% Inst4: length(ZOuts)=81
% Inst3: length(ZOuts)=729
% Inst2: length(ZOuts)=81
% Inst1: length(ZOuts)=9
% Inst1: ZInput=0 Digit=1 Zout=14
% Inst2: ZInput=14 Digit=2 Zout=376
% Inst3: ZInput=376 Digit=9 Zout=9790
% Inst4: ZInput=9790 Digit=3 Zout=376
% Inst5: ZInput=376 Digit=4 Zout=9785
% Inst6: ZInput=9785 Digit=9 Zout=376
% Inst7: ZInput=376 Digit=9 Zout=9789
% Inst8: ZInput=9789 Digit=8 Zout=254533
% Inst9: ZInput=254533 Digit=9 Zout=6617868
% Inst10: ZInput=6617868 Digit=4 Zout=254533
% Inst11: ZInput=254533 Digit=9 Zout=9789
% Inst12: ZInput=9789 Digit=1 Zout=376
% Inst13: ZInput=376 Digit=9 Zout=14
% Inst14: ZInput=14 Digit=9 Zout=0
% {0,[9,9,1,9,4,9,8,9,9,4,3,9,2,1]}As predicted, the maximum number of options under consideration by any block was 59,049 (=95) - an easy task for a modern computer. The output is in reverse order, because I left this code in I'm-just-working-in-the-shell state.
I worried as I clicked to proceed to Part 2 of this puzzle. Part 1 had taken a lot of analysis, and if Part 2 was going to make some major change like adding a new operation, or allowing zeros in some cases, I was probably going to give up. But thankfully, the change was the easiest one I had considered: find the lowest model number instead.
lowest_digit_for({add_out, ZeroOuts}, ZInput, _ZOuts) ->
((ZInput - hd(ZeroOuts)) rem 26) + 1;
lowest_digit_for({mult_out, ZeroOuts}, ZInput, ZOuts) ->
Base = ZInput * 26 + hd(ZeroOuts),
lists:foldl(fun(W, undefined) ->
case lists:member(Base+W-1, ZOuts) of
true ->
W;
false ->
undefined
end;
(_, Found) ->
Found
end,
undefined,
lists:seq(1,9)).I copy-pasted and then made the change instead of parameterizing my existing functions. But the only difference is in considering input digits in 1..9 ordering instead of 9..1 order. Literally a one-line change: remove the lists:reverse from the last line of highest_digit_for.
timer:tc(puzzle24,lowest_valid_value, [lists:reverse(SplitInst), [0]]).
% {10317,{0,[9,8,1,2,1,6,1,9,6,1,1,7,1,1]}}Most output has been elided here in order to highlight what I mean by this being a trivial task for a modern computer. The solver runs in 10ms. This model-number-checking ALU has a lock nearly as weak as the old video games that asked for the Nth word on a specific page of the manual!
This puzzle brought back memories of tracing through EVM bytecode - something I haven't done in nearly two years now. I can't say that it made me want to do it again. Full code is on github, as usual. On to the final puzzle!
Categories: Development AdventOfCode
Post Copyright © 2021 Bryan Fink