aoc/year2022/
day09.rs

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

aoc/year2022/
day09.rs
