Day 8

Probably could have used some matrix transposition operations here.

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)
+    }
+}