year2024/
day13.rs

1use utils::geometry::Vec2;
2use utils::prelude::*;
3
4/// Solving linear systems.
5#[derive(Clone, Debug)]
6pub struct Day13 {
7    machines: Vec<Machine>,
8}
9
10#[derive(Copy, Clone, Debug)]
11struct Machine {
12    button_a: Vec2<u64>,
13    button_b: Vec2<u64>,
14    prize: Vec2<u64>,
15}
16
17impl Day13 {
18    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
19        Ok(Self {
20            machines: parser::u64()
21                .with_prefix("Button A: X+")
22                .then(parser::u64().with_prefix(", Y+"))
23                .then(parser::u64().with_prefix(parser::eol().then("Button B: X+")))
24                .then(parser::u64().with_prefix(", Y+"))
25                .then(parser::u64().with_prefix(parser::eol().then("Prize: X=")))
26                .then(parser::u64().with_prefix(", Y="))
27                .with_suffix(parser::eol())
28                .map_res(|(ax, ay, bx, by, px, py)| {
29                    let m = Machine {
30                        button_a: Vec2::new(ax, ay),
31                        button_b: Vec2::new(bx, by),
32                        prize: Vec2::new(px, py),
33                    };
34
35                    // Check the two buttons are linear independent, meaning there is only one
36                    // solution for the linear equations.
37                    if det(m.button_a, m.button_b) == 0 {
38                        Err("expected buttons to be linearly independent")
39                    } else {
40                        Ok(m)
41                    }
42                })
43                .parse_lines(input)?,
44        })
45    }
46
47    #[must_use]
48    pub fn part1(&self) -> u64 {
49        self.machines
50            .iter()
51            .map(|m| m.required_tokens().unwrap_or(0))
52            .sum()
53    }
54
55    #[must_use]
56    pub fn part2(&self) -> u64 {
57        self.machines
58            .iter()
59            .map(|&(mut m)| {
60                m.prize += Vec2::new(10000000000000, 10000000000000);
61                m.required_tokens().unwrap_or(0)
62            })
63            .sum()
64    }
65}
66
67impl Machine {
68    fn required_tokens(&self) -> Option<u64> {
69        self.solve().map(|(a, b)| a * 3 + b)
70    }
71
72    fn solve(&self) -> Option<(u64, u64)> {
73        // https://en.wikipedia.org/wiki/Cramer%27s_rule#Explicit_formulas_for_small_systems
74        let det_denominator = det(self.button_a, self.button_b);
75        if det_denominator == 0 {
76            return None;
77        }
78
79        let det_a = det(self.prize, self.button_b);
80        let det_b = det(self.button_a, self.prize);
81        if det_a % det_denominator != 0 || det_b % det_denominator != 0 {
82            return None;
83        }
84
85        if let Ok(count_a) = (det_a / det_denominator).try_into()
86            && let Ok(count_b) = (det_b / det_denominator).try_into()
87        {
88            return Some((count_a, count_b));
89        }
90
91        None
92    }
93}
94
95fn det(a: Vec2<u64>, b: Vec2<u64>) -> i64 {
96    (a.x as i64) * (b.y as i64) - (b.x as i64) * (a.y as i64)
97}
98
99examples!(Day13 -> (u64, u64) [
100    {file: "day13_example0.txt", part1: 480},
101]);
year2024/day13.rs

year2024/
day13.rs
