summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/bin/2023/day18.rs232
-rw-r--r--src/bin/2023/main.rs2
-rw-r--r--src/grid.rs74
3 files changed, 308 insertions, 0 deletions
diff --git a/src/bin/2023/day18.rs b/src/bin/2023/day18.rs
new file mode 100644
index 0000000..74e2611
--- /dev/null
+++ b/src/bin/2023/day18.rs
@@ -0,0 +1,232 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
+enum Direction {
+ Up,
+ Down,
+ Left,
+ Right,
+}
+
+impl Direction {
+ fn from_pos(row: Row, col: Col, new_row: Row, new_col: Col) -> Self {
+ if row.abs_diff(new_row) == Row(1) && col.abs_diff(new_col) == Col(0)
+ {
+ if row > new_row {
+ Self::Up
+ } else {
+ Self::Down
+ }
+ } else if col.abs_diff(new_col) == Col(1)
+ && row.abs_diff(new_row) == Row(0)
+ {
+ if col > new_col {
+ Self::Left
+ } else {
+ Self::Right
+ }
+ } else {
+ panic!("invalid direction ({row:?}, {col:?}) -> ({new_row:?}, {new_col:?})")
+ }
+ }
+
+ fn horizontal(&self) -> bool {
+ matches!(self, Self::Left | Self::Right)
+ }
+
+ fn increasing(&self) -> bool {
+ matches!(self, Self::Down | Self::Right)
+ }
+
+ fn turns(&self) -> [Self; 2] {
+ match self {
+ Self::Up | Self::Down => [Self::Left, Self::Right],
+ Self::Left | Self::Right => [Self::Up, Self::Down],
+ }
+ }
+
+ fn turn_left(&self) -> Self {
+ match self {
+ Direction::Up => Direction::Left,
+ Direction::Down => Direction::Right,
+ Direction::Left => Direction::Down,
+ Direction::Right => Direction::Up,
+ }
+ }
+
+ fn turn_right(&self) -> Self {
+ match self {
+ Direction::Up => Direction::Right,
+ Direction::Down => Direction::Left,
+ Direction::Left => Direction::Up,
+ Direction::Right => Direction::Down,
+ }
+ }
+
+ fn offset(&self) -> (IRow, ICol) {
+ match self {
+ Self::Up => (IRow(-1), ICol(0)),
+ Self::Down => (IRow(1), ICol(0)),
+ Self::Left => (IRow(0), ICol(-1)),
+ Self::Right => (IRow(0), ICol(1)),
+ }
+ }
+}
+
+#[derive(Debug)]
+pub struct Instruction {
+ direction: Direction,
+ distance: isize,
+ real_direction: Direction,
+ real_distance: isize,
+}
+
+impl std::str::FromStr for Instruction {
+ type Err = anyhow::Error;
+
+ fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
+ let cap = regex_captures!(
+ r"^(U|D|L|R) (\d+) \(#([0-9a-f]{5})([0-9a-f])\)",
+ s
+ )
+ .ok_or_else(|| anyhow::anyhow!("failed to parse line"))?;
+
+ let direction = match &cap[1] {
+ "U" => Direction::Up,
+ "D" => Direction::Down,
+ "L" => Direction::Left,
+ "R" => Direction::Right,
+ _ => bail!("unknown direction {}", &cap[1]),
+ };
+ let distance = cap[2].parse()?;
+ let real_direction = match &cap[4] {
+ "0" => Direction::Right,
+ "1" => Direction::Down,
+ "2" => Direction::Left,
+ "3" => Direction::Up,
+ _ => bail!("unknown real direction in {}", &cap[4]),
+ };
+ let real_distance = isize::from_str_radix(&cap[3], 16)?;
+
+ Ok(Self {
+ direction,
+ distance,
+ real_direction,
+ real_distance,
+ })
+ }
+}
+
+pub fn parse(fh: File) -> Result<Vec<Instruction>> {
+ Ok(parse::lines(fh).collect())
+}
+
+pub fn part1(instructions: Vec<Instruction>) -> Result<i64> {
+ let mut map: Grid<bool> = Grid::default();
+ let mut pos = (IRow(0), ICol(0));
+ let mut corners = vec![pos];
+ for instruction in &instructions {
+ let offset = instruction.direction.offset();
+ pos = (
+ pos.0 + offset.0 * instruction.distance,
+ pos.1 + offset.1 * instruction.distance,
+ );
+ corners.push(pos);
+ }
+ let min_row = corners.iter().map(|(row, _)| row).min().unwrap();
+ let min_col = corners.iter().map(|(_, col)| col).min().unwrap();
+
+ let starting_pos =
+ (Row(min_row.0.abs_diff(0)), Col(min_col.0.abs_diff(0)));
+ let mut pos = starting_pos;
+ for instruction in &instructions {
+ let offset = instruction.direction.offset();
+ for _ in 0..instruction.distance {
+ pos = (
+ Row(pos.0 .0.checked_add_signed(offset.0 .0).unwrap()),
+ Col(pos.1 .0.checked_add_signed(offset.1 .0).unwrap()),
+ );
+ map.grow(pos.0 + 1, pos.1 + 1);
+ map[pos.0][pos.1] = true;
+ }
+ }
+
+ let trench: HashSet<_> = map
+ .indexed_cells()
+ .filter_map(
+ |((row, col), dug)| if *dug { Some((row, col)) } else { None },
+ )
+ .collect();
+ let mut internal_cell = None;
+ for (row, col) in map.adjacent(starting_pos.0, starting_pos.1, true) {
+ if trench.contains(&(row, col)) {
+ continue;
+ }
+ let mut count = 0;
+ for offset in 0..=(row.0.min(col.0)) {
+ let check_row = row - offset;
+ let check_col = col - offset;
+ if trench.contains(&(check_row, check_col)) {
+ count += 1;
+ }
+ }
+ if count % 2 == 1 {
+ internal_cell = Some((row, col));
+ }
+ }
+ let internal_cell = internal_cell.unwrap();
+ map.flood_fill(internal_cell.0, internal_cell.1, &true, true);
+
+ Ok(map.cells().filter(|dug| **dug).count().try_into().unwrap())
+}
+
+pub fn part2(instructions: Vec<Instruction>) -> Result<i64> {
+ let mut pos = (IRow(0), ICol(0));
+
+ let mut vertices = vec![pos];
+ let mut last_left = false;
+ for pair in instructions.windows(2) {
+ let instruction = &pair[0];
+ let next_instruction = &pair[1];
+ let mut distance = instruction.real_distance + 1;
+ if last_left {
+ distance -= 1;
+ }
+ if instruction.real_direction.turn_left()
+ == next_instruction.real_direction
+ {
+ distance -= 1;
+ last_left = true;
+ } else {
+ last_left = false;
+ }
+ let offset = instruction.real_direction.offset();
+ pos = (pos.0 + offset.0 * distance, pos.1 + offset.1 * distance);
+ vertices.push(pos);
+ }
+
+ let mut area = 0;
+ for i in 0..vertices.len() {
+ let next = if i == vertices.len() - 1 { 0 } else { i + 1 };
+ area += vertices[i].0 .0 * vertices[next].1 .0
+ - vertices[next].0 .0 * vertices[i].1 .0;
+ }
+ area /= 2;
+
+ Ok(area.abs().try_into().unwrap())
+}
+
+#[test]
+fn test() {
+ assert_eq!(
+ part1(parse(parse::data(2023, 18).unwrap()).unwrap()).unwrap(),
+ 36807
+ );
+ assert_eq!(
+ part2(parse(parse::data(2023, 18).unwrap()).unwrap()).unwrap(),
+ 48797603984357
+ );
+}
diff --git a/src/bin/2023/main.rs b/src/bin/2023/main.rs
index 25f7c4d..b9eb819 100644
--- a/src/bin/2023/main.rs
+++ b/src/bin/2023/main.rs
@@ -28,6 +28,7 @@ mod day14;
mod day15;
mod day16;
mod day17;
+mod day18;
// NEXT MOD
#[paw::main]
@@ -51,6 +52,7 @@ fn main(opt: Opt) -> Result<()> {
15 => advent_of_code::day!(2023, opt.day, opt.puzzle, day15),
16 => advent_of_code::day!(2023, opt.day, opt.puzzle, day16),
17 => advent_of_code::day!(2023, opt.day, opt.puzzle, day17),
+ 18 => advent_of_code::day!(2023, opt.day, opt.puzzle, day18),
// NEXT PART
_ => panic!("unknown day {}", opt.day),
}
diff --git a/src/grid.rs b/src/grid.rs
index b006882..63fab03 100644
--- a/src/grid.rs
+++ b/src/grid.rs
@@ -34,6 +34,13 @@ impl std::ops::Add<Row> for usize {
}
}
+impl std::ops::Add<Row> for Row {
+ type Output = Row;
+ fn add(self, other: Row) -> Self::Output {
+ Row(self.0 + other.0)
+ }
+}
+
impl std::ops::Add<usize> for Col {
type Output = Self;
fn add(self, other: usize) -> Self::Output {
@@ -48,6 +55,13 @@ impl std::ops::Add<Col> for usize {
}
}
+impl std::ops::Add<Col> for Col {
+ type Output = Col;
+ fn add(self, other: Col) -> Self::Output {
+ Col(self.0 + other.0)
+ }
+}
+
impl std::ops::Sub<usize> for Row {
type Output = Self;
fn sub(self, other: usize) -> Self::Output {
@@ -168,6 +182,13 @@ impl std::ops::Add<IRow> for isize {
}
}
+impl std::ops::Add<IRow> for IRow {
+ type Output = IRow;
+ fn add(self, other: IRow) -> Self::Output {
+ IRow(self.0 + other.0)
+ }
+}
+
impl std::ops::Add<isize> for ICol {
type Output = Self;
fn add(self, other: isize) -> Self::Output {
@@ -182,6 +203,13 @@ impl std::ops::Add<ICol> for isize {
}
}
+impl std::ops::Add<ICol> for ICol {
+ type Output = ICol;
+ fn add(self, other: ICol) -> Self::Output {
+ ICol(self.0 + other.0)
+ }
+}
+
impl std::ops::Sub<isize> for IRow {
type Output = Self;
fn sub(self, other: isize) -> Self::Output {
@@ -210,6 +238,34 @@ impl std::ops::Sub<ICol> for isize {
}
}
+impl std::ops::Mul<isize> for IRow {
+ type Output = Self;
+ fn mul(self, other: isize) -> Self::Output {
+ Self(self.0 * other)
+ }
+}
+
+impl std::ops::Mul<IRow> for isize {
+ type Output = IRow;
+ fn mul(self, other: IRow) -> Self::Output {
+ IRow(self * other.0)
+ }
+}
+
+impl std::ops::Mul<isize> for ICol {
+ type Output = Self;
+ fn mul(self, other: isize) -> Self::Output {
+ Self(self.0 * other)
+ }
+}
+
+impl std::ops::Mul<ICol> for isize {
+ type Output = ICol;
+ fn mul(self, other: ICol) -> Self::Output {
+ ICol(self * other.0)
+ }
+}
+
#[derive(Default, Clone, Debug, Eq, PartialEq, Hash)]
pub struct GridRow<T: Clone + Eq + PartialEq + std::hash::Hash> {
cells: Vec<T>,
@@ -330,6 +386,24 @@ impl<T: Clone + Eq + PartialEq + std::hash::Hash> Grid<T> {
pos: 0,
}
}
+
+ pub fn flood_fill(
+ &mut self,
+ row: Row,
+ col: Col,
+ fill: &T,
+ diagonal: bool,
+ ) {
+ let mut todo = vec![(row, col)];
+ while let Some((row, col)) = todo.pop() {
+ self[row][col] = fill.clone();
+ for (row, col) in self.adjacent(row, col, diagonal) {
+ if self[row][col] != *fill {
+ todo.push((row, col));
+ }
+ }
+ }
+ }
}
impl<T: Default + Clone + Eq + PartialEq + std::hash::Hash> Grid<T> {
generated by cgit v1.2.3-54-g00ecf (git 2.45.1) at 2024-05-29 08:08:52 +0000