Advent of Code (in MiniScript), Day 20

Welcome back to my series of Advent of Code solutions in MiniScript! Day 20 was an interesting one. It looked so easy, but ended up taking me significant time.

The problem gives you a series of numbers, which we are to treat as a circular buffer. For each number, we shift it forward or back in the buffer according to its value. So if the number is 3, we shift it forward three places; if it's -12, we shift it back twelve places, always wrapping around as needed.

Sounds pretty easy, right? There are some potential off-by-one errors lurking in the wrap-around, but those are pretty easy to catch through testing. I coded up a solution that worked on the test problem quite quickly, ran it on the full input file, and confidently pasted the answer into the challenge page.

My answer was wrong.

There followed a good hour of checking and double-checking my code, writing a completely different (and less efficient) way to shift the numbers around and debugging that just so I could compare it to the first way, coming up with and trying half a dozen additional incorrect answers (all of which generated the right answer on the sample data). If I still had hair, I would've been tearing it out!

Finally, I had a horrifying realization. The challenge says

The numbers should be moved in the order they originally appear in the encrypted file. Numbers moving around during the mixing process do not change the order in which the numbers are moved.

What does this mean? I took it to mean: if the fifth number in the original input was 42, then we should find 42 in the mixed buffer, wherever that might be, and move it 42 positions from there.

This obviously implies that there is only one 42 in the input. That seems like such a reasonable assumption that my brain accepted it without question, and for the next hour, I worked as if it were a fact, a stated part of the problem spec. Then I realized that the spec never actually came out and said this. With trepidation I did:

lines here is the set of values read from the input file. mapUtil.fromTo is just a quick way to make a map out of two lists; in this case, I mapped each number to itself, which is pointless except that it eliminates duplicates. So, m.len shows how many unique numbers there are.

5000 numbers in the input file, but only 3636 unique numbers.

OK, so my assumption was wrong, and my approach of just searching the mixed numbers for the next one to do was also wrong. It worked fine on the sample data because there were no duplicates, but failed miserably on the real input data.

To do it properly, we need to either keep our buffer as little maps or lists that contain the value and the original index; or keep a separate list of indexes, and mix those instead of (or in addition to) the values. I chose to keep a separate index list, and mix both lists.

So the working code is:

import "mapUtil"
import "listUtil"
import "aoc"

partTwo = false
if 1 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if lines == null then
    print "Unable to read: " + fname
    exit
end if
if not lines[-1] then lines.pop

lines.apply @val
msg = lines
if partTwo then msg.multiplyBy 811589153

list.moveFromTo = function(idxA, idxB)
    value = self[idxA]
    self.remove idxA
    if idxB > idxA then self.insert idxB-1, value else self.insert idxB, value
end function

indexes = range(0, msg.len-1)

for iteration in range(1, 1 + 9 * partTwo)
    print "Iteration " +  iteration + "..."
    for idx in range(0, msg.len-1)
        oldIdx = indexes.indexOf(idx)
        value = msg[oldIdx]
        if value == 0 then continue
        steps = value % (msg.len - 1)
        idx = (oldIdx + steps + (steps>0)) % msg.len
        if idx < 0 then idx = idx + msg.len
        msg.moveFromTo oldIdx, (idx % msg.len)
        indexes.moveFromTo oldIdx, (idx % msg.len)
    end for
end for

result = []
zeroIdx = msg.indexOf(0)
result.push msg[(zeroIdx + 1000) % msg.len]
result.push msg[(zeroIdx + 2000) % msg.len]
result.push msg[(zeroIdx + 3000) % msg.len]

print "key numbers: " + result
print "final answer: " + result.sum

Part Two was a trivial modification to the first part; we only need to multiply the values by a big number, and do the mixing ten times instead of one. The code above handles both cases (depending on the value of partTwo in line 5).

Results and Conclusions

Because I wasted so much time before realizing my mistake, it took me an hour and a half to solve Part 1, giving me a rank of 2416. Part 2 took only a few additional minutes, bumping my rank up to 2016.

It's amazing how, as we are interpreting something like a problem statement, we can make an assumption without even consciously realizing it. And then we treat that assumption as if it's reality. Indeed, I find that when somebody has a bug they don't understand, it's usually not something like a typo or incorrect syntax; it's something they are assuming, that is not actually true.

The art of debugging is mostly the art of checking all your assumptions, and the hardest one to check is always the one you're not even thinking about.