complete day 14HEADmaster

1 files changed, 345 insertions, 0 deletions

diff --git a/day14b/src/main.rs b/day14b/src/main.rs
new file mode 100644
index 0000000..f1c3846
--- /dev/null
+++ b/day14b/src/main.rs
@@ -0,0 +1,345 @@
+/// --- Part Two ---
+///
+/// You realize you misread the scan.  There isn't an endless void at the bottom of the scan -
+/// there's floor, and you're standing on it!
+///
+/// You don't have time to scan the floor, so assume the floor is an infinite horizontal line with
+/// a y coordinate equal to two plus the highest y coordinate of any point in your scan.
+///
+/// In the example above, the highest y coordinate of any point is 9, and so the floor is at y=11.
+/// (This is as if your scan contained one extra rock path like -infinity,11 -> infinity,11.) With
+/// the added floor, the example above now looks like this:
+///
+/// ```
+///         ...........+........
+///         ....................
+///         ....................
+///         ....................
+///         .........#...##.....
+///         .........#...#......
+///         .......###...#......
+///         .............#......
+///         .............#......
+///         .....#########......
+///         ....................
+/// <-- etc #################### etc -->
+/// ```
+///
+/// To find somewhere safe to stand, you'll need to simulate falling sand until a unit of sand
+/// comes to rest at 500,0, blocking the source entirely and stopping the flow of sand into the
+/// cave.  In the example above, the situation finally looks like this after 93 units of sand come
+/// to rest:
+///
+/// ```
+/// ............o............
+/// ...........ooo...........
+/// ..........ooooo..........
+/// .........ooooooo.........
+/// ........oo#ooo##o........
+/// .......ooo#ooo#ooo.......
+/// ......oo###ooo#oooo......
+/// .....oooo.oooo#ooooo.....
+/// ....oooooooooo#oooooo....
+/// ...ooo#########ooooooo...
+/// ..ooooo.......ooooooooo..
+/// #########################
+/// ```
+///
+/// Using your scan, simulate the falling sand until the source of the sand becomes blocked.  How
+/// many units of sand come to rest?
+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 };
+const FLOOR_OFFSET: usize = 2;
+
+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)
+                {
+                    continue;
+                }
+
+                if self.get(&next_pos) == &Terrain::Air {
+                    history.push(next_pos);
+                    pos = next_pos;
+                    continue 'block;
+                }
+            }
+
+            count += 1;
+            if pos == SAND_SOURCE {
+                break '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
+    }
+}
+
+#[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 mut 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();
+
+    bounds.maxy = bounds.maxy + FLOOR_OFFSET as i32;
+    let max_x_len = 2 * bounds.maxy - 1;
+    let minx = SAND_SOURCE.x - (max_x_len - 1) / 2;
+    let maxx = SAND_SOURCE.x + (max_x_len - 1) / 2;
+    assert!(minx < bounds.minx);
+    assert!(maxx > bounds.maxx);
+    bounds.minx = minx;
+    bounds.maxx = maxx;
+
+    geography.push(RockStructure(vec![
+        Coords {
+            x: minx,
+            y: bounds.maxy,
+        },
+        Coords {
+            x: maxx,
+            y: bounds.maxy,
+        },
+    ]));
+
+    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:?}");
+}