Day 20: My favourite problem from Advent of Code 2023
mliezun.github.io
mliezun.github.io
The intended solution only works because the input is more constrained than what the problem statement says (the problem in full generality is PSPACE-hard). If you give me a problem to solve, I'd rather have all the hypotheses, all at once.
One thing that bothers me more though is when the example input is nonsense for Part II or can be solved but in a radically different way because it has very different properties than the inputs people are given for real. Contrast day 19, where the example input has a rational answer, which you are told about for the Part II, against day 20 where the example input is completely irrelevant for Part II and good luck.
One thing I've tried to do when I run into those kinds of problems is to write a little benchmark to illustrate the difference between approaches. It's always kinda fun to watch your initial brute force solution start chugging while your shiny new solution seems to handle whatever you toss at it - great lesson in choosing effective algorithms.
I use Elixir to do the puzzles, so I've used Benchee for this, and it works very well. So easy to set up too.
Here's an example benchmark, which also has the output. As the input size increases you start getting some pretty crazy ratios between the two algorithms (the "smart" version was 200,000 times faster than the "naive" one on the largest test input!)
https://github.com/epiccoleman/advent_of_code_ex/blob/master...
That would be fine if there was only one input. But we have seen countless cases of a solution working for some and not others (including/especially the test input). So the cases and patterns I see in my input may be part of the hidden problem statement, or they may be just an artifact of my particular input. I at least feel more satisfied when I know my solution will solve all inputs.
For that reason, I side with the desire for a bit more purity and closure, vs having to guess, and not being sure about your guess until you go to reddit. Making educated guesses about patterns is a valuable ability, but I don't like the aesthetics of it here.
I try to write solutions which would work for inputs like mine but I'm not fussed if, for example, my code panics on hypothetical "valid" inputs that I didn't consider.
So e.g I have panics for nonsense input like, "Pipe networks with more than one Start can't be solved" and "Uneveen seed list cannot work as described in problem" [Yes that's a typo] but I also have "Should not send signals unexpectedly" and "Surely not all the stones have X velocity 0"
[1] https://github.com/flurie/aoc-rust/blob/main/src/bin/08.rs#L...
A more general solution is possible -- but it does require a trick that people may not be aware of unless they've studied a little number theory.
Annoying to code, but I've done it a thousand times by hand for math competitions, so it's kind of carved into my skull.
There might be multiple cases, but I don't think there's anything better (please let me know if there is, I'm very interested) -- as a matter of fact, an instance of the original problem can be used to encode an instance of a system of linear congruences, so finding a better algorithm for the latter would imply a better algorithm for the former.
n1*n2 can get at least as big as a*b/8 without a naive linear search being guaranteed to be fast, so this roughly square roots the runtime of 'CRT on all pairs' if n1 is close to n2.
Here's the code, sorry it's not as well commented as yours, and I haven't integrated it into a solution to day 8.
https://github.com/penteract/adventofcode/blob/master/utils/... .
For more than 2 moduli, the best I can think of is to separate them into 2 roughly equal parts, generate the full lists of allowed remainders for each part, then use this algorithm to combine the parts. There may be better things you can do here (and perhaps you can show that for large sets of allowed remainders across enough different moduli, the solutions are spread out evenly enough there's one you can find by naive linear search).
Dealing with non-coprime moduli is left as an exercise to the reader :).
The intended solution was seemingly to calculate the length of the cycle (as in, until you were on a "Z" node) for each starting node separately. Once you'd done this, you could find the LCM of these cycle lengths to find the overall period of the cycle (~10^13).
This solution might not work if your cycles weren't constant length -- for example imagine when walking your graph you found your i_th Z-node after {6, 7, 6, 7, 6, 7, 6, 7 ...} steps; or perhaps {6, 7, 7, 7, ...}. In the test data, this didn't occur - it was always {n, n, n, n, ...}.
I can give another example perhaps - consider you're asked to find the last 3 digits of 2^n for n >= 1. You start off calculating: 002, 004, 008, ... eventually you get to 2^103 which ends in 008. This means that the cycle length would be {103, 101, 101, 101, 101, ...} since it'll never get back to 002 or 004. Solving this is a bit more difficult than the constant cycle lengths, since it's not a simple LCM.
What has to be constant is the cycle length for (node, tape instruction #) pairs, because all the state to determine every future step is based on the current node and tape position; if both are the same, the path will be the same as before. I think, at least without advanced math, the only thing to rely on for "true" loops is identical pairs of (instr #, node), not just instr # or tape steps or node individually.
* a "tail" -- some initial part of the path before you get into a true cycle (like the 002, 004 in the example above)
* an inner repeating cycle before you reach a node you've seen before.
In the case given |t| = 0 and |c| = 1, but it's easy to construct a more complex example with nodes (A, B, C, D), edges (A->B, B->C, C->D, D->B), and 'ending nodes' being B and D. In this case left and right paths go to the same node. This case would have a tail of length 1, and then the inner cycles would be of length {2, 1, 2, 1 ...}.
As a result, valid 'ending states' (Z-nodes) for this graph would be after {1, 3, 4, 6, 7, 9, 10, ...} steps.
Initial tails are something they should've done, which would've foiled the naive "find the cycle lengths and use lcm" approach.
It's much closer to how real world engineering problems work where you have to do a little bit of investigation and maybe find some creative way to constrain your problem that nobody explicitly tells you about. Much prefer it to the 'here are the exact five keywords so you know what CS class algorithm you need to use' kind of thing.
I _love_ when one of these problems encourages me to reach for a tool like that. (At least, when it's one I'm already aware of and I have time to dedicate to grokking and solving the puzzle).
I used graphviz on one of last years problems and found it pretty helpful. It just feels so cool when you learn a new "spell" to help you feel out the problem.
Another example was from 2020, where I used lexx/yacc to generate a parser for the expressions in the input. This was honestly probably slower than just doing it myself but it felt so cool to solve it with a tool - and it's neat to plant little signposts in your brain that will light up when you run across a similar class of problem in your real work.
Another thing I often do is use vim to munge the input and save myself some parsing code, which is a very generically useful branch of "magic" to have under your fingers.
Object oriented programming has ruined us
Thats why this is an issue
I liked the demonstration of this approach in Chapter 6 of Robert C. Martin’s Agile Software Development: Principles, Patterns and Practices. It’s available online here:
https://people.scs.carleton.ca/~jeanpier//Fall2021/Topic%201...
What you will find is that the modules form a set of binary counters (chains of flip flops), with a number encoded into them via whether they are connected to a "hub" node of the chain (a conjunction).
You can parse the module structure and traverse the graph to extract that number. The connections to the hub are the bits of the number (1 if module is connected, 0 if not). Do that for all the counters and LCM (or multiply since they are all coincidentally co-prime) them together to get your answer.
No simulation required.
It is my favorite problem of AoC as well this year mostly because it was the first problem in many years where when part 2 popped I didn't immediately mostly know what algorithm they were going for.
In fact I didn't see people wrestling with LLMs trying to get them to solve early days and I can't believe it's impossible. My expectation is that the fad has passed, the sort of people who tried Chat GPT in 2022 because it was hot have moved on, the sort of people who resorted to it because they don't like AoC just didn't do AoC in 2023. If you enjoy these puzzles it makes sense for you to solve them, not to ask a machine to do it.
That's what many people who resorted to Z3 found frustrating. A Z3 solution to Day 24 is arguably "correct" and it certainly "works" but it's not very satisfying in terms of feeling like you achieved anything. This is why I wrote a solution which didn't do that even though it was days slower to write.
I kind of agree with your last point. I try to do all the problems without non-built in python packages myself for exactly the reason you describe. Just feels more satisfying to me.
Part 1: easy.
Apply part 1 solution to example, works.
Apply part 1 solution to real input, works.
Part 2: hard to very hard.
Apply part 2 solution to example, usually works.
Apply part 2 solution to real input, doesn't work due to time / memory constraints.
But having to look at the input to discover a pattern that isn't explained as part of the instructions always irks me.
Wouldn’t LCM be the correct/more general approach? The periods could have common factors, right?
We would probably find out if some inputs aren't co-prime because the naive multiplying solution breaks, but they could be non-prime and yet co-prime, for example 15, 14, 11, 23 is a set of numbers which are co-prime, but neither 15 nor 14 are prime.
e.g. a flip-flop (default to low) with 2 input ports, on first clock signal (time 1) both ports receives a low pulse; second clock signal (time 2) the flip-flop inspects 2 inputs and decides to give a low (two flips) at the end.
Frustratingly, this model passes the 2 examples flawlessly but fails for the real input.