How to repair a bridge, Advent of Code 2024 Day 7

After what felt like an eternity (five hours, to be precise), Day 20 part 2 finally decided to cooperate. I’m still slightly dazed from the wait, but duty calls! Today we’re tackling Day 7 of Advent of Code, picking up where we left off with Day 6 last week. Our task today is to repair a bridge so we can cross it and continue our search for the Chief Historian.

A cute illustration generated by Microsoft Copilot

Today’s challenge presents us with a different kind of problem: we’re given lists of numbers arranged in a specific format (thankfully, not a 2D puzzle today…). Each line is designed to form an equation, but the operators are absent. Our task is to test various operators to determine if the resulting equation holds true.

We use two parsing functions to process the input. The parse function first splits each line by the colon (:) character:

def parse(input: str) -> tuple[tuple[int, tuple[int, ...]], ...]:
    return tuple(
        parse_line(*line.strip().split(":")) for line in input.strip().splitlines()
    )

parse_line converts the string expected and the string of operands to integers, returning a tuple containing the integer expected and a tuple of integer operands

def parse_line(expected: str, operands: str) -> tuple[int, tuple[int, ...]]:
    return int(expected), tuple(int(item) for item in operands.strip().split(" "))

I prefer a functional programming style, and despite Python’s imperative nature, libraries like toolz/cytoolz are incredibly useful. Today, we’re using thread_first from toolz.functoolz. Here's how thread_first operates: It takes an initial value and then applies a sequence of function-argument pairs, threading the result through each step.

>>> from operator import add, mul
>>> assert thread_first(1, (add, 2), (mul, 2)) == mul(add(1, 2), 2)

In this example, thread_first starts with 1, then applies add with 2 (resulting in 3), and finally applies mul with 2 (resulting in 6). This is equivalent to mul(add(1, 2), 2).

We now define the calculate function to apply the operations. It takes a tuple of functions (funcs) and a tuple of operands (operands) as input:

def calculate(
    funcs: tuple[Callable[[int, int], int], ...], operands: tuple[int, ...]
) -> int:
    assert len(operands) - len(funcs) == 1

    return thread_first(operands[0], *(zip(funcs, operands[1:])))

The assert ensures one more operand than functions. operands[1:] provides the operands for the functions. zip and * create the function-operand pairs for thread_first, which performs the chained calculations.

Example:

>>> from operator import add, mul
>>> calculate((add, mul), (2,3,4))
20

Now we can verify each line of the input using the check_can_calibrate function. This function takes the expected result, the operands, and a tuple of possible functions as input, and returns True if any combination of functions produces the expected result, and False otherwise:

def check_can_calibrate(
    expected: int,
    operands: tuple[int, ...],
    funcs: tuple[Callable[[int, int], int], ...],
) -> bool:
    return next(
        filter(
            None,
            (
                calculate(funcs, operands) == expected
                for funcs in product(funcs, repeat=len(operands) - 1)
            ),
        ),
        False,
    )

itertools.product generates all function combinations. A generator expression checks if any combination matches the expected result. filter(None, ...) and next(..., False) efficiently find the first True result or return False if none is found.

For Part 1, we’re given only multiplication and addition operators. The puzzle asks for the sum of the expected values, where a valid equation can be formed using these operators. We implement the evaluate function to calculate this sum:

def evaluate(
    input_parsed: tuple[tuple[int, tuple[int, ...]], ...],
    funcs: tuple[Callable[[int, int], int], ...],
):
    return sum(
        expected
        for expected, operands in input_parsed
        if check_can_calibrate(expected, operands, funcs)
    )

It iterates through the parsed input and sums the expected values for which check_can_calibrate returns True.

Lastly, we assemble part 1 from what we have already built so far

import operator

def part1(input: str) -> int:
    return evaluate(parse(input), (operator.mul, operator.add))

This function parses the input using parse and then calls evaluate with the parsed data and the tuple of functions (operator.mul, operator.add), representing multiplication and addition respectively.

In Part 2, we encounter a concatenation operator that joins two numbers together. In Python, this is equivalent to using an f-string:

>>> int(f"{20}{24}")
2024
>>> int(f"{123}{45}")
12345

This effectively creates a new number by appending the digits of the second number to the end of the first number.

Alternatively, we can perform the concatenation using a mathematical formula. The number of digits in a positive integer x can be calculated using the formula:

This works because log₁₀(x) gives the power to which 10 must be raised to get x. The floor function rounds this down to the nearest integer, and adding 1 gives the number of digits. Let’s take 123 as an example:

Implementing this as the int_concat function:

def int_concat(alpha: int, beta: int) -> int:
    return alpha * (10 ** floor(log10(beta) + 1)) + beta

Performing integer concatenation mathematically avoids the overhead of string conversions. String concatenation involves memory allocation and manipulation, which is less efficient than direct integer arithmetic, especially for large numbers or many concatenations. This mathematical approach is therefore generally faster and more memory-efficient.

Lastly, we implement part 2. The only difference compared to part 1 is the addition of the int_concat operator:

def part2(input: str) -> int:
    return evaluate(parse(input), (operator.mul, operator.add, int_concat))

Ta-da! We’ve cracked Day 7. This was a relatively straightforward challenge, especially compared to the later days (Day 20 optimization is still giving me a headache 😭). Although it might not be the most performant, I prioritized readability.

That’s all for today. Happy holiday and happy new year 🎉! Fingers crossed for a better job situation next year (still #OpenToWork, ping me for collaborations!), and I shall write again, next week.