Advent of Code

In today’s Advent of Code puzzle, we have a reasonably easy solution that is not super efficient, but I did learn a few things along the way, which is also the point of doing these things. Aside from the fact that they are fun, I mean.

Day 7, part 1

Each line has the form: ANSWER: OP1 OP2 ... OPN. We have to find for each line if there is a way to put + and * signs between the operands to get the answer, knowing that the evaluation will always take place left-to-right. So: 190 = 10*19 is correct. The final answer to the puzzle is the sum of all answers with at least one way of combining the operands that works.

As usual, we begin by parsing the data, reusing the load_as_str function I previously define to just get the content of the file as a string. Splitting by : then by , we get a list of tuples of the form (ANSWER, [OP1, OP2..., OPN]).

def load_operations():
    data = load_as_str('day7').strip()
    lines = data.split('\n')
    operations = []
    for l in lines:
        ans, operands = l.split(':')
        operands = operands.strip().split(' ')
        operations.append((int(ans), [int(o) for o in operands]))
    return operations

Now we have to test all the different combinations of + and *. If we have n operands, we will have n-1 signs, and therefore 2^(n-1) possible combinations. I initially tried to do something with itertools.accumulate, but I initially couldn’t find a non-cursed way of making the operator in accumulate change during the accumulation. And it was not very efficient anyway. So I settled on pre-generating all possible binary patterns for the lengths of operands list that are present in the dataset. To do that, I iterated integer values and convert them to binary text representation, and then converted 0s to operator.add and 1s to operator.mul.

def generate_all_binary_patterns(n: int):
    patterns = []
    for i in range(0, 2**n):
        cur_pattern = [operator.add]*n
        b = bin(i)[2:]
        for j, k in enumerate(b[::-1]):
            if k == '1':
                cur_pattern[n-1-j] = operator.mul
        patterns.append(cur_pattern)
    return patterns

operations = load_operations()
ns = set([len(ops)-1 for ans, ops in operations])
all_patterns = {n: generate_all_binary_patterns(n) for n in ns}

Then it’s a matter of applying all those patterns in order until we hit one where the total matches the answer.

def accfn(operands: list[int], operators: list, target: int):
    total = operands[0]
    for v, op in zip(operands[1:], operators):
        total = op(total, v)
        if total > target:
            break
    return total


def verify_all_operations(operations, all_patterns):
    total_correct = 0
    for ans, ops in operations:
        patterns = all_patterns[len(ops)-1]
        for pattern in patterns:
            if accfn(ops, pattern, ans) == ans:
                total_correct += ans
                break
    print(total_correct)

Part 2: ternary combinations?

For part 2, a new operator appears, which concatenates two number together. So we define the operation:

def concat(a, b):
    return int(str(a)+str(b))

And now instead of generating binary patterns we have to generate ternary patterns. I found some code on StackOverflow to convert an integer to ternary string, because I didn’t want to spend too much time on that solution as I knew I’d be coming back to find something a bit less clunky later. Still, I wanted to check that the rest of the code was reasonably resistant to change.

def ternary (n):
    """https://stackoverflow.com/a/34559825"""
    if n == 0:
        return '0'
    nums = []
    while n:
        n, r = divmod(n, 3)
        nums.append(str(r))
    return ''.join(reversed(nums))


def generate_all_ternary_patterns(n: int):
    patterns = []
    for i in range(0, 3**n):
        cur_pattern = [operator.add]*n
        t = ternary(i)
        for j, k in enumerate(t[::-1]):
            if k == '1':
                cur_pattern[n-1-j] = operator.mul
            if k == '2':
                cur_pattern[n-1-j] = concat
        patterns.append(cur_pattern)
    return patterns

Replacing the binary function by the ternary function to generate all patterns worked easily (albeit not quickly), which was a relief. Altogether I think this was the challenge that I solved the quickest. But I did come back for some refactoring later…

Some refactoring later…

I didn’t like having to make a whole new function to add the new operator. I wanted to ideally just have to provide the list of operations at the input of the system, and then have the rest generic. Thanks to Juhis’ solution I realized that I could do that with itertools.product. I knew itertools was the way, I just never used that one before. Such a great library.

def generate_all_patterns(operators: list, n: int):
    return list(itertools.product(operators, repeat=n))

We can generate all combinations of size n of the operators, which is great. Our main function becomes:

def verify_all_operations(operations, operators):
    ns = set([len(ops)-1 for ans, ops in operations])
    all_patterns = {n: generate_all_patterns(operators, n) for n in ns}
    
    total_correct = 0
    for ans, ops in operations:
        operators = all_patterns[len(ops)-1]
        for pattern in operators:
            if accfn(ops, pattern, ans) == ans:
                total_correct += ans
                break
    print(total_correct)

operations = load_operations('')
verify_all_operations(operations, [operator.add, operator.mul, concat])

Bonus cursed version

class SwitchAccumulator:
    def __init__(self, pattern: list):
        self.pattern = pattern.copy()
    
    def switchop(self, a, b):
        return self.pattern.pop(0)(a, b)

...

def verify_all_operations(operations, operators):
    ...
            total = list(itertools.accumulate(ops, SwitchAccumulator(pattern).switchop)).pop()
            if total == ans:
                total_correct += ans
                break
    print(total_correct)