complete day 8

1 files changed, 203 insertions, 0 deletions

diff --git a/day08a/src/main.rs b/day08a/src/main.rs
new file mode 100644
index 0000000..510ccb7
--- /dev/null
+++ b/day08a/src/main.rs
@@ -0,0 +1,203 @@
+/// --- Day 8: Treetop Tree House ---
+///
+/// The expedition comes across a peculiar patch of tall trees all planted carefully in a grid.
+/// The Elves explain that a previous expedition planted these trees as a reforestation
+/// effort.  Now, they're curious if this would be a good location for a tree house.
+///
+/// First, determine whether there is enough tree cover here to keep a tree house hidden.  To do
+/// this, you need to count the number of trees that are visible from outside the grid when looking
+/// directly along a row or column.
+///
+/// The Elves have already launched a quadcopter to generate a map with the height of each tree
+/// (your puzzle input). For example:
+///
+/// ```
+/// 30373
+/// 25512
+/// 65332
+/// 33549
+/// 35390
+/// ```
+///
+/// Each tree is represented as a single digit whose value is its height, where 0 is the shortest
+/// and 9 is the tallest.
+///
+/// A tree is visible if all of the other trees between it and an edge of the grid are shorter than
+/// it.  Only consider trees in the same row or column; that is, only look up, down, left, or right
+/// from any given tree.
+///
+/// All of the trees around the edge of the grid are visible - since they are already on the edge,
+/// there are no trees to block the view.  In this example, that only leaves the interior nine
+/// trees to consider:
+///
+///     The top-left 5 is visible from the left and top. (It isn't visible from the right or bottom
+///     since other trees of height 5 are in the way.)
+///     The top-middle 5 is visible from the top and right.
+///     The top-right 1 is not visible from any direction; for it to be visible, there would need
+///     to only be trees of height 0 between it and an edge.
+///     The left-middle 5 is visible, but only from the right.
+///     The center 3 is not visible from any direction; for it to be visible, there would need to
+///     be only trees of at most height 2 between it and an edge.
+///     The right-middle 3 is visible from the right.
+///     In the bottom row, the middle 5 is visible, but the 3 and 4 are not.
+///
+/// With 16 trees visible on the edge and another 5 visible in the interior, a total of 21 trees
+/// are visible in this arrangement.
+///
+/// Consider your map; how many trees are visible from outside the grid?
+use clap::Parser;
+use itertools::Itertools;
+
+use std::fs::File;
+use std::io::prelude::*;
+use std::io::BufReader;
+use std::path::PathBuf;
+
+const FILEPATH: &'static str = "examples/input.txt";
+
+#[derive(Parser, Debug)]
+#[clap(author, version, about, long_about = None)]
+struct Cli {
+    #[clap(short, long, default_value = FILEPATH)]
+    file: PathBuf,
+}
+
+#[derive(Clone)]
+struct Visibility {
+    visible: bool,
+    top: u8,
+    bottom: u8,
+    left: u8,
+    right: u8,
+}
+
+impl Visibility {
+    fn new() -> Self {
+        Self {
+            visible: false,
+            top: 0,
+            bottom: 0,
+            left: 0,
+            right: 0,
+        }
+    }
+}
+
+fn main() {
+    let args = Cli::parse();
+
+    let file = File::open(&args.file).unwrap();
+    let reader = BufReader::new(file);
+    let grid = reader
+        .lines()
+        .map(|l| {
+            l.unwrap()
+                .chars()
+                .map(|c| c.to_digit(10).unwrap() as u8)
+                .collect_vec()
+        })
+        .collect_vec();
+
+    let xdim = grid.len();
+    let ydim = grid[0].len();
+
+    let mut vis_grid: Vec<Vec<Visibility>> = Vec::new();
+    vis_grid.resize(xdim, vec![Visibility::new(); ydim]);
+
+    for idx in 0..xdim {
+        for idy in 0..ydim {
+            let tree = grid[idx][idy];
+            match (idy, idx) {
+                (0, 0) => {
+                    let vis = &mut vis_grid[idx][idy];
+                    vis.visible = true;
+                    vis.left = tree;
+                    vis.top = tree;
+                }
+                (0, _) => {
+                    let vis = &mut vis_grid[idx][idy];
+                    vis.visible = true;
+                    vis.left = tree;
+                }
+                (_, 0) => {
+                    let vis = &mut vis_grid[idx][idy];
+                    vis.visible = true;
+                    vis.top = tree;
+                }
+                (idy, idx) => {
+                    let lhs_vis = vis_grid[idx][idy - 1].left;
+                    let top_vis = vis_grid[idx - 1][idy].top;
+
+                    let vis = &mut vis_grid[idx][idy];
+                    if lhs_vis < tree {
+                        vis.left = tree;
+                        vis.visible = true;
+                    } else {
+                        vis.left = lhs_vis;
+                    }
+
+                    if top_vis < tree {
+                        vis.top = tree;
+                        vis.visible = true;
+                    } else {
+                        vis.top = top_vis;
+                    }
+
+                    if lhs_vis >= tree && top_vis >= tree {
+                        vis.visible = false;
+                    }
+                }
+            }
+        }
+    }
+
+    for idx in (0..xdim).rev() {
+        for idy in (0..ydim).rev() {
+            let tree = grid[idx][idy];
+            match (idy, idx) {
+                (x, y) if (x == ydim - 1 && y == xdim - 1) => {
+                    let vis = &mut vis_grid[idx][idy];
+                    vis.visible = true;
+                    vis.right = tree;
+                    vis.bottom = tree;
+                }
+                (x, _) if x == ydim - 1 => {
+                    let vis = &mut vis_grid[idx][idy];
+                    vis.visible = true;
+                    vis.right = tree;
+                }
+                (_, y) if y == xdim - 1 => {
+                    let vis = &mut vis_grid[idx][idy];
+                    vis.visible = true;
+                    vis.bottom = tree;
+                }
+                (idy, idx) => {
+                    let rhs_vis = vis_grid[idx][idy + 1].right;
+                    let bottom_vis = vis_grid[idx + 1][idy].bottom;
+
+                    let vis = &mut vis_grid[idx][idy];
+                    if rhs_vis < tree {
+                        vis.right = tree;
+                        vis.visible = true;
+                    } else {
+                        vis.right = rhs_vis;
+                    }
+
+                    if bottom_vis < tree {
+                        vis.bottom = tree;
+                        vis.visible = true;
+                    } else {
+                        vis.bottom = bottom_vis;
+                    }
+                }
+            }
+        }
+    }
+
+    let res: u32 = vis_grid
+        .into_iter()
+        .flatten()
+        .map(|v| if v.visible { 1 } else { 0 })
+        .sum();
+    println!("{res:?}");
+}