Advent of Code 2021 - Day 24

This topic is about Day 24 of the Advent of Code 2021 .

We have a private leaderboard (shared with users of Erlang Forums ):

The entry code is:
`370884-a6a71927`

Happy X-mass yâ€™all.

So for today my code isnâ€™t actually the â€śoptimalâ€ť solution, because that would have required you to completely read the assembly thatâ€™s in the input data and then do things that would absolutely not be a thing for the provided test inputs, but I have this thing where I want all of my solutions to run with both the test and the actual inputs without telling my functions about whatâ€™s happening.

So, how did I approach this? Well, I did take a look at the actual input and realized that it actually consists of 14 subprograms that pipe their output as input into the next subprogram. Each of these starts by reading the â€śinputâ€ť and puts their â€śreturn valueâ€ť in `z`. So with that, I made the problem into a â€śfind the smallest/largest input that causes the entire pipeline to retun a 0â€ť.

The way I then do this is by recursively attempting all of the possible inputs in descending/ascending order at each level and passing the output to the next level. I also keep track of â€śseen statesâ€ť in a map (in case weâ€™re at the same level with the same input value/z pair, we then already know that this wonâ€™t give us our 0).

And then we just run this whole thing and a whooping 75 seconds later (on my M1 Pro), we get an answer (for both of the parts).

Anyhow hereâ€™s the code:

Edit:

realised that I could apply one optimisation that would still meet my constraints, but cut the runtime dramatically (to now < 2s). Itâ€™s basically

``````def run_until_z_is_zero([subprogram | rest], z, input, level, seen, mode) do
if z > 26 ** if(level < 7, do: level, else: 14 - level) do
{z, input, seen}
else
end
end
``````
2 Likes

Merry Christmas!

I solved the problem after a few hours, but performance was abysmal (almost 10 minutes for each part), so I kept searching for a better solution during the day.

Finally, after much tweaking and light peeking at hints on reddit, I arrived at the following solution that solves both part in about 0.03 seconds on my computer:

1 Like

Thank you both @ramuuns and @bjorng , with your input I have been able to put up a solution of my own, using my own research on the problem and valuable hints from you.

It is slow (~2min for a part) but it works

This is the hardest problem of aoc2021 in my opinion Canâ€™t solve it after many days. In the end, I look into reddit and found a very elegant answer, this method doesnâ€™t need to analyze the input. I translated it into elixir.

1 Like