Day 16: Flawed Frequency Transmission

---

Links:

• Puzzle on adventofcode.com
• Source Code

We’re blessed with a very short puzzle today. But don’t let that concise description fool you because oh is it ever painful. It’s another one of those puzzles that lure you in with a relatively easy first part and then go “yeah now let’s scale it up”. Your cute little $\mathcal{O}(n^2)$ algorithm now has to do 7 orders of magnitude more work and even though you pray to the gods it just won’t be able to tackle it. At least not in under an hour.

What this usually means is that you have to find a way to cheat the system and calculate the result without actually putting in the work. I don’t really like this type of puzzle. In terms of challenge they’re great, but they force you to ignore parts of - if not the entire - story to solve them.

This may sound like I’m annoyed but I’m really not. Even though I wasn’t convinced by the puzzle in the context of advent of code’s story, it was still a good challenge and I’m quite fascinated by today’s puzzle.

As stated before, the first part can be solved by applying “bare” algorithm 100 times. This does take a bit of time, but it works. You could use partial sums to get it down to $N * (1 + \frac{1}{2} + \frac{1}{3} + \dotsb) = \mathcal{O}(n * log(n))$. I didn’t feel comfortable about this when I solved it though, so I just used the inefficient quadratic approach.

I solved the second part by abusing the fact that the offset points to the second half of the signal. This is really helpful because of the way the pattern is generated. For the $nth$ item, each element in the base pattern $(0, 1, 0, -1)$ is repeated $n$ times. If $N$ is the length of the signal and $n \ge \frac {N} {2}$ the pattern repeats $0$ $\lfloor\frac {N} {2}\rfloor$ times followed by $1$ repeated $\lceil\frac {N} {2}\rceil$ times. The result of an element in the signal only depends on the elements following it.

Using this we can calculate the $ith$ value in the signal $A$ using the formula:

$$A[i] = A[i] + A[i + 1] + \dotsb + A[N - 1] = \sum_{j=i}^{N} A[j]$$

This can be performed in $\mathcal{O}(n)$ and thus the second part becomes easily solvable. All we need to do is run this algorithm over the elements starting from the offset to the end, repeat it another 99 times, and then read the result from offset to offset + 8 (exclusive).

This isn’t a general solution though, it only works when the output is found in the second half of the signal. A general solution using partial sums would probably take about a minute to complete.

Edit:

I came back to this puzzle on the same day because I really couldn’t let the inefficiency of the first part go. I played around with the idea of partial sums and got it working.

To give a brief overview of how it works: First, a list where each element contains the running sum of the signal values up to that point is constructed.

$$S[i] = A[0] + A[1] + \dotsb + A[i] = \sum_{j=0}^{i} {A[j]}$$

Then the code finds the relevant ranges where the pattern doesn’t return 0. The sum of a pattern range is easily determined using the running sums by taking the running sum at the end of the range r and subtracting the one at the start of the range l ($S[r] - S[l]$). This sum is then multiplied by the pattern’s value at that position and added to the total.

The first part now runs ~70 times faster for the standard input length of 650. I didn’t touch the second part though.

---

Overview
Previous day Next day