Day 07

• Puzzle for the day
• Full code for my solution

Them pesky elephants have stolen all the mathematical operators the engineers need to calculate calibrations for a rope bridge safety.

We gotta find those operators and see if we can put them back in the right order.

Read input

Today our input is a series of equations (missing operators) and their results:

190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20

To parse these in, I’m splitting at : to separate result from the equation, split the equation part by white space and convert everything to integers:

def map_fn(line):
    result, numbers = line.split(": ")
    result = int(result)
 
    numbers = [int(num) for num in numbers.split()]
 
    return result, numbers

Part 1

In the first part, we have two mathematical operations: + for addition and * for multiplication. For each equation, we need to figure out if there’s a way to put those between the numbers to reach the correct result.

from itertools import product
 
def is_solvable(result, numbers):
    operators = ["*", "+"]
 
    for operator_order in product(operators, repeat=len(numbers) - 1):
        total = numbers[0]
        for idx, num in enumerate(numbers[1:]):
            if operator_order[idx - 1] == "+":
                total += num
            elif operator_order[idx - 1] == "*":
                total *= num
            if total > result:
                break
        if total == result:
            return True
    return False

Python’s wonderful itertools module has a great function product that can help create all the possible combinations we need. We give the repeat keyword argument as one less than the amount of numbers (as there are one less empty spot as there are numbers) and it will happily churn out a ton of possible operation orders.

I then go through number by number and based on the operation, calculate the next total.

If at any point, the current total is larger than the desired result, we bail out. This is why I also put multiplication first in the operators because it results in higher numbers faster and thus we could save a couple of iterations down the line.

def part_1():
    equations = read_input(7, map_fn)
 
    calibration_result = 0
    for result, numbers in equations:
        if is_solvable(result, numbers):
            calibration_result += result
 
    print(f"Part 1: {calibration_result}")

To put everything together, I read in the input and go through each equation. If it is solvable, I add the result to the total and we get the result!

Part 2

The second part offers a classic Advent of Code twist: adding a third operator which suddenly increases the amount of the possible orders of operators to so high that using the same approach as in the first part, things slow down significantly.

Let’s start with that anyway since that’s how I did it.

def is_solvable_with_concatenation(result, numbers):
    operators = ("*", "||", "+")
 
    for operator_order in product(operators, repeat=len(numbers) - 1):
        total = numbers[0]
        for idx, num in enumerate(numbers[1:]):
            if operator_order[idx - 1] == "+":
                total += num
            elif operator_order[idx - 1] == "*":
                total *= num
            elif operator_order[idx - 1] == "||":
                total = int(f"{total}{num}")
            if total > result:
                break
 
        if total == result:
            return True

As a code change, this one is very small. We add the || operator that concatenates the two numbers together and add the corresponding calculation into the if clauses.

def part_2():
    equations = read_input(7, map_fn)
 
    calibration_result = 0
    for result, numbers in equations:
        if is_solvable_with_concatenation(result, numbers):
            calibration_result += result
 
    print(f"Part 2: {calibration_result}")

By running this the same way we did with part 1 takes the time spent from 0.32 seconds to a whopping 28 seconds.

I figured one way to optimise it a bit is to have the first part return all the solved equations and then skip their calculations in the second part as we already know them.

I changed the original part to:

def part_1():
    equations = read_input(7, map_fn)
 
    solvable = set()
    for result, numbers in equations:
        if is_solvable(result, numbers):
            solvable.add((result, tuple(numbers)))
 
    calibration_result = sum(res for res, _ in solvable)
    print(f"Part 1: {calibration_result}")
 
    return solvable

and then the second part to

def part_2(solved):
    equations = read_input(7, map_fn)
 
    calibration_result = 0
    for result, numbers in equations:
        if (result, tuple(numbers)) in solved:
            continue
        if is_solvable_with_concatenation(result, numbers):
            calibration_result += result
 
    calibration_result += sum(r for r, _ in solved)
 
    print(f"Part 2: {calibration_result}")

Once I run them together, feeding the output of part 1 to the part 2 function, the time spent drops a few seconds to roughly 24 seconds.

But I didn’t originally solve it quite like that. Instead of storing a tuple of result, numbers, I stored only the result because I had ran a bash script to examine the input and had come to the incorrect conclusion that each result would only appear once. But there was one tiny equation worth 241 that was skipped by my initial code and caused such a nasty and hard to debug bug. Once I figured that out, the above code was the one that brought me the second star.

I normally never look into the input file for these kinds of tricks and today taught me the hard way that I should not try that again either.

Anyway, my solution is very slow because creating all the operator orders and applying them all to all equations just takes a lot of time.

As I then looked at others’ solutions after finishing mine, I learned that a recursive solution to this would have been way more efficient, dropping the run time to just a couple of seconds. Having seen and tested the solution, I can’t claim I would have reached that conclusion myself. Had I thought of recursion, I may have been able to come up with a solution but I poisoned that well already.

Here’s one recursive solution by Toni, adapted to match the variable names that I used above so you can see how it would work.

def is_solvable_with_recursion(result, numbers):
    max_length = len(numbers)
 
    def is_solvable(total, length):
        if length == max_length:
            return total == result
 
        if total > result:
            return False
 
        num = numbers[length]
        if is_solvable(total + num, length + 1):
            return True
        elif is_solvable(total * num, length + 1):
            return True
        elif is_solvable(int(f"{total}{num}"), length + 1):
            return True
        else:
            return False
 
    return is_solvable(numbers[0], 1)

Today was one of them “I don’t recognise the right trick” puzzles for me. I can cook up a naive solution that takes time but probably would have never found the right direction for an efficient one.

Luckily the naive solution was still under half a minute which is still wait-able time and is within the realms of “fast enough that I can run it a few times to check my refactoring still returns the right result”.