aoc/year2024/
day07.rs

1//! # Bridge Repair
2//!
3//! The equations can be validated using a recursive solution that checks all possible combinations
4//! of operators. However, the number of states to check grows exponentially as 2ⁿ in part one
5//! and 3ⁿ in part two.
6//!
7//! A much faster approach works in reverse from the end of the equation to prune as many states
8//! as possible by checking which operations are possible. For example:
9//!
10//! ```none
11//! Test Value: 123456
12//! Equation: 2 617 56
13//! Addition is possible as 123456 >= 56
14//! Multiplication is not possible as 56 is not a factor of 123456
15//! Concatenation is possible as 1234 || 56 = 123456
16//! ```
17//!
18//! Following the concatenation branch and applying an inverse concatenation
19//! (the full solution would also follow the addition branch):
20//!
21//! ```none
22//! Test Value: 1234
23//! Equation: 2 617
24//! Addition is possible as 1234 >= 617
25//! Multiplication is possible as 2 * 617 = 1234
26//! Concatenation is not possible as 1234 does not end in 617
27//! ```
28//!
29//! Following the multiplication branch:
30//!
31//! ```none
32//! Test Value: 2
33//! Equation: 2
34//! ```
35//!
36//! The test value is equal to the last term which means that the equation is valid.
37//!
38//! Inverse concatenation can be implemented without time-consuming conversion to or from
39//! strings by dividing the left term by the next power of ten greater than the right term.
40//! For example:
41//!
42//! * 7 || 9 => 79 => 79 / 10 => 7
43//! * 12 || 34 => 1234 => 1234 / 100 => 12
44//! * 123 || 789 => 123789 => 123789 / 1000 => 123
45use crate::util::parse::*;
46
47type Input = (u64, u64);
48
49pub fn parse(input: &str) -> Input {
50    let mut equation = Vec::new();
51
52    input.lines().fold((0, 0), |(part_one, part_two), line| {
53        equation.clear();
54        equation.extend(line.iter_unsigned::<u64>());
55
56        let (test_value, last) = (equation[0], equation.len() - 1);
57
58        // If an equation is valid for part one then it's also valid for part two.
59        if valid(&equation, test_value, last, false) {
60            (part_one + test_value, part_two + test_value)
61        } else if valid(&equation, test_value, last, true) {
62            (part_one, part_two + test_value)
63        } else {
64            (part_one, part_two)
65        }
66    })
67}
68
69pub fn part1(input: &Input) -> u64 {
70    input.0
71}
72
73pub fn part2(input: &Input) -> u64 {
74    input.1
75}
76
77fn valid(terms: &[u64], test_value: u64, index: usize, concat: bool) -> bool {
78    if index == 1 {
79        test_value == terms[1]
80    } else {
81        let pow = next_power_of_ten(terms[index]);
82        (concat
83            && test_value % pow == terms[index]
84            && valid(terms, test_value / pow, index - 1, concat))
85            || (test_value.is_multiple_of(terms[index])
86                && valid(terms, test_value / terms[index], index - 1, concat))
87            || (test_value >= terms[index]
88                && valid(terms, test_value - terms[index], index - 1, concat))
89    }
90}
91
92#[inline]
93fn next_power_of_ten(n: u64) -> u64 {
94    if n < 10 {
95        10
96    } else if n < 100 {
97        100
98    } else {
99        1000
100    }
101}
aoc/year2024/day07.rs

aoc/year2024/
day07.rs
