151 lines
3.3 KiB
Rust
151 lines
3.3 KiB
Rust
//! Day 8: Treetop Tree House
|
|
|
|
type Grid = Vec<Vec<u8>>;
|
|
|
|
fn parse_grid(input: &[String]) -> Grid {
|
|
let mut grid = Grid::new();
|
|
|
|
for line in input {
|
|
let mut grid_ln = Vec::new();
|
|
for tree in line.chars() {
|
|
let tree_h = tree.to_digit(10).unwrap() as u8;
|
|
grid_ln.push(tree_h);
|
|
}
|
|
grid.push(grid_ln);
|
|
}
|
|
grid
|
|
}
|
|
|
|
fn is_tree_visible(grid: &Grid, x: usize, y: usize) -> bool {
|
|
let h = grid.len();
|
|
let w = grid[0].len();
|
|
let tree_height = grid[y][x];
|
|
|
|
if x == 0 || x == w - 1 || y == 0 || y == h - 1 {
|
|
return true;
|
|
}
|
|
|
|
if (0..x).all(|xi| grid[y][xi] < tree_height) {
|
|
return true;
|
|
}
|
|
|
|
if (x + 1..w).all(|xi| grid[y][xi] < tree_height) {
|
|
return true;
|
|
}
|
|
|
|
if (0..y).all(|yi| grid[yi][x] < tree_height) {
|
|
return true;
|
|
}
|
|
|
|
if (y + 1..h).all(|yi| grid[yi][x] < tree_height) {
|
|
return true;
|
|
}
|
|
|
|
false
|
|
}
|
|
|
|
fn scenic_score(grid: &Grid, x: usize, y: usize) -> usize {
|
|
let h = grid.len();
|
|
let w = grid[0].len();
|
|
let tree_height = grid[y][x];
|
|
|
|
let side_score = |start: i64, end: i64, coord: usize, is_x: bool| {
|
|
let mut coord2 = start;
|
|
let mut n = 1;
|
|
|
|
while coord2 != end {
|
|
let h = if is_x {
|
|
grid[usize::try_from(coord2).unwrap()][coord]
|
|
} else {
|
|
grid[coord][usize::try_from(coord2).unwrap()]
|
|
};
|
|
|
|
if h >= tree_height {
|
|
return n;
|
|
}
|
|
|
|
if start < end {
|
|
coord2 += 1;
|
|
} else {
|
|
coord2 -= 1;
|
|
}
|
|
n += 1;
|
|
}
|
|
start.abs_diff(end)
|
|
};
|
|
|
|
let left = side_score(x as i64 - 1, -1, y, false);
|
|
let right = side_score(x as i64 + 1, w as i64, y, false);
|
|
let up = side_score(y as i64 - 1, -1, x, true);
|
|
let down = side_score(y as i64 + 1, h as i64, x, true);
|
|
|
|
(left * right * up * down).try_into().unwrap()
|
|
}
|
|
|
|
pub fn part1(input: Vec<String>) -> String {
|
|
let grid = parse_grid(&input);
|
|
let mut n: u32 = 0;
|
|
|
|
for (y, row) in grid.iter().enumerate() {
|
|
for x in 0..row.len() {
|
|
if is_tree_visible(&grid, x, y) {
|
|
n += 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
n.to_string()
|
|
}
|
|
|
|
pub fn part2(input: Vec<String>) -> String {
|
|
let grid = parse_grid(&input);
|
|
let mut max_score = 0;
|
|
|
|
for (y, row) in grid.iter().enumerate() {
|
|
for x in 0..row.len() {
|
|
max_score = max_score.max(scenic_score(&grid, x, y));
|
|
}
|
|
}
|
|
|
|
max_score.to_string()
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
|
|
const DAY: u8 = 8;
|
|
|
|
#[test]
|
|
fn t_example1() {
|
|
let input = crate::read_example(DAY);
|
|
let grid = parse_grid(&input);
|
|
assert!(is_tree_visible(&grid, 4, 0));
|
|
assert!(is_tree_visible(&grid, 1, 1));
|
|
assert!(!is_tree_visible(&grid, 3, 1));
|
|
|
|
assert_eq!(part1(input), "21");
|
|
}
|
|
|
|
#[test]
|
|
fn tmp() {
|
|
let input = crate::read_example(DAY);
|
|
let grid = parse_grid(&input);
|
|
dbg!(scenic_score(&grid, 2, 3));
|
|
}
|
|
|
|
#[test]
|
|
fn t_example2() {
|
|
assert_eq!(part2(crate::read_example(DAY)), "8");
|
|
}
|
|
|
|
#[test]
|
|
fn t_part1() {
|
|
assert_eq!(part1(crate::read_input(DAY)), "1533");
|
|
}
|
|
|
|
#[test]
|
|
fn t_part2() {
|
|
assert_eq!(part2(crate::read_input(DAY)), "345744");
|
|
}
|
|
}
|