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

aoc/year2022/
day09.rs
