aoc/year2024/day13.rs
1//! # Claw Contraption
2//!
3//! Each claw machine is a system of two linear equations:
4//!
5//! ```none
6//! (Button A X) * (A presses) + (Button B X) * (B presses) = Prize X
7//! (Button A Y) * (A presses) + (Button B Y) * (B presses) = Prize Y
8//! ```
9//!
10//! Shortening the names and representing as a matrix:
11//!
12//! ```none
13//! [ ax bx ][ a ] = [ px ]
14//! [ ay by ][ b ] = [ py ]
15//! ```
16//!
17//! To solve we invert the 2 x 2 matrix then premultiply the right column.
18use crate::util::iter::*;
19use crate::util::parse::*;
20
21type Claw = [i64; 6];
22
23pub fn parse(input: &str) -> Vec<Claw> {
24 input.iter_signed().chunk::<6>().collect()
25}
26
27pub fn part1(input: &[Claw]) -> i64 {
28 input.iter().filter_map(|row| play(row, 0)).sum()
29}
30
31pub fn part2(input: &[Claw]) -> i64 {
32 input.iter().filter_map(|row| play(row, 10_000_000_000_000)).sum()
33}
34
35/// Invert the 2 x 2 matrix representing the system of linear equations.
36fn play(&[ax, ay, bx, by, px, py]: &Claw, offset: i64) -> Option<i64> {
37 let (px, py) = (px + offset, py + offset);
38
39 let det = ax * by - ay * bx;
40 let a = by * px - bx * py;
41 let b = ax * py - ay * px;
42
43 // If determinant is zero there's no solution. Integer solutions only.
44 (det != 0 && a % det == 0 && b % det == 0).then(|| (3 * a + b) / det)
45}