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, i32, i32, i32, 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: Vec<_> = first.zip(second).collect();
19
20    // Determine maximum extents
21    let (x1, y1, x2, y2, _) = pairs.iter().fold(
22        (i32::MAX, i32::MAX, i32::MIN, i32::MIN, ORIGIN),
23        |(x1, y1, x2, y2, point), &(step, amount)| {
24            let next = point + step * amount;
25            (x1.min(next.x), y1.min(next.y), x2.max(next.x), y2.max(next.y), next)
26        },
27    );
28
29    (x1, y1, x2, y2, pairs)
30}
31
32/// Simulate a rope length of 2
33pub fn part1(input: &Input) -> u32 {
34    simulate::<2>(input)
35}
36
37/// Simulate a rope length of 10
38pub fn part2(input: &Input) -> u32 {
39    simulate::<10>(input)
40}
41
42/// Simulates a rope of arbitrary length.
43///
44/// The head knot always moves according the instructions from the problem input. Remaining knots
45/// move according to their delta from the head (2nd knot) or the previous knot
46/// (3rd and subsequent knots).
47///
48/// Using const generics for the rope length allows the compiler to optimize the loop and speeds
49/// things up by about 40%.
50fn simulate<const N: usize>(input: &Input) -> u32 {
51    let (x1, y1, x2, y2, pairs) = input;
52    let width = x2 - x1 + 1;
53    let height = y2 - y1 + 1;
54    let start = Point::new(-x1, -y1);
55
56    let mut distinct = 0;
57    let mut rope = [start; N];
58    let mut grid = vec![false; (width * height) as usize];
59
60    for &(step, amount) in pairs {
61        for _ in 0..amount {
62            rope[0] += step;
63            for i in 1..N {
64                if !apart(rope[i - 1], rope[i]) {
65                    break;
66                }
67                rope[i] += rope[i - 1].signum(rope[i]);
68            }
69
70            let tail = rope[N - 1];
71            let index = (width * tail.y + tail.x) as usize;
72
73            if !grid[index] {
74                grid[index] = true;
75                distinct += 1;
76            }
77        }
78    }
79
80    distinct
81}
82
83/// Two knots are considered "apart" if the they are not diagonally adjacent, that is the absolute
84/// distance in either x or y axes is greater than 1.
85#[inline]
86fn apart(a: Point, b: Point) -> bool {
87    (a.x - b.x).abs() > 1 || (a.y - b.y).abs() > 1
88}
aoc/year2022/day09.rs

aoc/year2022/
day09.rs
