Advent of Code 2024 - Day 13: Claw Contraption

:: 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
 
from advent import parse, ints
import numpy as np

input   = parse(13, ints, sep='\n\n')
epsilon = 0.0001
err     = 10000000000000

def cost(a00, a10, a01, a11, b0, b1, offset, limit):
    coefficients = np.array([[a00, a01],[a10, a11]])
    unknowns     = np.array([b0 + offset, b1 + offset])
    a, b         = np.linalg.solve(coefficients, unknowns)
    a_int, b_int = round(a), round(b)

    if 0 <= a_int <= limit and 0 <= b_int <= limit and abs(a - a_int) < epsilon and abs(b - b_int) < epsilon:
        return 3 * a_int + b_int

def solve(offset=0, limit=100):
    return sum(c for t in input if (c := cost(*t, offset, limit)))

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

assert solve()         == 29436
assert solve(err, err) == 103729094227877

Parsing

We’re given textual input with lots of information, but we only care about the numbers in this case, so passing the ints() higher order function to the parse() function gives us just the numbers in the input:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
input   = parse(13, ints, sep='\n\n')

----------------------------------------------------------------------------------------------------
day13.txt ➜ 20989 chars, 1279 lines; first 3 lines:
----------------------------------------------------------------------------------------------------
Button A: X+43, Y+21
Button B: X+16, Y+31
Prize: X=6735, Y=9135

Button A: X+52, Y+55
Button B: X+69, Y+11
Prize: X=2798, Y=1100
----------------------------------------------------------------------------------------------------
parse(13) ➜ 320 entries:
----------------------------------------------------------------------------------------------------
((43, 21, 16, 31, 6735, 9135), (52, 55, 69, 11, 2798, 1100), (13, 32,  ... 35, 42, 26, 13022, 9764))
----------------------------------------------------------------------------------------------------

Solution

Let’s consider the first section of information:

Button A: X+43, Y+21
Button B: X+16, Y+31
Prize: X=6735, Y=9135

From this, we an form two equations:

43A + 16B = 6735
21A + 31B = 9135

One option would be to solve this manually by solving for A in terms of B using one equation, and then substitute the result for A in the second equation, and solve for B, etc. However, I chose Python for this year’s Advent of Code because I’m interested in using it for data science and artificial intelligence. One of the libraries that’s very useful in this area is numpy, so I used numpy’s linear algebra capabilities to solve the equations.

Here’s the cost() function:

1
2
3
4
5
6
7
8
 
def cost(a00, a10, a01, a11, b0, b1, offset, limit):
    coefficients = np.array([[a00, a01],[a10, a11]])
    unknowns     = np.array([b0 + offset, b1 + offset])
    a, b         = np.linalg.solve(coefficients, unknowns)
    a_int, b_int = round(a), round(b)

    if 0 <= a_int <= limit and 0 <= b_int <= limit and abs(a - a_int) < epsilon and abs(b - b_int) < epsilon:
        return 3 * a_int + b_int

We pass in the parsed values as is, so we need to select the appropriate ones for placement into the coefficient matrix and unknowns vector, then it’s simply a matter of calling np.linalg.solve() to solve the system of linear equations.

After that, we need to verify the following:

  • a is within the valid range
  • b is within the valid range
  • a is within epsilon of an integer
  • b is within epsilon of an integer

If everything passes, we return the case as 3 * A + B

The solve() function accepts an optional (for part 2) offset and limit, and then sums all the valid costs.

1
2
 
def solve(offset=0, limit=100):
    return sum(c for t in input if (c := cost(*t, offset, limit)))

For part 2, we simply pass the calibration error as the offset, and since we don’t know the exact limit, other than that it’s large, we just use the same value for the limit to simplify the code:

1
2
 
solve()
solve(err, err)

New Python Concepts

  • import <lib> as <label>
  • np.array()
  • np.linalg.solve()
  • round()
  • Numpy

Conclusion

As expected, Numpy made today’s puzzle simple. I’m not sure if I’ll get much opportunity to use more of Python’s data science and AI libraries on the other puzzles, but it was fun to be able to on this one.

Postscript

Here’s a version using sympy instead of numpy. It was 615 times slower, so maybe not the best tool for this particular problem, but could be very handy for others:

 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
from sympy import symbols, Eq, solve

input   = parse(13, ints, sep='\n\n', print_lines=3)
epsilon = 0.0001
err     = 10000000000000

def cost(a0, a1, a2, a3, b0, b1, offset, limit):
    x, y = symbols('x y')
    eq1 = Eq(a0*x + a2*y, b0 + offset)
    eq2 = Eq(a1*x + a3*y, b1 + offset)
    solution = solve((eq1, eq2), (x, y))
    a, b = solution[x], solution[y]
    a_int, b_int = round(a), round(b)

    if 0 <= a_int <= limit and 0 <= b_int <= limit and abs(a - a_int) < epsilon and abs(b - b_int) < epsilon:
        return 3 * a_int + b_int

def run(offset=0, limit=100):
    return sum(c for t in input if (c := cost(*t, offset, limit)))

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

assert run()         == 29436
assert run(err, err) == 103729094227877