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 conditition 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    let times = first.iter_unsigned::<u128>();
42    let distances = second.iter_unsigned::<u128>();
43    let mut result = 1;
44
45    for (time, distance) in times.zip(distances) {
46        // Use the quadratic formula to find the start and end positions.
47        let root = (time * time - 4 * distance).isqrt();
48        let mut start = (time - root).div_ceil(2);
49        let mut end = (time + root) / 2;
50
51        // As we're using integer math we may need to adjust 1 step.
52        if start * (time - start) > distance {
53            start -= 1;
54        }
55        if end * (time - end) > distance {
56            end += 1;
57        }
58
59        result *= end - start - 1;
60    }
61
62    result
63}
aoc/year2023/day06.rs

aoc/year2023/
day06.rs
