path: root/day09a/src/main.rs

/// --- Day 9: Rope Bridge ---
///
/// This rope bridge creaks as you walk along it.  You aren't sure how old it is, or whether it can
/// even support your weight.
///
/// It seems to support the Elves just fine, though.  The bridge spans a gorge which was carved out
/// by the massive river far below you.
///
/// You step carefully; as you do, the ropes stretch and twist.  You decide to distract yourself by
/// modeling rope physics; maybe you can even figure out where not to step.
///
/// Consider a rope with a knot at each end; these knots mark the head and the tail of the rope.  If
/// the head moves far enough away from the tail, the tail is pulled toward the head.
///
/// Due to nebulous reasoning involving Planck lengths, you should be able to model the positions
/// of the knots on a two-dimensional grid.  Then, by following a hypothetical series of motions
/// (your puzzle input) for the head, you can determine how the tail will move.
///
/// Due to the aforementioned Planck lengths, the rope must be quite short; in fact, the head (H)
/// and tail (T) must always be touching (diagonally adjacent and even overlapping both count as
/// touching):
///
/// ```
/// ....
/// .TH.
/// ....
///
/// ....
/// .H..
/// ..T.
/// ....
///
/// ...
/// .H. (H covers T)
/// ...
/// ```
///
/// If the head is ever two steps directly up, down, left, or right from the tail, the tail must
/// also move one step in that direction so it remains close enough:
///
/// ```
/// .....    .....    .....
/// .TH.. -> .T.H. -> ..TH.
/// .....    .....    .....
///
/// ...    ...    ...
/// .T.    .T.    ...
/// .H. -> ... -> .T.
/// ...    .H.    .H.
/// ...    ...    ...
/// ```
///
/// Otherwise, if the head and tail aren't touching and aren't in the same row or column, the tail
/// always moves one step diagonally to keep up:
///
/// ```
/// .....    .....    .....
/// .....    ..H..    ..H..
/// ..H.. -> ..... -> ..T..
/// .T...    .T...    .....
/// .....    .....    .....
///
/// .....    .....    .....
/// .....    .....    .....
/// ..H.. -> ...H. -> ..TH.
/// .T...    .T...    .....
/// .....    .....    .....
/// ```
///
/// You just need to work out where the tail goes as the head follows a series of motions.  Assume
/// the head and the tail both start at the same position, overlapping.
///
/// For example:
///
/// ```
/// R 4
/// U 4
/// L 3
/// D 1
/// R 4
/// D 1
/// L 5
/// R 2
/// ```
///
/// This series of motions moves the head right four steps, then up four steps, then left three
/// steps, then down one step, and so on.  After each step, you'll need to update the position of
/// the tail if the step means the head is no longer adjacent to the tail.  Visually, these motions
/// occur as follows (s marks the starting position as a reference point):
///
/// ```
/// == Initial State ==
///
/// ......
/// ......
/// ......
/// ......
/// H.....  (H covers T, s)
///
/// == R 4 ==
///
/// ......
/// ......
/// ......
/// ......
/// TH....  (T covers s)
///
/// ......
/// ......
/// ......
/// ......
/// sTH...
///
/// ......
/// ......
/// ......
/// ......
/// s.TH..
///
/// ......
/// ......
/// ......
/// ......
/// s..TH.
///
/// == U 4 ==
///
/// ......
/// ......
/// ......
/// ....H.
/// s..T..
///
/// ......
/// ......
/// ....H.
/// ....T.
/// s.....
///
/// ......
/// ....H.
/// ....T.
/// ......
/// s.....
///
/// ....H.
/// ....T.
/// ......
/// ......
/// s.....
///
/// == L 3 ==
///
/// ...H..
/// ....T.
/// ......
/// ......
/// s.....
///
/// ..HT..
/// ......
/// ......
/// ......
/// s.....
///
/// .HT...
/// ......
/// ......
/// ......
/// s.....
///
/// == D 1 ==
///
/// ..T...
/// .H....
/// ......
/// ......
/// s.....
///
/// == R 4 ==
///
/// ..T...
/// ..H...
/// ......
/// ......
/// s.....
///
/// ..T...
/// ...H..
/// ......
/// ......
/// s.....
///
/// ......
/// ...TH.
/// ......
/// ......
/// s.....
///
/// ......
/// ....TH
/// ......
/// ......
/// s.....
///
/// == D 1 ==
///
/// ......
/// ....T.
/// .....H
/// ......
/// s.....
///
/// == L 5 ==
///
/// ......
/// ....T.
/// ....H.
/// ......
/// s.....
///
/// ......
/// ....T.
/// ...H..
/// ......
/// s.....
///
/// ......
/// ......
/// ..HT..
/// ......
/// s.....
///
/// ......
/// ......
/// .HT...
/// ......
/// s.....
///
/// ......
/// ......
/// HT....
/// ......
/// s.....
///
/// == R 2 ==
///
/// ......
/// ......
/// .H....  (H covers T)
/// ......
/// s.....
///
/// ......
/// ......
/// .TH...
/// ......
/// s.....
/// ```
///
/// After simulating the rope, you can count up all of the positions the tail visited at least
/// once.  In this diagram, s again marks the starting position (which the tail also visited) and #
/// marks other positions the tail visited:
///
/// ```
/// ..##..
/// ...##.
/// .####.
/// ....#.
/// s###..
/// ```
///
/// So, there are 13 positions the tail visited at least once.
///
/// Simulate your complete hypothetical series of motions.  How many positions does the tail of the
/// rope visit at least once?
use clap::Parser;
use itertools::Itertools;

