aoc/year2023/
day06.rs

1//! # Wait For It
2//!
3//! We can solve analytically using the quadratic formula.
4//! * `x` is time spent holding the button.
5//! * `t` is the duration of the race.
6//! * `d` is the record distance.
7//!
8//! Then the distance travelled is:
9//!
10//! * `x * (t - x)`
11//!
12//! To beat the record the following condition must hold:
13//!
14//! * `x * (t - x) = d`
15//! * `x² - tx +d = 0`
16//!
17//! The start and end times where we will be the record are given by the roots of the
18//! quadratic equation which we can solve using the
19//! [quadratic formula](https://en.wikipedia.org/wiki/Quadratic_formula).
20//!
21//! * `(t ± √(t² - 4d)) / 2`
22use crate::util::parse::*;
23
24pub fn parse(input: &str) -> Vec<&str> {
25    input.lines().collect()
26}
27
28pub fn part1(input: &[&str]) -> u128 {
29    race(input[0], input[1])
30}
31
32pub fn part2(input: &[&str]) -> u128 {
33    race(&merge(input[0]), &merge(input[1]))
34}
35
36fn merge(line: &str) -> String {
37    line.chars().filter(char::is_ascii_digit).collect()
38}
39
40fn race(first: &str, second: &str) -> u128 {
41    first
42        .iter_unsigned::<u128>()
43        .zip(second.iter_unsigned::<u128>())
44        .map(|(time, distance)| {
45            // Use the quadratic formula to find the start and end positions.
46            let root = (time * time - 4 * distance).isqrt();
47            let mut start = (time - root).div_ceil(2);
48            let mut end = time.midpoint(root);
49
50            // As we're using integer math we may need to adjust 1 step.
51            if start * (time - start) > distance {
52                start -= 1;
53            }
54            if end * (time - end) > distance {
55                end += 1;
56            }
57
58            end - start - 1
59        })
60        .product()
61}
aoc/year2023/day06.rs

aoc/year2023/
day06.rs
