aoc/year2022/
day09.rs

1//! # Rope Bridge
2//!
3//! This solution relies on the [`Point`] utility module. Two dimensional problems are common in
4//! Advent of Code, so having a decent `Point` (or `Coord` or `Pos`) implementation is convenient.
5use crate::util::parse::*;
6use crate::util::point::*;
7
8type Pair = (Point, i32);
9type Input = (i32, i32, Point, Vec<Pair>);
10
11/// Converts input lines into a pair of [`Point`] and integer amount, to indicate direction and
12/// magnitude respectively. Then determines the maximum extent of the head so that we can allocate
13/// a two-dimensional grid.
14pub fn parse(input: &str) -> Input {
15    let first = input.bytes().filter(u8::is_ascii_alphabetic).map(Point::from);
16    let second = input.iter_signed();
17    let pairs: Vec<_> = first.zip(second).collect();
18
19    // Determine maximum extents.
20    let (x1, y1, x2, y2, _) = pairs.iter().fold(
21        (i32::MAX, i32::MAX, i32::MIN, i32::MIN, ORIGIN),
22        |(x1, y1, x2, y2, point), &(step, amount)| {
23            let next = point + step * amount;
24            (x1.min(next.x), y1.min(next.y), x2.max(next.x), y2.max(next.y), next)
25        },
26    );
27
28    let width = x2 - x1 + 1;
29    let height = y2 - y1 + 1;
30    let start = Point::new(-x1, -y1);
31    (width, height, start, pairs)
32}
33
34/// Simulate a rope length of 2.
35pub fn part1(input: &Input) -> u32 {
36    simulate::<2>(input)
37}
38
39/// Simulate a rope length of 10.
40pub fn part2(input: &Input) -> u32 {
41    simulate::<10>(input)
42}
43
44/// Simulates a rope of arbitrary length.
45///
46/// The head knot always moves according to the instructions from the problem input. Remaining knots
47/// move according to their delta from the head (2nd knot) or the previous knot
48/// (3rd and subsequent knots).
49///
50/// Using const generics for the rope length allows the compiler to optimize the loop and speeds
51/// things up by about 40%.
52fn simulate<const N: usize>(input: &Input) -> u32 {
53    let (width, height, start, pairs) = input;
54
55    let mut distinct = 0;
56    let mut rope = [*start; N];
57    let mut grid = vec![false; (width * height) as usize];
58
59    for &(step, amount) in pairs {
60        for _ in 0..amount {
61            rope[0] += step;
62            for i in 1..N {
63                let delta = rope[i - 1] - rope[i];
64
65                // Two knots are considered "apart" if they are not diagonally adjacent, that is
66                // the absolute distance in either x or y axes is greater than 1.
67                if delta.x.abs() <= 1 && delta.y.abs() <= 1 {
68                    break;
69                }
70
71                rope[i] += Point::new(delta.x.signum(), delta.y.signum());
72            }
73
74            let tail = rope[N - 1];
75            let index = (width * tail.y + tail.x) as usize;
76
77            if !grid[index] {
78                grid[index] = true;
79                distinct += 1;
80            }
81        }
82    }
83
84    distinct
85}
aoc/year2022/day09.rs

aoc/year2022/
day09.rs
