Advent of Code Day 24: Computing with Sets | Hacker News Reader

Advent of Code Day 24: Computing with Sets

reitzen.com

61 pointsreitzensteinm17 comments

This was also roughly the idea I used; if you squint it comes down to a BFS and as such can use a lot of memory. My solution was to fix the first few digits (as in the article) and then run the VM in parallel over the remaining digits, combining solutions (because the have the same internal state) as it goes. If you do this for all the allowed permutations of the first few digits then you must have covered the entire search space.

I don't really understand how the "early out" logic works but that would have been pretty nice. My solution didn't have that and took quite a bit of time.

There sure is a lot of squinting going on in this thread.

There really is a lot of "squinting" in here--is there an inside joke I missed?

I implemented a very similar solution to the one in the OP in Python, abusing the superpowers granted by Pandas. (Using Pandas was strictly necessary, Python itself is too slow)

The "correct" solution to the problem is, as often is the case for Advent of Code, too tedious to implement: since the only way the program behavior changes is if the states of the registers diverge after an input operation, you can consider inputs that lead to the same states as "related". The coarsest partition with respect to this relation may be found by partition refinement. (https://en.wikipedia.org/wiki/Partition_refinement)

Assuming an efficient representation of the search space, this results in a solution that does the minimum amount of work possible.

The way I solved this was by squinting a little and realizing that every time a div instruction happened, then a certain number following it needed to be 0, depending on the value of certain constants embedded in the code, and also on certain other fields in the input. So instead of starting with an input number, it is possible to calculate the min and max values the fields may contain right there, as long as we embed the field positions in a stack.

As this is only going through the input code once, this is virtually instantaneous and ended up as the day that was fastest of all days to compute.

https://github.com/yxhuvud/aoc21/blob/main/day24.cr

I guess the solution could be classified as meta-analytical.

That's very clever. Though this does rely on the supplied input following a certain format. So far they all seem to.

The early out interpreter I describe should work in general, although it will probably fail to accelerate many programs.

I saw a lot of reverse engineering of the programs in the AoC subreddit, which was part of the reason I decided to write this up. I didn't even read the supplied program when building this solution.

I spend some days writing a program which construct an expression tree (actually a DAG) from the instruction and then through applying logic derives the equations between the input values for when the final result must be zero. But this was after analyzing the puzzle itself and understanding how the puzzle worked. In a sense it automated the analyzes I performed myself on my own input. The program works for all possible puzzles and very quickly finds a solution. For the details see: https://github.com/FransFaase/AdventOfCode2021#tuesday-decem...

I remember that day, the day I really gave up on Advent of Code. There was no way to solve the problem without tweaking things by hand. It stopped being a programming puzzle, and just became a nightmare.

I solved this in a couple of hours just now with pen and paper after looking at the input program. There seem to be only 3 types of instructions:

- either you unconditionally append a new digit to Z

- or you conditionally either:

- replace the last digit in Z with a new one

- or you remove the last digit in Z

The only way you would end up with a 0 at the end is if every one of those conditions evaluates such that you always remove the last digit of Z. Each of those 7 conditions constrains 2 of the input digits at a time, and once you list out those conditions, you're done.

While it's an interesting approach to implementing it, this feels like it's functionally equivalent to "Brute force execution with memoization". Specifically, it's like a depth-first search, and the set you have at each stage is equivalent to the set of memoised values you would have with a more typical implementation. Or am I missing something that makes it different?

You're not missing anything. It's collapsing the state space at the value level rather than interpreter wide, but it's a similar process.

Because it doesn't capture the whole state it is vulnerable to false positives. But that in turn probably makes it more memory efficient.

My solution would make Google disappointed in a whiteboard interview, imo.

Day 24 was hard... This is an interesting and elegant approach. Thank you for sharing.

Skipped it due to time and ability constraints. Going for the cucumbers later...

Thank you! I quite liked that the solution was a small repurpose of a straight forward interpreter. The ALU->Rust compiler via partial evaluation coming in the next post also barely modifies the naïve interpreter.

I built that one after AoC concluded out of curiosity, but the contents of this post were my in the moment solution.

I had a not so great solution that took about 30 minutes to run, but since I was busy with Christmas things I'd run it, go about my things, stop by the computer later, fix a tiny mistake, and run it again. I kept thinking about cleaner ways to solve it, this was hard one.

My solution is a black box crack. Test with each added input digit whether with a certain value the output "z" becomes smaller. If not, then try the previous digits again.

https://easylang.online/apps/show.html?f=aoc21/24.el

What was the thought process that led to this solution? Did day 24 remind you of some other problem you'd seen before?

My first instinct was to vectorize the interpreter, amortizing the cost across searching many possibilities in parallel. But 9^14 is still a huge search space even when efficiently implemented on a CPU, and indeed the compile to Rust brute force version I built later isn't faster than this one at finding the lowest/highest answers.

Then I started to think about pruning the search space with early out. If you squint, there's a similarity here to bloom filters. It gives you two possible answers: definitely no, or possibly yes.

I was expecting to run in to issues where the state grew too large, but that turned out never to be the case.

An alternate way to approach it would have been with dynamic programming, but I didn't feel like that would be as much fun.

Reply on news.ycombinator.com