path: root/day14a/src/main.rs

/// --- Day 14: Regolith Reservoir ---
///
/// The distress signal leads you to a giant waterfall!  Actually, hang on - the signal seems like
/// it's coming from the waterfall itself, and that doesn't make any sense.  However, you do notice
/// a little path that leads behind the waterfall.
///
/// Correction: the distress signal leads you behind a giant waterfall!  There seems to be a large
/// cave system here, and the signal definitely leads further inside.
///
/// As you begin to make your way deeper underground, you feel the ground rumble for a moment.
/// Sand begins pouring into the cave!  If you don't quickly figure out where the sand is going,
/// you could quickly become trapped!
///
/// Fortunately, your familiarity with analyzing the path of falling material will come in handy
/// here.  You scan a two-dimensional vertical slice of the cave above you (your puzzle input) and
/// discover that it is mostly air with structures made of rock.
///
/// Your scan traces the path of each solid rock structure and reports the x,y coordinates that
/// form the shape of the path, where x represents distance to the right and y represents distance
/// down.  Each path appears as a single line of text in your scan.  After the first point of each
/// path, each point indicates the end of a straight horizontal or vertical line to be drawn from
/// the previous point.  For example:
///
/// ```
/// 498,4 -> 498,6 -> 496,6
/// 503,4 -> 502,4 -> 502,9 -> 494,9
/// ```
///
/// This scan means that there are two paths of rock; the first path consists of two straight
/// lines, and the second path consists of three straight lines.  (Specifically, the first path
/// consists of a line of rock from 498,4 through 498,6 and another line of rock from 498,6 through
/// 496,6.)
///
/// The sand is pouring into the cave from point 500,0.
///
/// Drawing rock as #, air as ., and the source of the sand as +, this becomes:
///
///
/// ```
///   4     5  5
///   9     0  0
///   4     0  3
/// 0 ......+...
/// 1 ..........
/// 2 ..........
/// 3 ..........
/// 4 ....#...##
/// 5 ....#...#.
/// 6 ..###...#.
/// 7 ........#.
/// 8 ........#.
/// 9 #########.
/// ```
///
/// Sand is produced one unit at a time, and the next unit of sand is not produced until the
/// previous unit of sand comes to rest.  A unit of sand is large enough to fill one tile of air in
/// your scan.
///
/// A unit of sand always falls down one step if possible.  If the tile immediately below is
/// blocked (by rock or sand), the unit of sand attempts to instead move diagonally one step down
/// and to the left.  If that tile is blocked, the unit of sand attempts to instead move diagonally
/// one step down and to the right.  Sand keeps moving as long as it is able to do so, at each step
/// trying to move down, then down-left, then down-right.  If all three possible destinations are
/// blocked, the unit of sand comes to rest and no longer moves, at which point the next unit of
/// sand is created back at the source.
///
/// So, drawing sand that has come to rest as o, the first unit of sand simply falls straight down
/// and then stops:
///
/// ```
/// ......+...
/// ..........
/// ..........
/// ..........
/// ....#...##
/// ....#...#.
/// ..###...#.
/// ........#.
/// ......o.#.
/// #########.
/// ```
///
/// The second unit of sand then falls straight down, lands on the first one, and then comes to
/// rest to its left:
///
/// ```
/// ......+...
/// ..........
/// ..........
/// ..........
/// ....#...##
/// ....#...#.
/// ..###...#.
/// ........#.
/// .....oo.#.
/// #########.
/// ```
///
/// After a total of five units of sand have come to rest, they form this pattern:
///
/// ```
/// ......+...
/// ..........
/// ..........
/// ..........
/// ....#...##
/// ....#...#.
/// ..###...#.
/// ......o.#.
/// ....oooo#.
/// #########.
/// ```
///
/// After a total of 22 units of sand:
///
/// ```
/// ......+...
/// ..........
/// ......o...
/// .....ooo..
/// ....#ooo##
/// ....#ooo#.
/// ..###ooo#.
/// ....oooo#.
/// ...ooooo#.
/// #########.
/// ```
///
/// Finally, only two more units of sand can possibly come to rest:
///
/// ```
/// ......+...
/// ..........
/// ......o...
/// .....ooo..
/// ....#ooo##
/// ...o#ooo#.
/// ..###ooo#.
/// ....oooo#.
/// .o.ooooo#.
/// #########.
/// ```
///
/// Once all 24 units of sand shown above have come to rest, all further sand flows out the bottom,
/// falling into the endless void.  Just for fun, the path any new sand takes before falling
/// forever is shown here with ~:
///
/// ```
/// .......+...
/// .......~...
/// ......~o...
/// .....~ooo..
/// ....~#ooo##
/// ...~o#ooo#.
/// ..~###ooo#.
/// ..~..oooo#.
/// .~o.ooooo#.
/// ~#########.
/// ~..........
/// ~..........
/// ~..........
/// ```
///
/// Using your scan, simulate the falling sand.  How many units of sand come to rest before sand
/// starts flowing into the abyss below?
use clap::Parser;
use itertools::Itertools;
use nom::bytes::complete::tag;
use nom::character::complete::i32;
use nom::combinator::{map, opt};
use nom::error::{ContextError, ErrorKind as NomErrorKind, ParseError};
use nom::multi::many1;
use nom::sequence::{terminated, tuple};
use nom::IResult;

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

