diff options
Diffstat (limited to 'src/day_8.rs')
| -rw-r--r-- | src/day_8.rs | 326 |
1 files changed, 326 insertions, 0 deletions
diff --git a/src/day_8.rs b/src/day_8.rs new file mode 100644 index 0000000..145bc22 --- /dev/null +++ b/src/day_8.rs @@ -0,0 +1,326 @@ +use std::{collections::HashSet, fmt::Display}; + +use anyhow::Result; + +use crate::{Problem, Solution}; + +type TreeHeight = i8; + +struct Visibility { + capacity_x: usize, + capacity_y: usize, + trees_seen: HashSet<(usize, usize)>, + max_north: Vec<TreeHeight>, + max_east: Vec<TreeHeight>, + max_south: Vec<TreeHeight>, + max_west: Vec<TreeHeight>, +} + +impl Visibility { + fn with_capacity(capacity_x: usize, capacity_y: usize) -> Self { + Self { + capacity_x, + capacity_y, + trees_seen: HashSet::new(), + max_north: vec![-1; capacity_x], + max_east: vec![-1; capacity_y], + max_south: vec![-1; capacity_x], + max_west: vec![-1; capacity_y], + } + } + + fn check_trees(&mut self, tree_grid: Vec<Vec<TreeHeight>>) { + self.check_trees_nw(&tree_grid); + self.check_trees_se(&tree_grid); + } + + fn check_trees_nw(&mut self, tree_grid: &[Vec<TreeHeight>]) { + for (y, trees) in tree_grid.iter().enumerate() { + for (x, tree) in trees.iter().enumerate() { + self.check_tree_nw(x, y, *tree) + } + } + } + + fn check_trees_se(&mut self, tree_grid: &[Vec<TreeHeight>]) { + for (y, trees) in tree_grid.iter().enumerate().rev() { + for (x, tree) in trees.iter().enumerate().rev() { + self.check_tree_se(x, y, *tree) + } + } + } + + fn check_tree_nw(&mut self, x: usize, y: usize, tree: TreeHeight) { + if tree > self.max_north[x] { + self.trees_seen.insert((x, y)); + self.max_north[x] = tree; + } + + if tree > self.max_west[y] { + self.trees_seen.insert((x, y)); + self.max_west[y] = tree; + } + } + + fn check_tree_se(&mut self, x: usize, y: usize, tree: TreeHeight) { + if tree > self.max_south[x] { + self.trees_seen.insert((x, y)); + self.max_south[x] = tree; + } + + if tree > self.max_east[y] { + self.trees_seen.insert((x, y)); + self.max_east[y] = tree; + } + } +} + +impl Display for Visibility { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + for y in 0..self.capacity_y { + let mut l = String::new(); + for x in 0..self.capacity_x { + l.push(if self.trees_seen.contains(&(x, y)) { + 'X' + } else { + ' ' + }) + } + writeln!(f, "{}", l)?; + } + Ok(()) + } +} + +#[derive(Debug, Default)] +struct ScenicScore { + tree: Tree, + north: Vec<Tree>, + east: Vec<Tree>, + south: Vec<Tree>, + west: Vec<Tree>, +} + +impl ScenicScore { + fn new( + tree: Tree, + north: Vec<Tree>, + east: Vec<Tree>, + south: Vec<Tree>, + west: Vec<Tree>, + ) -> Self { + Self { + tree, + north, + east, + south, + west, + } + } + fn score(&self) -> usize { + self.north.len() * self.east.len() * self.south.len() * self.west.len() + } +} + +impl Display for ScenicScore { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + for t in &self.north { + for _ in 0..self.tree.x { + write!(f, "x")?; + } + write!(f, "{t:>width$}", width = self.tree.x)?; + for _ in self.tree.x..self.east.len() { + write!(f, "x")?; + } + writeln!(f)?; + } + + let line = self + .west + .iter() + .chain([&self.tree]) + .chain(self.east.iter()) + .map(|t| t.to_string()) + .collect::<Vec<_>>() + .join(""); + + let offset = self.tree.x - self.west.len(); + writeln!(f, "{:offset$}", line)?; + + for t in &self.south { + for _ in 0..self.tree.x { + write!(f, "x")?; + } + writeln!(f, "{t:>width$}", width = self.tree.x)?; + for _ in self.tree.x..self.east.len() { + write!(f, "x")?; + } + } + + Ok(()) + } +} + +impl PartialEq for ScenicScore { + fn eq(&self, other: &Self) -> bool { + self.score() == other.score() + } +} + +impl Eq for ScenicScore {} + +impl PartialOrd for ScenicScore { + fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { + self.score().partial_cmp(&other.score()) + } +} + +impl Ord for ScenicScore { + fn cmp(&self, other: &Self) -> std::cmp::Ordering { + self.score().cmp(&other.score()) + } +} + +#[derive(Debug, Default, Clone, Copy)] +struct Tree { + x: usize, + y: usize, + height: TreeHeight, +} + +impl Tree { + fn new(x: usize, y: usize, height: TreeHeight) -> Self { + Self { x, y, height } + } + + fn scenic_score(&self, tree_grid: &[Vec<Tree>]) -> ScenicScore { + let mut north: Vec<Tree> = Vec::new(); + for t in tree_grid.iter().map(|v| v[self.x]).take(self.y).rev() { + north.push(t); + if t >= *self { + break; + } + } + north.reverse(); + + let mut east: Vec<Tree> = Vec::new(); + for t in tree_grid[self.y].iter().skip(self.x + 1) { + east.push(*t); + if t >= self { + break; + } + } + + let mut south: Vec<Tree> = Vec::new(); + for t in tree_grid.iter().map(|v| v[self.x]).skip(self.y + 1) { + south.push(t); + if t >= *self { + break; + } + } + + let mut west: Vec<Tree> = Vec::new(); + for t in tree_grid[self.y].iter().take(self.x).rev() { + west.push(*t); + if t >= self { + break; + } + } + west.reverse(); + + ScenicScore::new(*self, north, east, south, west) + } +} + +impl PartialEq for Tree { + fn eq(&self, other: &Self) -> bool { + self.height == other.height + } +} + +impl PartialOrd for Tree { + fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { + self.height.partial_cmp(&other.height) + } +} + +impl Display for Tree { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}", self.height) + } +} + +pub struct Day8; + +impl Problem for Day8 { + const DAY: u8 = 8; + + const INPUT: &'static str = include_str!("../input/day_8.txt"); +} + +impl Solution for Day8 { + type Answer1 = usize; + + type Answer2 = usize; + + fn part_1(input: &str) -> Result<Self::Answer1, anyhow::Error> { + let tree_grid: Vec<Vec<TreeHeight>> = input + .lines() + .map(|l| { + l.chars() + .filter_map(|c| c.to_digit(10).map(|d| d as TreeHeight)) + .collect() + }) + .collect(); + + let mut visibility = Visibility::with_capacity(tree_grid[0].len(), tree_grid.len()); + visibility.check_trees(tree_grid); + Ok(visibility.trees_seen.len()) + } + + fn part_2(input: &str) -> Result<Self::Answer2, anyhow::Error> { + let tree_grid: Vec<Vec<Tree>> = input + .lines() + .enumerate() + .map(|(y, l)| { + l.chars() + .enumerate() + .filter_map(|(x, c)| c.to_digit(10).map(|d| Tree::new(x, y, d as TreeHeight))) + .collect() + }) + .collect(); + + let trees = tree_grid.iter().flatten(); + + let max_score = trees + .map(|t| t.scenic_score(&tree_grid)) + .max() + .ok_or_else(|| anyhow::anyhow!("Failed to find max"))?; + + Ok(max_score.score()) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + const TEST_INPUT: &str = indoc::indoc! {r#" + 30373 + 25512 + 65332 + 33549 + 35390 + "#}; + + #[test] + fn test_part_1_example() -> Result<()> { + Ok(assert_eq!(21, Day8::part_1(TEST_INPUT)?)) + } + + #[test] + fn test_part_2_example() -> Result<()> { + println!("{TEST_INPUT}"); + Ok(assert_eq!(8, Day8::part_2(TEST_INPUT)?)) + } +} |