Solving Advent of Code 2021 Day 13 with a linear equation

This year I’m doing Advent of Code in Erlang. The data structures it provides are all immutable, so I have to be kinda clever if I don’t want my solutions to run too slowly. This is my solution for Day 13: Transparent Origami.

The first thing I noticed when I got the input was that all the folds are right down the middle, so I figured that instead of doing all the folds iteratively you could get the final position of a point on the paper just knowing the X and Y of the point and the X and Y offsets of the last folds.

Imagine that you have a 15x11 piece of paper.

And that the instructions tell you to:

If you were to fold that piece of paper following the instructions and then unfold it, you’d get a grid of 3x2 rectangles with a line of crease between each of them. Notice that the width and height of the rectangles are the same as the last x and y the paper was folded along.

The key thing here is understanding how these rectangles will end up looking when the whole piece of paper is folded. The top left rectangle is unchanged, but the next one on the right will be flipped horizontally, and the next one on the right will be unchanged again. The first rectangle down from the top left will be flipped vertically, and the one on its right will end up rotated by 180 degrees, because it’ll be flipped both horizontally and vertically.

Here’s a visualization, where u = unchanged, h = flipped horizontally, v = flipped vertically and r = flipped both directions.

So if you want to get the final X coordinate of a point in the 3rd rectangle right from the top left (the one at 2,0, if the first rectangle is 0,0), for example 10,0, you’d have to subtract the number of creases between that and the first rectangle, in this case 2, and then modulo by the width of the rectangle, which is 3, which gives you 2.

If you want to get the final X coordinate of a point in the 2nd rectangle though, for example 0,4, you’d have to perform the same operations as above and then subtract it from the width of the rectangle minus 1, since the rectangle is flipped horizontally.

What I did at this point was go on Wolfram Alpha to try and figure out a formula for getting the number of creases given a certain X. I’m sure you can find that out somehow. I didn’t, but what I noticed was that the function I described above formed a certain shape…

If you plot the input X as the X of the graph and the expected output numbers as the Y, you get this funny looking graph as a result. If you want to know what position a certain number will end up in, just walk the X that many times and find the number at that position.

Some X positions are empty because that’s where the creases are. If you put some pointy tips on those positions you’d end up with a proper triangle wave.

So how do we use this knowledge to solve Day 13 of Advent of Code 2021? Well, you could look at the explanation on Wikipedia and translate the general formula into your favourite language, but that implies you can read math notation. Or you could google “triangle wave function programming” and find this StackOverflow answer and then copy and paste that in your code.

Since the amplitude and the period of the wave are the same (we always advance by 1) we can get rid of the first division. You’ll also notice that the graph of the function for the width of the rectangle goes from –1 to 3 (an interval of 4), so we’ll have to add 1 to both the width and the X to use this, and in the end we’ll have to subtract 1 from the output to return it to the 0..2 interval we need.

This is what I ended up with:

It runs pretty quickly even in Erlang.