Advent of Code 2024, Day 7

If you check the operands from the right, you can prune recursion branches, because you know that

• a concatenation with the last operand can only have happened if the result ends in the same digits as the operand,
• a multiplication with the last operand can only have happened if the result is divisible by the operand, and
• an addition with the last operand can only have happened if the result is not less than the operand.

I only found this tip later.

Part 1, from the left (0.1 seconds)

import sys

def check(n, acc, xs):
    if xs == []: return n == acc
    return check(n, acc+xs[0], xs[1:]) or check(n, acc*xs[0], xs[1:])

rows = []
with open(sys.argv[1]) as f:
    for line in f:
        xs = line.split()
        n, xs = xs[0][:-1], xs[1:]
        n, xs = int(n), [int(x) for x in xs]
        rows.append((n, xs))

s = 0
for (n, xs) in rows:
    if check(n, 0, xs):
        s += n
print(s)

Part 2, from the left (6 seconds)

import sys

def check(n, acc, xs):
    if acc > n: return False
    if xs == []: return n == acc
    a = acc + xs[0]
    b = acc * xs[0]
    c = int(str(acc) + str(xs[0]))
    return check(n, a, xs[1:]) or check(n, b, xs[1:]) or check(n, c, xs[1:])

rows = []
with open(sys.argv[1]) as f:
    for line in f:
        xs = line.split()
        n, xs = xs[0][:-1], xs[1:]
        n, xs = int(n), [int(x) for x in xs]
        rows.append((n, xs))

s = 0
for (n, xs) in rows:
    if check(n, 0, xs):
        s += n
print(s)

Part 2, from the right (0.03 seconds)

import sys

def is_cat(xs, x, n):
    n, x = str(n), str(x)
    if not n.endswith(x): return False
    n = int("0" + n[:-len(x)])
    return check(n, xs)

def is_mul(xs, x, n):
    n, mod = divmod(n, x)
    return mod == 0 and check(n, xs)

def is_add(xs, x, n):
    n -= x
    return n >= 0 and check(n, xs)

def check(n, xs):
    xs, x = xs[:-1], xs[-1]
    if not xs: return n == x
    return is_cat(xs, x, n) or is_mul(xs, x, n) or is_add(xs, x, n)

rows = []
with open(sys.argv[1]) as f:
    for line in f:
        xs = line.split()
        n, xs = xs[0][:-1], xs[1:]
        n, xs = int(n), [int(x) for x in xs]
        rows.append((n, xs))

s = 0
for (n, xs) in rows:
    if check(n, xs):
        s += n
print(s)

2024-12-23