1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

//! This is my solution for [Advent of Code - Day 8 - _Treetop Tree House_](https://adventofcode.com/2022/day/8)
//!
//! Identify the best tree in a grid to build a tree house in, it must be hidden and have a good view.

use std::fs;
use itertools::FoldWhile::{Continue, Done};
use itertools::Itertools;
use crate::util::grid::Grid;

/// The entry point for running the solutions with the 'real' puzzle input.
///
/// - The puzzle input is expected to be at `<project_root>/res/day-8-input`
/// - It is expected this will be called by [`super::main()`] when the user elects to run day 8.
pub fn run() {
    let contents = fs::read_to_string("res/day-8-input").expect("Failed to read file");
    let grid = Grid::from(contents);

    println!(
        "The count of visible trees is: {}",
        find_visible_count(&grid)
    );

    println!(
        "The tree with the highest scenery score is: {}",
        find_best_scenery_score(&grid)
    );
}

/// Count the trees visible from the edges of the grid.
fn find_visible_count(grid: &Grid) -> usize {
    let mut visible = Grid::new(
        grid.width,
        grid.height(),
        |x, y| u8::from(x == 0 || y == 0 || x == grid.width - 1 || y == grid.height() - 1),
    );

    for y in 1..(grid.height() - 1) {
        mark_visible_trees((y, 0), (0, 1), &grid, &mut visible);
        mark_visible_trees((y, grid.width - 1), (0, -1), &grid, &mut visible);
    }

    for x in 1..(grid.width - 1) {
        mark_visible_trees((0, x), (1, 0), &grid, &mut visible);
        mark_visible_trees((grid.height() - 1, x), (-1, 0), &grid, &mut visible);
    }

    visible.sum()
}

/// For a given row or column start or end step forwards or backwards marking those that can be seen from the starting
/// position
fn mark_visible_trees(
    (origin_y, origin_x): (usize, usize),
    (dy, dx): (isize, isize),
    trees_grid: &Grid,
    visibility_grid: &mut Grid,
) {
    let mut max_height = trees_grid.get(origin_x, origin_y).unwrap();

    (1..)
        .map(
            |pos| {
                with_delta(origin_y, dy, pos)
                    .zip(with_delta(origin_x, dx, pos))
                    .and_then(|(y, x)| trees_grid.get(y, x).map(|h| (y, x, h)))
            })
        .while_some()
        .for_each(|(y, x, h)| {
            if max_height < h {
                max_height = h;
                visibility_grid.set(y, x, 1);
            }
        });
}

/// Apply a multiple of a delta to a starting position to get the position for a step if it is positive
fn with_delta(init: usize, delta: isize, multiplier: isize) -> Option<usize> {
    isize::try_from(init)
        .map(|init_i| init_i + delta * multiplier)
        .and_then(|result| usize::try_from(result))
        .ok()
}

/// For each tree in the grid, multiply the trees they can see in each direction. Return the best score.
fn find_best_scenery_score(grid: &Grid) -> usize {
    let deltas: Vec<(isize, isize)> = vec![(-1, 0), (0, -1), (1, 0), (0, 1)];

    grid.iter().map(
        |(pos, height)| {
            deltas.iter()
                  .map(|&delta| count_visible_with_delta(pos, delta, height, grid))
                  .reduce(|a, b| a * b).unwrap_or(0)
        }
    ).max().unwrap_or(0)
}

/// For a given tree, count how many trees can be seen in a given direction
fn count_visible_with_delta((origin_y, origin_x): (usize, usize), (dy, dx): (isize, isize), origin_height: u8, grid: &Grid) -> usize {
    (1..)
        .map(
            |pos| {
                with_delta(origin_y, dy, pos)
                    .zip(with_delta(origin_x, dx, pos))
                    .and_then(|(y, x)| grid.get(y, x))
            })
        .while_some()
        .fold_while(
            0,
            |count, h|
                if h >= origin_height { Done(count + 1) } else { Continue(count + 1) },
        ).into_inner()
}

#[cfg(test)]
mod tests {
    use crate::day_8::{find_best_scenery_score, find_visible_count};
    use crate::util::grid::Grid;

    fn sample_grid() -> Grid {
        let input = "30373
25512
65332
33549
35390".to_string();

        Grid::from(input)
    }

    #[test]
    fn can_count_visible() {
        assert_eq!(find_visible_count(&sample_grid()), 21);
    }

    #[test]
    fn can_find_max_score() {
        assert_eq!(find_best_scenery_score(&sample_grid()), 8);
    }
}