Day 9 challenge of Advent Of Code is to deal with Rope Physics. We pass a rope bridge over a gorge. The elves pass easily, while the bridge behaves differently as we enter it. To distract yourself we are modelling rope physics.

The rope we model contains of two parts, head & tail. When the head moves on a 2-dimensional grid the tail moves according to specific rules. The head will follow a series of motions (the puzzle input) while the tail will follow. The tail needs to stay in touch with the head all the time, meaning it's either adjacent to the head (including diagonal directions).

....
.TH.
....

....
.H..
..T.
....

...
.H. (H covers T)
...

H marks the head, T the tail. If the head moves one step but the tail stays a neighbor, the tail will not move. If the tail moves ahead the tail will follow by moving in one of its eight neighboring directions.

Part 1

The rope will follow a set of motions, for example:

R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2

where the first line states that the head moves to the right by four steps. The head can move right (R), down (D), left (L) & up (U). Once the rope has followed all motions the goal is to count all unique positions the tail has visited. The initial state is head & tail are in the same position (they are allowed to overlap). Following the motions above the final state looks as follows:

..##..
...##.
.####.
....#.
s###..

where s is the initial position. The tail part has visited 13 positions in this case.

Let's start by parsing the given input from the file input.txt. The format is fairly straightforward and does not warrant a parser such as peg or nom for today. First part is the direction followed by number of steps (u32). For the direction we introduce an enum.

#[derive(Debug)]
enum Direction {
    Right,
    Up,
    Left,
    Down,
}

impl From<&str> for Direction {
    fn from(d: &str) -> Self {
        match d {
            "R" => Self::Right,
            "U" => Self::Up,
            "L" => Self::Left,
            "D" => Self::Down,
            _ => panic!("Unsupported input found"),
        }
    }
}

#[derive(Debug)]
struct Move {
    pub dir: Direction,
    pub steps: u32,
}

impl Move {
    pub fn new(dir: Direction, steps: u32) -> Self {
        Self { dir, steps }
    }
}

fn parse(input: &str) -> Vec<Move> {
    input
        .lines()
        .map(str::trim)
        .filter(|l| !l.is_empty())
        .map(|line| {
            let (dir, steps) = line.split_once(" ").expect("Failed to parse line.");
            Move::new(
                dir.into(),
                steps.parse::<u32>().expect("Failed to parse number"),
            )
        })
        .collect::<Vec<_>>()
}

fn part1(moves: &[Move]) -> usize {
    todo!()
}

fn main() {
    let grid = parse(include_str!("input.txt"));
    println!("Part 1: {}", part1(&grid));
}

#[cfg(test)]
mod tests {
    use crate::*;

    const INPUT: &str = r#"
        R 4
        U 4
        L 3
        D 1
        R 4
        D 1
        L 5
        R 2
    "#;

    #[test]
    fn check_part1() {
        let grid = parse(INPUT);
        assert_eq!(13, part1(&grid));
    }
}

The code sets up the Direction enum, a Move struct & the parse function to read in all moves. Each line is expected to contain a direction and an integer, separated by a whitespace. The test currently fails.

The rope is moving in a 2-dimensional grid, therefore coordinates will be used. We only keep track of the movements & keep the trail as a list of visited positions the tail will visit. Along with head and tail positions this will be grouped in a Grid struct.

#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
struct Pos {
    x: i32,
    y: i32,
}

impl Pos {
    pub const fn new(x: i32, y: i32) -> Self {
        Self { x, y }
    }

    pub fn touches(&self, rhs: &Pos) -> bool {
        (self.x - rhs.x).abs() <= 1 && (self.y - rhs.y).abs() <= 1
    }
}

impl std::ops::AddAssign for Pos {
    fn add_assign(&mut self, rhs: Self) {
        self.x += rhs.x;
        self.y += rhs.y;
    }
}

#[derive(Debug)]
struct Grid {
    head: Pos,
    last_head: Pos,
    tail: Pos,
    trail: HashSet<Pos>,
}

impl Grid {
    const DIRECTIONS: [Pos; 4] = [
        Pos::new(1, 0),  // right
        Pos::new(0, -1), // up
        Pos::new(-1, 0), // left
        Pos::new(0, 1),  // down
    ];

    pub fn new() -> Self {
        let trail = HashSet::from([Pos::new(0, 0)]);
        Self {
            head: Pos::new(0, 0),
            last_head: Pos::new(0, 0,),
            tail: Pos::new(0, 0),
            trail,
        }
    }

