diff options
Diffstat (limited to 'day08a/src/main.rs')
| -rw-r--r-- | day08a/src/main.rs | 203 |
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:?}"); +} |