Advent of Code 2021 - Day 24

Learning Questions & Discussions Coding Challenges
1

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

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

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

2

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
      ... # previous code that was this function
    end
end
2 Likes
3

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
4

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 :smiley:

5

This is the hardest problem of aoc2021 in my opinion :grinning: 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