const FILEPATH: &'static str = "examples/input.txt";
const SAND_SOURCE: Coords = Coords { x: 500, y: 0 };

pub type Input<'a> = &'a str;
pub type Result<'a, T> = IResult<Input<'a>, T, Error<Input<'a>>>;

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ErrorKind {
    Nom(NomErrorKind),
    Context(&'static str),
    Custom(String),
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Terrain {
    Air,
    Rock,
    Sand,
    SandSource,
}

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

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Error<I> {
    pub errors: Vec<(I, ErrorKind)>,
}

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

impl Coords {
    fn path_between(&self, other: &Coords) -> Vec<Coords> {
        if self == other {
            panic!()
        }
        if self.x == other.x {
            let yrange = {
                if self.y > other.y {
                    other.y..=self.y
                } else if other.y > self.y {
                    self.y..=other.y
                } else {
                    panic!()
                }
            };
            yrange.map(|y| Coords { x: self.x, y }).collect_vec()
        } else {
            let xrange = {
                if self.x > other.x {
                    other.x..=self.x
                } else if other.x > self.x {
                    self.x..=other.x
                } else {
                    panic!()
                }
            };
            xrange.map(|x| Coords { x, y: self.y }).collect_vec()
        }
    }
}

#[derive(Clone, Debug)]
struct Grid {
    data: Vec<Vec<Terrain>>,
    bounds: GridBoundaries,
}

impl Grid {
    fn new(bounds: GridBoundaries) -> Self {
        let xlen = (bounds.maxx - bounds.minx) as usize + 1;
        let ylen = (bounds.maxy - bounds.miny) as usize + 1;
        let data = vec![vec![Terrain::Air; ylen]; xlen];
        Self { data, bounds }
    }

    fn get(&self, coord: &Coords) -> &Terrain {
        &self.data[(coord.x - self.bounds.minx) as usize][(coord.y - self.bounds.miny) as usize]
    }

    fn set(&mut self, coord: &Coords, terrain: Terrain) {
        self.data[(coord.x - self.bounds.minx) as usize][(coord.y - self.bounds.miny) as usize] =
            terrain;
    }

    fn populate(&mut self, geography: Vec<RockStructure>) {
        geography
            .into_iter()
            .map(|rstruct| {
                rstruct
                    .0
                    .as_slice()
                    .windows(2)
                    .map(|window| window[0].path_between(&window[1]))
                    .flatten()
                    .collect_vec()
            })
            .flatten()
            .scan(self, |state, coords| {
                state.data[(coords.x - state.bounds.minx) as usize]
                    [(coords.y - state.bounds.miny) as usize] = Terrain::Rock;
                Some(())
            })
            .last()
            .unwrap()
    }

    fn run(&mut self) -> usize {
        let mut count = 0;
        let mut pos = SAND_SOURCE;
        let mut history = vec![SAND_SOURCE];
        'block: loop {
            for (dx, dy) in [(0, 1), (-1, 1), (1, 1)] {
                let next_pos = Coords {
                    x: &pos.x + dx,
                    y: &pos.y + dy,
                };

                if (next_pos.x < self.bounds.minx)
                    || (next_pos.x > self.bounds.maxx)
                    || (next_pos.y > self.bounds.maxy)
                {
                    break 'block;
                }

                if self.get(&next_pos) == &Terrain::Air {
                    history.push(next_pos);
                    pos = next_pos;
                    continue 'block;
                }
            }

            self.set(&pos, Terrain::Sand);
            pos = {
                loop {
                    let prev_pos = history[history.len() - 1];
                    match self.get(&prev_pos) {
                        Terrain::Air | Terrain::SandSource => break prev_pos,
                        _ => {
                            let _ = history.pop();
                            continue;
                        }
                    };
                }
            };
            count += 1;
        }
        count
    }
}

#[derive(Clone, Debug)]
struct GridBoundaries {
    minx: i32,
    maxx: i32,
    miny: i32,
    maxy: i32,
}

impl GridBoundaries {
    fn new() -> Self {
        GridBoundaries {
            minx: i32::max_value(),
            maxx: i32::min_value(),
            miny: 0,
            maxy: i32::min_value(),
        }
    }

    fn combine(&mut self, other: &GridBoundaries) {
        self.minx = i32::min(self.minx, other.minx);
        self.maxx = i32::max(self.maxx, other.maxx);
        self.miny = i32::min(self.miny, other.miny);
        self.maxy = i32::max(self.maxy, other.maxy);
    }

    fn fold(&self, other: &Coords) -> Self {
        let mut res = GridBoundaries::new();
        res.minx = i32::min(self.minx, other.x);
        res.maxx = i32::max(self.maxx, other.x);
        res.miny = i32::min(self.miny, other.y);
        res.maxy = i32::max(self.maxy, other.y);
        res
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct RockStructure(Vec<Coords>);

impl<I> ParseError<I> for Error<I> {
    fn from_error_kind(input: I, kind: NomErrorKind) -> Self {
        let errors = vec![(input, ErrorKind::Nom(kind))];
        Self { errors }
    }

    fn append(input: I, kind: NomErrorKind, mut other: Self) -> Self {
        other.errors.push((input, ErrorKind::Nom(kind)));
        other
    }
}

impl<I> ContextError<I> for Error<I> {
    fn add_context(input: I, ctx: &'static str, mut other: Self) -> Self {
        other.errors.push((input, ErrorKind::Context(ctx)));
        other
    }
}

fn parse_coord(input: &str) -> Result<Coords> {
    map(tuple((terminated(i32, tag(",")), i32)), |(x, y)| Coords {
        x,
        y,
    })(input)
}

fn parse_line(input: &str) -> Result<RockStructure> {
    map(many1(terminated(parse_coord, opt(tag(" -> ")))), |v| {
        RockStructure(v)
    })(input)
}

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

    let file = File::open(&args.file).unwrap();
    let reader = BufReader::new(file);

    let mut bounds = GridBoundaries::new();
    let geography = reader
        .lines()
        .map(|l| parse_line(l.unwrap().as_str()).unwrap().1)
        .scan(&mut bounds, |state, rstruct| {
            state.combine(
                &rstruct
                    .0
                    .iter()
                    .fold(GridBoundaries::new(), |acc, x| acc.fold(x)),
            );
            Some(rstruct)
        })
        .collect_vec();

    let mut grid = Grid::new(bounds);
    grid.set(&SAND_SOURCE, Terrain::SandSource);
    grid.populate(geography);
    assert_eq!(grid.get(&SAND_SOURCE), &Terrain::SandSource);

    let res = grid.run();
    println!("{res:?}");
}