Advent of Code 2024 - Day 7: Bridge Repair

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
from advent import parse, ints

input = parse(7, ints)

def evaluate(x, op, y):
    match op:
        case '*':  return x * y
        case '+':  return x + y
        case '||': return int(str(x) + str(y))

def is_valid(ops, answer, result, operands):
    if  result > answer:
        return False
    elif len(operands) == 0:
        return result == answer
    else:
        return any(is_valid(ops, answer, evaluate(result, op, operands[0]), operands[1:]) for op in ops)

def solve(*operators):
    return sum(lst[0] for lst in input if is_valid(operators, lst[0], lst[1], lst[2:]))

# ---------------------------------------------------------------------------------------------

assert solve('*','+')      == 2664460013123   # Part 1
assert solve('*','+','||') == 426214131924213 # Part 2

Parsing

Today’s input has a list of numbers on each line. The first number is the answer, and the remaining numbers are operands. Here’s the output of parse(7, ints):

----------------------------------------------------------------------------------------------------
day07.txt ➜ 24522 chars, 850 lines; first 7 lines:
----------------------------------------------------------------------------------------------------
5519591: 5 519 507 83
28956735990: 2 892 65 427 3 389
1325281: 995 826 828 5 7 8 1
215986656838: 545 8 9 604 20 82
5790512: 8 7 16 10 91 776
12246166: 2 41 72 4 30 3 722 23
22104: 35 604 8 1 431 520 4
----------------------------------------------------------------------------------------------------
parse(7) ➜ 850 entries:
----------------------------------------------------------------------------------------------------
((5519591, 5, 519, 507, 83), (28956735990, 2, 892, 65, 427, 3, 389), ( ... 34, 539, 53, 66, 7, 869))
----------------------------------------------------------------------------------------------------

Solution

My first approach (see day07_decoupled.py decoupled the formation of expressions and evaluation at the cost of being inefficient. The inefficiency was primarily due to not being able to short circuit the evaluation. Our operators all increase the result value, so if the result of a partially evaluated expression is already greater than the answer, we can return False immediately.

The new solution is shorter, still readable, and 7x faster than the original version. It has three components:

evaluate : evaluate an expression of the form: x op y:

1
2
3
4
5
 
def evaluate(x, op, y):
    match op:
        case '*':  return x * y
        case '+':  return x + y
        case '||': return int(str(x) + str(y))

is_valid : indicate whether any of the expressions evaluate to the answer

1
2
3
4
5
6
7
 
def is_valid(ops, answer, result, operands):
    if  result > answer:
        return False
    elif len(operands) == 0:
        return result == answer
    else:
        return any(is_valid(ops, answer, evaluate(result, op, operands[0]), operands[1:]) for op in ops)

solve : sum all the answers for valid equations

1
2
 
def solve(operators):
    return sum(lst[0] for lst in input if is_valid(operators, lst[0], lst[1], lst[2:]))

With that in place, the two parts are easy, differing only in the possible operators:

  • Part 1: solve(('*','+'))
  • Part 2: solve(('*','+','||'))

New Python Concepts

  • Sequence concatenation (1,2) + (3,4) -> (1,2,3,4)

Conclusion

I’m pleased with both the readability and efficiency of my final solution. Python continues to be pragmatic!

Postscript

I noticed another person’s solution using higher order functions (something I probably would’ve naturally done in Racket), so I converted my solution to use lambdas - I like it better:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
from advent import parse, ints

input = parse(7, ints)

plus = lambda x, y: x + y
mult = lambda x, y: x * y
conc = lambda x, y: int(str(x) + str(y))

def is_valid(ops, answer, result, operands):
    if  result > answer:
        return False
    elif len(operands) == 0:
        return result == answer
    else:
        return any(is_valid(ops, answer, op(result, operands[0]), operands[1:]) for op in ops)

def solve(*operators):
    return sum(lst[0] for lst in input if is_valid(operators, lst[0], lst[1], lst[2:]))

# ---------------------------------------------------------------------------------------------

assert solve(mult, plus)       == 2664460013123   # Part 1
assert solve(mult, plus, conc) == 426214131924213 # Part 2

Postscript 2

Finally, a port of the previous Python version into Racket:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#lang racket

(require "./advent.rkt")

(define input (parse-aoc 7 numbers))

(define conc (λ (x y) (string->number (string-append (number->string x) (number->string y)))))

(define (is-valid? ops answer result operands)
  (cond [ (> result answer) #f                ]
        [ (null? operands)  (= answer result) ]
        [ else (ormap (λ (op)
                        (is-valid? ops answer (op result (car operands)) (cdr operands)))
                      ops) ]))

(define (solve . operators)
  (~> (filter (λ (lst)
                (is-valid? operators (car lst) (cadr lst) (cddr lst)))
              input)
      (map car _)
      (apply + _)))

;; --------------------------------------------------------------------------------------------

(check-equal? (solve * +) 2664460013123)
(check-equal? (solve * + conc) 426214131924213)