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//! As 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 concentation
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 concenation 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    let mut part_one = 0;
52    let mut part_two = 0;
53
54    for line in input.lines() {
55        equation.extend(line.iter_unsigned::<u64>());
56
57        // If an equation is valid for part one then it's also valid for part two.
58        if valid(&equation, equation[0], equation.len() - 1, false) {
59            part_one += equation[0];
60            part_two += equation[0];
61        } else if valid(&equation, equation[0], equation.len() - 1, true) {
62            part_two += equation[0];
63        }
64
65        equation.clear();
66    }
67
68    (part_one, part_two)
69}
70
71pub fn part1(input: &Input) -> u64 {
72    input.0
73}
74
75pub fn part2(input: &Input) -> u64 {
76    input.1
77}
78
79fn valid(terms: &[u64], test_value: u64, index: usize, concat: bool) -> bool {
80    if index == 1 {
81        test_value == terms[1]
82    } else {
83        (concat
84            && test_value % next_power_of_ten(terms[index]) == terms[index]
85            && valid(terms, test_value / next_power_of_ten(terms[index]), index - 1, concat))
86            || (test_value.is_multiple_of(terms[index])
87                && valid(terms, test_value / terms[index], index - 1, concat))
88            || (test_value >= terms[index]
89                && valid(terms, test_value - terms[index], index - 1, concat))
90    }
91}
92
93#[inline]
94fn next_power_of_ten(n: u64) -> u64 {
95    if n < 10 {
96        10
97    } else if n < 100 {
98        100
99    } else {
100        1000
101    }
102}
aoc/year2024/day07.rs

aoc/year2024/
day07.rs