    /// Apply the given move, update tail if necessary, keep track of where tail stepped.
    pub fn step(&mut self, m: &Move) {
        for _ in 0..m.steps {
            let dir = Self::DIRECTIONS[m.dir as usize];
            self.last_head = self.head;
            self.head += dir;

            // update tail position if head moves away
            if !self.tail.touches(&self.head) {
                self.tail = self.last_head;
                self.trail.insert(self.tail);
            }
        }
    }
}

// 👇 apply all moves
fn part1(moves: &[Move]) -> usize {
    let mut grid = Grid::new();
    for m in moves {
        grid.step(m);
    }
    grid.trail.len()
}

The Pos struct holds the coordinates, the Grid is to keep track of head, tail and the visited positions. Initially the rope starts at position 0,0. The interesting part here is the Pos#touches method that checks if two positions touch each other. The Grid#step method applies the given movement, updates the tail accordingly and keeps track of visited positions. Only unique positions are stored, ignoring any revisited coordinates.

With the code in place the test now passes and we should be able to get the first solution.

Part 2

A rope snaps and you realize the rope does not consists of only two knots but has a length of 10, where one knot is still the head, while all other knots are the tail. Visited positions are still only counted by the last knot, the end of the tail.

The same motion applies meaning neighboring knots still need to touch until the end of the rope. Instead of keeping head & tail in separate fields, we will refactor the current solution to use a Vec of variable length.

#[derive(Debug)]
struct Grid {
    rope: Vec<Pos>,
    trail: HashSet<Pos>,
}

impl Grid {
    //    👇 Construct rope of length N
    pub fn new(num_knots: usize) -> Self {
        let trail = HashSet::from([Pos::new(0, 0)]);
        let rope = repeat(Pos::new(0, 0)).take(num_knots).collect::<Vec<_>>();
        Self { rope, trail }
    }

    pub fn step(&mut self, m: &Move) {
        let dir = Self::DIRECTIONS[m.dir as usize];
        for _ in 0..m.steps {
            let mut last_head = self.rope[0];
            self.rope[0] += dir;

            for index in 1..self.rope.len() {
                let head = self.rope[index - 1];
                let tail = self.rope[index];

                if !head.touches(&tail) {
                    self.rope[index] = last_head;
                    last_head = head;
                    self.trail.insert(head);
                }
            }
        }
    }
}

The test for part 1 still passes, that seems easy enough. Adding another test to check part 2 should help.

fn part2(moves: &[Move]) -> usize {
    let mut grid = Grid::new(10);
    for m in moves {
        grid.step(m);
    }
    grid.trail.len()
}

#[cfg(test)]
mod tests {
    // 👇 Add new test
    #[test]
    fn check_part2() {
        let grid = parse(INPUT);
        assert_eq!(36, part2(&grid));
    }
}

Which unfortunately does not pass because I failed to realize the following snippet from the challenge:

However, be careful: more types of motion are possible than before, so you might want to visually compare your simulated rope to the one above.

After a bit of thought that makes sense, because while one or more knots from the tail need to adjust their positions not all of them need to move. For two knots the solution was working ok, but for ropes longer than two knots it does not.

Instead of moving up a knot into the position of its predecessor knots need to check pair wise if they touch and update their position accordingly if not. The idea is to find the directional movement required to catch up with the position of a predecessor. The head & its successors can only move one step at a time it should therefore not be possible to "break" the rope.

struct Pos {
    /// Returns a directional Vector to advance one knot to the other
    pub fn get_dir(&self, target: &Pos) -> Pos {
        let x = match target.x.cmp(&self.x) {
            Ordering::Less => 1,
            Ordering::Equal => 0,
            Ordering::Greater => -1,
        };
        let y = match target.y.cmp(&self.y) {
            Ordering::Less => 1,
            Ordering::Equal => 0,
            Ordering::Greater => -1,
        };
        Pos::new(x, y)
    }
}

The previous step method needs to be adjusted as well.

struct Grid {
    pub fn step(&mut self, m: &Move) {
        let dir = Self::DIRECTIONS[m.dir as usize];
        //  👇 to avoid borrow checker issue with mutable `self.rope`
        let num_knots = self.rope.len();

        for _ in 0..m.steps {
            self.rope[0] += dir;

            for index in 1..num_knots {
                let head = self.rope[index - 1];
                let tail = self.rope[index];

                if !tail.touches(&head) {
                    self.rope[index] += head.get_dir(&tail);
                }
            }

            if let Some(last) = self.rope.last() {
                self.trail.insert(*last);
            }
        }
    }
}

The refactored for loop updates the head, then for each pair of knots updates the knot if they don't touch each other.

The tests should pass now & the second solution can be determined.

fn main() {
    let moves = parse(include_str!("input.txt"));
    println!("Part 1: {}", part1(&moves));
    println!("Part 2: {}", part2(&moves));
}