adventofcode22/src/day9.rs

//! Day 9: Rope Bridge

use std::{collections::HashSet, fmt::Debug};

use itertools::Itertools;

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

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Direction {
    U,
    D,
    R,
    L,
}

impl Position {
    fn move_dir(self, dir: Direction) -> Self {
        match dir {
            Direction::U => Self {
                x: self.x,
                y: self.y + 1,
            },
            Direction::D => Self {
                x: self.x,
                y: self.y - 1,
            },
            Direction::R => Self {
                x: self.x + 1,
                y: self.y,
            },
            Direction::L => Self {
                x: self.x - 1,
                y: self.y,
            },
        }
    }

    fn dx(self, p2: Position) -> i32 {
        self.x - p2.x
    }

    fn dy(self, p2: Position) -> i32 {
        self.y - p2.y
    }
}

impl Debug for Position {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_fmt(format_args!("{}|{}", self.x, self.y))
    }
}

fn update_rope_pos(hpos: Position, tpos: Position) -> (Position, Position) {
    let dx = hpos.dx(tpos);
    let dy = hpos.dy(tpos);

    match (dx.abs() < 2, dy.abs() < 2) {
        (true, true) => (hpos, tpos),
        (true, false) => (
            hpos,
            Position {
                x: hpos.x,
                y: hpos.y - dy + dy.signum(),
            },
        ),
        (false, true) => (
            hpos,
            Position {
                x: hpos.x - dx + dx.signum(),
                y: hpos.y,
            },
        ),
        (false, false) => (
            hpos,
            Position {
                x: hpos.x - dx + dx.signum(),
                y: hpos.y - dy + dy.signum(),
            },
        ),
    }
}

fn parse_line(line: &str) -> (Direction, i32) {
    let (d_str, n_str) = line.split_once(' ').unwrap();
    let d = match d_str {
        "U" => Direction::U,
        "D" => Direction::D,
        "R" => Direction::R,
        "L" => Direction::L,
        _ => panic!("invalid dir: {}", d_str),
    };
    (d, n_str.parse().unwrap())
}

fn print_rope(rope: &[Position]) {
    let (min_x, max_x) = match rope.iter().map(|p| p.x).minmax() {
        itertools::MinMaxResult::NoElements => return,
        itertools::MinMaxResult::OneElement(x) => (x, x),
        itertools::MinMaxResult::MinMax(min_x, max_x) => (min_x, max_x),
    };
    let (min_y, max_y) = match rope.iter().map(|p| p.y).minmax() {
        itertools::MinMaxResult::NoElements => return,
        itertools::MinMaxResult::OneElement(y) => (y, y),
        itertools::MinMaxResult::MinMax(min_y, max_y) => (min_y, max_y),
    };

    for y in (min_y..=max_y).rev() {
        for x in min_x..=max_x {
            if let Some((n, _)) = rope.iter().find_position(|p| p == &&Position { x, y }) {
                print!("{}", n)
            } else {
                print!(".");
            }
        }
        println!();
    }
    println!();
}

pub fn part1(input: Vec<String>) -> String {
    let mut visited = HashSet::new();

    let mut hpos = Position::default();
    let mut tpos = Position::default();
    visited.insert(tpos);

    for (dir, n) in input.iter().map(|line| parse_line(line)) {
        for _ in 0..n {
            (hpos, tpos) = update_rope_pos(hpos.move_dir(dir), tpos);
            visited.insert(tpos);
        }
    }

    visited.len().to_string()
}

pub fn part2(input: Vec<String>) -> String {
    let mut visited = HashSet::new();
    let rope_len = 10;

    // head of the rope first
    let mut rope = (0..rope_len)
        .map(|_| Position::default())
        .collect::<Vec<_>>();
    visited.insert(rope[rope_len - 1]);

    for (dir, n) in input.iter().map(|line| parse_line(line)) {
        for _ in 0..n {
            let mut new_rope = Vec::with_capacity(rope_len);
            let mut rope_iter = rope.iter();
            let mut hpos = rope_iter.next().copied().unwrap().move_dir(dir);

            for tpos in rope_iter {
                let (n_hpos, n_tpos) = update_rope_pos(hpos, *tpos);
                new_rope.push(n_hpos);
                // Tail pos of this section will be head pos of next section
                hpos = n_tpos;
            }
            new_rope.push(hpos);
            rope = new_rope;
            visited.insert(rope[rope_len - 1]);
            // print_rope(&rope);
        }
    }

    print_rope(&rope);
    visited.len().to_string()
}

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

    use rstest::rstest;

    const DAY: u8 = 9;

    #[rstest]
    #[case(
        Position {x: 0, y: 0},
        Position {x: 0, y: 0},
        Direction::R,
        Position {x: 0, y: 0},
    )]
    #[case(
        Position {x: 1, y: 0},
        Position {x: 0, y: 0},
        Direction::R,
        Position {x: 1, y: 0},
    )]
    #[case(
        Position {x: 4, y: 1},
        Position {x: 3, y: 0},
        Direction::U,
        Position {x: 4, y: 1},
    )]
    #[case(
        Position {x: 4, y: 4},
        Position {x: 4, y: 3},
        Direction::L,
        Position {x: 4, y: 3},
    )]
    #[case(
        Position {x: 3, y: 4},
        Position {x: 4, y: 3},
        Direction::L,
        Position {x: 3, y: 4},
    )]
    fn rope_pos(
        #[case] hpos: Position,
        #[case] tpos: Position,
        #[case] dir: Direction,
        #[case] exp: Position,
    ) {
        let (_, tpos) = update_rope_pos(hpos.move_dir(dir), tpos);
        assert_eq!(tpos, exp);
    }

    #[test]
    fn t_example1() {
        assert_eq!(part1(crate::read_example(DAY)), "13");
    }

    #[test]
    fn t_example2() {
        assert_eq!(part2(crate::read_example(DAY)), "1");
    }

    #[test]
    fn t_example2b() {
        let input = vec![
            "R 5".to_owned(),
            "U 8".to_owned(),
            "L 8".to_owned(),
            "D 3".to_owned(),
            "R 17".to_owned(),
            "D 10".to_owned(),
            "L 25".to_owned(),
            "U 20".to_owned(),
        ];
        assert_eq!(part2(input), "36");
    }

    #[test]
    fn t_part1() {
        assert_eq!(part1(crate::read_input(DAY)), "6332");
    }

    #[test]
    fn t_part2() {
        assert_eq!(part2(crate::read_input(DAY)), "2511");
    }
}