use std::collections::HashSet;
use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
use std::path::PathBuf;

const FILEPATH: &'static str = "examples/input.txt";

#[derive(Parser, Debug)]
#[clap(author, version, about, long_about = None)]
struct Cli {
    #[clap(short, long, default_value = FILEPATH)]
    file: PathBuf,
}

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

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

#[derive(Clone, Debug)]
struct Command {
    dir: Direction,
    amount: u32,
}

#[derive(Clone, Debug)]
struct State {
    head: Coord,
    tail: Coord,
    tail_visited: HashSet<Coord>,
}

impl Coord {
    fn new() -> Self {
        Self { x: 0, y: 0 }
    }
}

impl Command {
    fn parse(dir: &str, amount: &str) -> Self {
        use Direction::*;
        let d = match dir {
            "U" => Up,
            "D" => Down,
            "L" => Left,
            "R" => Right,
            _ => panic!("unknown direction {}", dir),
        };
        Self {
            dir: d,
            amount: amount.parse::<u32>().unwrap(),
        }
    }
}

impl State {
    fn new() -> Self {
        let mut hs = HashSet::new();
        hs.insert(Coord::new());
        State {
            head: Coord::new(),
            tail: Coord::new(),
            tail_visited: hs,
        }
    }

    fn update_tail(&mut self) {
        match (self.head.x - self.tail.x, self.head.y - self.tail.y) {
            (0, 0)
            | (1, 0)
            | (-1, 0)
            | (0, 1)
            | (0, -1)
            | (1, 1)
            | (-1, -1)
            | (1, -1)
            | (-1, 1) => return,
            (xdiff, ydiff) => {
                self.tail.x += i32::signum(xdiff);
                self.tail.y += i32::signum(ydiff);
                self.tail_visited.insert(self.tail);
            },
        }
    }

    fn shift(&mut self, dir: Direction) {
        use Direction::*;
        match dir {
            Up => self.head.y += 1,
            Down => self.head.y -= 1,
            Right => self.head.x += 1,
            Left => self.head.x -= 1,
        }
        self.update_tail();
    }

    fn process(&mut self, cmd: &Command) {
        for _ in 0..cmd.amount {
            self.shift(cmd.dir);
        }
    }
}

fn main() {
    let args = Cli::parse();

    let file = File::open(&args.file).unwrap();
    let reader = BufReader::new(file);
    let mut state = State::new();
    let _ = reader
        .lines()
        .map(|l| {
            l.unwrap()
                .split_whitespace()
                .map(|s| s.to_owned())
                .collect_tuple::<(String, String)>()
                .unwrap()
        })
        .map(|(dir, amount)| Command::parse(dir.as_str(), amount.as_str()))
        .scan(&mut state, |state, cmd| {
            state.process(&cmd);
            Some(())
        })
        .last();

    let res = state.tail_visited.len();
    println!("{res:?}");
}