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

aoc/year2024/
day07.rs
