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

year2024/
day13.rs
