When's a mod not a mod?

Dialed: Modulo Operators in C++ and Python

One of my favorite seasonal pastimes over the past few years is the Advent of Code challenge. The thought-provoking and fun problems often lead you to learn something new such as an algorithm you’ve never used or an unexpected feature of a programming language or environment. In this post, I will examine the challenge from Day 1 of 2025 with code examples that solve each part (so consider this a spoiler alert if you’ve not completed it already).

Part 1: The Illusion of Similarity

The first part of the challenge actually masks the difference between the mod operator in Python and C++ because it only increments the password when the dial points at exactly zero. The solution is identical in principle, here it is in C++:

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main(int argc, char **argv)
{
    if (argc != 2) {
        cout << "usage: " << argv[0] <<  " input.txt" << endl;
        return 1;
    }

    ifstream f(argv[1]);
    string line;
    int pass = 0, dial = 50;
    while (getline(f, line)) {
        auto d = line[0];
        auto a = line.substr(1);
        if (d == 'L')
            dial -= stoi(a);
        else
            dial += stoi(a);
        dial %= 100;
        if (dial == 0)
            pass++;
    }
    cout << pass << endl;
}

Notice that whether you are calculating the mathematical modulo or simply the remainder, by resetting the dial using %= 100, we keep the dial from overflowing the integer type, and since we only increment the password when we arrive at 0, the logic is simple and the different implementations are hidden.

Part 2: The Remainder

For part two, the difficulty customarily jumps up a notch. In this problem, it reveals a couple of significant differences in the languages and their implementations. In this post I will drill down into two of them:

  • modulo vs remainder
  • floored division

Let’s look at a few examples of the % operator in Python and C++:

Python’s % operator gives the result the sign of the divisor, which makes it wrap around cleanly with a positive divisor:

>>> [i % 3 for i in range(-2, 3)]
[1, 2, 0, 1, 2]

C++11, on the other hand, produces a remainder with the sign of the dividend which makes the problem slightly more difficult:

$ cat mod_test.cpp
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main(int argc, char *argv[])
{
    auto wrap = vector<int>{-2, -1, 0, 1, 2};
    for (auto i = wrap.begin(); i != wrap.end(); i++)
        cout << *i << " % 3 = " << *i % 3 << endl;
    return 0;
}
$ g++ -Wall -std=c++11 -o mod_test_cpp mod_test.cpp 
$ ./mod_test_cpp 
-2 % 3 = -2
-1 % 3 = -1
0 % 3 = 0
1 % 3 = 1
2 % 3 = 2

Note that, unlike C++, Python wraps around on negative numbers (i.e. remains positive)!

C++ Solution

Firstly, let’s borrow the mod function from Stack Overflow which is absolutely good enough for our purposes since we’re using a positive divisor.

template<typename V>
V mod(const V& a, const V& b)
{
    return (a % b + b) % b;
}

This allows us to solve the problem with a simple if, else if, else if statement that would hopefully make Kernighan and Pike happy. After determining the direction the dial is turned, we have the simple case of a right-hand turn where the number will be positive and the result is trivial to calculate or a left-hand turn with a possible negative. We can use the abs function to convert negative numbers to positive and then cater to the edge case of whether or not the dial was already on 0 to avoid the off-by-one.

#include <iostream>
#include <fstream>
#include <string>
#include "../../../cpp-utils/cpp-utils.hpp"
using namespace std;

int main(int argc, char **argv)
{
    if (argc != 2) {
        cout << "usage: " << argv[0] <<  " input.txt" << endl;
        return 1;
    }

    ifstream f(argv[1]);
    string line;
    int pass = 0, dial = 50;

    while (getline(f, line)) {
        auto d = line[0];
        auto a = stoi(line.substr(1));

        auto ndial = d == 'R' ? dial + a : dial - a;

        if (d == 'R')
            pass += ndial / 100;
        else if (dial == 0)
            pass += abs(ndial / 100);
        else if (ndial <= 0)
            pass += abs(ndial / 100)+1;

        dial = mod(ndial, 100);
    }

    cout << pass << endl;
}

Python Solution

While we could cast the floating-point value returned by Python’s division operator (/) to an int which truncates the result, we can actually take advantage of the floored division feature (//) which allows us to explore a slightly different algorithm.

#!/usr/bin/env python3

import sys
from math import ceil

def main():
    if len(sys.argv) != 2:
        print(f'usage: {sys.argv[0]} input.txt')
        sys.exit(1)

    pw, dial = 0, 50
    with open(sys.argv[1], 'r') as f:
        for line in f:
            d = line[0]
            a = int(line[1:])

            ndial = dial + a if d == 'R' else dial - a

            if d == 'R':
                pw += ndial // 100
            else:
                pw += ceil(dial / 100) - ceil(ndial / 100)

            dial = ndial % 100

    print(pw)


if __name__ == '__main__':
    main()

Python’s floored division rounds towards negative infinity instead of truncating, so when we go negative, we’re actually rounding down to -1 right away. This breaks the symmetry we relied on in our C++ solution where the integer division truncates towards 0. In C++ we solved the problem in three simple branches, and while we can make use of the ceil function to round up on left-hand turns to solve the problem the exact same way, we can also explore an alternative solution. Notice that we can also use the modulo operator to reset the dial because it reflects the notion of a dial and because it allows us to make right turns in a single floored division.

Note that floating point division on the left-hand turn isn’t ideal and may potentially lead to accuracy or performance issues in production code but, for readability, it solves the problem for this blog post and the Advent of Code challenge. Because do you really want to read this? Instead, think of every call to ceil in this post to actually refer to a custom function which implements accurate int-based division as shown below:

pw += -((-dial) // 100) + ((-ndial) // 100)

To demonstrate the floor and ceiling division in Python alongside floating point division and truncated division, we can step back into our Python interpreter:

>>> from math import ceil
>>> -1//100
-1
>>> ceil(-1/100)
0
>>> -1/100
-0.01
>>> int(-1/100)
0
>>> 1//100
0
>>> ceil(1/100)
1
>>> 1/100
0.01
>>> int(1/100)
0

Part 3: The Infinite Line

Because it wouldn’t be one of my blog posts without a bonus takeaway 🙂

The keen-eyed reader may have noticed we actually don’t need to reset the dial using the mod operator in the Python solution. By treating the problem as an infinite line and counting the dial’s “0 crossings” – now, more accurately, any crossing of a multiple of 100 – we can make the following change to the algorithm to adjust the dial for each input and count right-hand turns in the inverse way to left-hand turns. Python’s ability to handle arbitrarily large integers out of the box means we don’t need to worry about overflows (though performance may suffer eventually if the numbers get big or small enough)! In C++, however, this approach would require us to consider overflow or introduce an arbitrary-precision integer type.

if d == 'R':
    pw += ndial // 100 - dial // 100
else:
    pw += ceil(dial / 100) - ceil(ndial / 100)

dial = ndial

Conclusion

Different programming language implementations can be surprising and may lend themselves to different solutions to problems. Advent of Code is a great way to learn algorithms, data structures, and improve your programming abilities. Even if you don’t have time to complete the entire challenge, drilling down into even the earliest days can lead to interesting insights!

References

Suggested posts

Sau – Hack The Box Write-up

Categories:

Write-up

Quines

Categories:

Programming

GCC compatible inline assembly with Clang

Categories:

Programming

LLDB Cheatsheet

Categories:

Programming