diff options
Diffstat (limited to '2022/src/bin/day_8.rs')
| -rw-r--r-- | 2022/src/bin/day_8.rs | 231 |
1 files changed, 231 insertions, 0 deletions
diff --git a/2022/src/bin/day_8.rs b/2022/src/bin/day_8.rs new file mode 100644 index 0000000..d044aa6 --- /dev/null +++ b/2022/src/bin/day_8.rs @@ -0,0 +1,231 @@ +use nom::{ + character::complete::{anychar, line_ending}, + combinator::map_res, + multi::{many1, separated_list1}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_8.txt")?; + let trees = TreeField::parser(&input).unwrap().1; + + dbg!(trees.count_visible_trees()); + dbg!(trees.find_best_scenic_score()); + + Ok(()) +} + +#[derive(Debug)] +struct TreeField { + width: usize, + height: usize, + tree_heights: Vec<Vec<i8>>, + row_height_fields: Vec<HeightField>, + column_height_fields: Vec<HeightField>, +} + +#[derive(Default, Debug)] +struct HeightField { + left_breaking_points: Vec<(usize, i8)>, + right_breaking_points: Vec<(usize, i8)>, +} + +enum TreeFieldError { + Empty, + NotRectangular, +} + +impl TreeField { + fn parser(input: &str) -> IResult<&str, TreeField> { + map_res( + separated_list1( + line_ending, + many1(map_res(anychar, |c: char| c.to_string().parse::<i8>())), + ), + TreeField::new, + )(input) + } + + fn new(tree_heights: Vec<Vec<i8>>) -> Result<TreeField, TreeFieldError> { + let height = tree_heights.len(); + if height == 0 { + return Result::Err(TreeFieldError::Empty); + } + + let width = tree_heights[0].len(); + let mut row_height_fields = Vec::new(); + for row in &tree_heights { + if row.len() != width { + return Result::Err(TreeFieldError::NotRectangular); + } + row_height_fields.push(HeightField::new(&row)); + } + + let mut column_height_fields = Vec::new(); + for column_i in 0..width { + let mut column = Vec::new(); + for row in &tree_heights { + column.push(row[column_i].clone()); + } + column_height_fields.push(HeightField::new(&column)); + } + + Ok(TreeField { + width, + height, + tree_heights, + row_height_fields, + column_height_fields, + }) + } + + fn tree_is_visible(&self, x: usize, y: usize) -> bool { + let tree_height = self.tree_heights[y][x]; + let (left_height, right_height) = self.row_height_fields[y].heights_at(x); + let (up_height, down_height) = self.column_height_fields[x].heights_at(y); + tree_height > left_height + || tree_height > right_height + || tree_height > up_height + || tree_height > down_height + } + + fn count_visible_trees(&self) -> usize { + let mut count = 0; + for y in 0..self.height { + for x in 0..self.width { + if self.tree_is_visible(x, y) { + count += 1; + } + } + } + count + } + + fn tree_scenic_score(&self, x: usize, y: usize) -> usize { + let tree_height = self.tree_heights[y][x]; + let (left_height, right_height) = self.row_height_fields[y].heights_at(x); + let left_score = if tree_height > left_height { + x + } else { + let mut count = 0; + let mut shift_x = x; + while shift_x > 0 { + count += 1; + shift_x -= 1; + let height = self.tree_heights[y][shift_x]; + if height >= tree_height { + break; + } + } + count + }; + let right_score = if tree_height > right_height { + self.width - 1 - x + } else { + let mut count = 0; + let mut shift_x = x; + while shift_x < self.width - 1 { + count += 1; + shift_x += 1; + let height = self.tree_heights[y][shift_x]; + if height >= tree_height { + break; + } + } + count + }; + + let (up_height, down_height) = self.column_height_fields[x].heights_at(y); + let up_score = if tree_height > up_height { + y + } else { + let mut count = 0; + let mut shift_y = y; + while shift_y > 0 { + count += 1; + shift_y -= 1; + let height = self.tree_heights[shift_y][x]; + if height >= tree_height { + break; + } + } + count + }; + let down_score = if tree_height > down_height { + self.height - 1 - y + } else { + let mut count = 0; + let mut shift_y = y; + while shift_y < self.height - 1 { + count += 1; + shift_y += 1; + let height = self.tree_heights[shift_y][x]; + if height >= tree_height { + break; + } + } + count + }; + + left_score * right_score * up_score * down_score + } + + fn find_best_scenic_score(&self) -> usize { + let mut max = 0; + for y in 0..self.height { + for x in 0..self.width { + let next = self.tree_scenic_score(x, y); + max = max.max(next); + } + } + max + } +} + +impl HeightField { + fn new(row: &[i8]) -> HeightField { + let mut left_breaking_points = Vec::new(); + let mut last_height = -1; + for (i, height) in row.iter().enumerate() { + if height > &last_height { + last_height = height.clone(); + left_breaking_points.push((i.clone(), height.clone())); + } + } + + let mut right_breaking_points = Vec::new(); + last_height = -1; + for (i, height) in row.iter().enumerate().rev() { + if height > &last_height { + last_height = height.clone(); + right_breaking_points.push((i.clone(), height.clone())); + } + } + + HeightField { + left_breaking_points, + right_breaking_points, + } + } + + fn heights_at(&self, i: usize) -> (i8, i8) { + let left = self + .left_breaking_points + .iter() + .filter(|(left_i, _)| left_i < &i) + .map(|(_, height)| height.clone()) + .last() + .unwrap_or(-1); + + let right = self + .right_breaking_points + .iter() + .filter(|(right_i, _)| right_i > &i) + .map(|(_, height)| height.clone()) + .last() + .unwrap_or(-1); + + (left, right) + } +} |