Advent of Code 2025
2025-12-01
Programming MathIt’s that time of the year again! Christmas is coming, which means Panettone, Glühwein at the markets, family time, and most of all… Advent of Code! Quoting its creator Eric Wastl,
Advent of Code is an Advent calendar of small programming puzzles for a variety of skill levels that can be solved in any programming language you like. People use them as interview prep, company training, university coursework, practice problems, a speed contest, or to challenge each other.
For me it has been a tradition for the past four years. The first year I joined was pretty brutal, I was Lanternfish’d on day 6 and didn’t go on with the subsequent days. Last year I completed all the challenges before Christmas for the first time and I had a real blast. This year I’ll try to write here about the puzzles I find more interesting. The post assumes that you have already solved the problem or at least familiarity with the statement.
Day 1: integer division and modulo
The first 3-4 days of AoC are typically almost trivial to solve, but often there are alternative solutions that are more interesting, and it was the case also with this year’s day 1. The brute-force solution, namely rotating the dial tick by tick and checking each time zero was crossed, was a good choice in this case. However, it was also possible to find the answer more efficiently using integer division and modulo. The problem stated that a dial with numbers from 0 to 99 would be rotated \(n\) steps left or right for a large number of times, and asked how many times the number zero was crossed. Given that the dial is a circular object restricted to the interval 0-99, its new value after a rotation of \(n\) steps is given by a modulo operation.
\[ \textrm{(new value)} = \mathrm{mod}\,(\textrm{(old value)} + n, 100) \]
But how many times was “\(0\)” crossed during a rotation? It depends on the initial value of the dial, the direction of the rotation, and the final value of the dial. The problem statement implies that if the dial ends at zero, that doesn’t count as a crossing. Except for this technical detail, we can use division to find out how many “complete turns” the dial makes before reaching the final position. The starting value will always be in the \([0, 99]\) range. Let’s consider counterclockwise and clockwise rotations separately.
Counterclockwise (positive) rotation
Let’s consider a counterclockwise rotation first, which will add to the current value. The only way to cross zero during this movement is if we encounter a positive multiple of 100 before the modulo. Thus, we can get the final result by dividing \(\textrm{(old value)} + n\) by 100. The result of this division should be an integer, so we need to round down or truncate the result. (Your favourite programming language will have a way to do this.) There is only one edge case: if we end exactly at a multiple of 100. In that case, the final value of the dial is zero, and this particular zero doesn’t count as crossed, according to the problem statement.
Clockwise (negative) rotation
This roation will subtract from the current value, meaning that we could end with a negative integer before doing the modulo. In this case, zero is crossed if we encounter either zero itself or negative multiples of 100 (-100, -200, and so on). Thus, we can again use integer division of \(\textrm{(old value)} + n\) (where \(n\) is negative) to find the answer. However, the logic will depend on which definition of integer division you are using. There are multiple conventions to carry out integer division, the most popular being truncated division (used in the C programming language) and floored division (used in Python). To solve the problem we can use either method, but the implementatin will be slightly different. Floored division will give \(-1\) when the number is between \(-100\) and \(0\), while truncated division will give \(0\). Remembering that the starting value is always \(\ge0\), floored division gives us a more direct answer because we can simply take the absolute value of the result as the number of crossings. With truncated division, we need to add one to the absolute number. The same edge case as before also occurs here: if we end exactly at 0 or a multiple of -100, that doesn’t count as a crossing. But now there is one additional two edge case: if the starting value of the dial is zero itself, we don’t technically cross it when we go to negative values. The integer division will not distinguish this case on its own, so we need to add special logic manually.
The difference between floored and truncated division is explained well on the Wikipedia modulo page. My solution in Julia can be found on GitHub.
Marginalia
Leave a comment