# Day 8 (Advent of Code 2022)

In the day 8 problem, our input is a height map:

30373
25512
65332
33549
35390


This is a 5x5 grid, and every number denotes the height of a tree. For part 1, we must find out how many trees are visible from the outside of the grid.

If we consider the first row, from the left: only the 3 is visible: it obscures the 0. From the right, 3 and 7 are visible.

For the first column, from the top: 3 is visible, then it obscures the 2.

The challenge here is that trees might be visible from different directions: for example, this two:

  30373
->25512
65332
33549
35390


Is not visible from the top or the bottom, or the right, but it is visible from the left.

I can think of two ways to do this, and so let's do both! But first, we'll need a grid data structure.

## A grid data structure

In src/main.rs, let's add:

Rust code
mod grid;


Saving the file gives us a build error: the src/grid.rs file doesn't exist yet. Doing CmdOrCtrl+. on that line brings up rust-analyzer's quick fixes, and one of them is "Create module at grid.rs" - let's do that. Then we can use "Go to definition" (mapped to F12 by default, I have it mapped to "Leader+d" for me where leader is \\, since I have the Vim extension enabled at all times)

In there, we can start making a Grid data structure:

Rust code
// in src/grid.rs

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub(crate) struct GridCoord {
pub(crate) x: usize,
pub(crate) y: usize,
}

impl std::fmt::Debug for GridCoord {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "({}, {})", self.x, self.y)
}
}

impl From<(usize, usize)> for GridCoord {
fn from((x, y): (usize, usize)) -> Self {
Self { x, y }
}
}

pub(crate) struct Grid<T> {
width: usize,
height: usize,
data: Vec<T>,
}

impl<T> Grid<T>
where
T: Default + Clone,
{
pub(crate) fn new(width: usize, height: usize) -> Self {
Self {
width,
height,
data: vec![T::default(); width * height],
}
}

fn in_bounds(&self, coord: GridCoord) -> bool {
coord.x < self.width && coord.y < self.height
}

pub(crate) fn cell_mut(&mut self, coord: GridCoord) -> Option<&mut T> {
if !self.in_bounds(coord) {
return None;
}
Some(&mut self.data[coord.y * self.width + coord.x])
}

pub(crate) fn cell(&self, coord: GridCoord) -> Option<&T> {
if !self.in_bounds(coord) {
return None;
}
Some(&self.data[coord.y * self.width + coord.x])
}

pub(crate) fn width(&self) -> usize {
self.width
}

pub(crate) fn height(&self) -> usize {
self.height
}
}


And that feels like a good start!

I don't feel like the problem really warrants reaching for nom, so let's just wing it:

Rust code
// in src/main.rs

use grid::Grid;

mod grid;

fn main() {
let grid = parse_grid(include_str!("sample-input.txt"));
println!("grid at (0, 0): {:?}", grid.cell((0, 0).into()));
println!("grid at (3, 0): {:?}", grid.cell((3, 0).into()));
println!("grid at (0, 2): {:?}", grid.cell((0, 2).into()));
println!("grid at (2, 10): {:?}", grid.cell((2, 10).into()));
println!("grid at (10, 2): {:?}", grid.cell((10, 2).into()));
}

fn parse_grid(input: &str) -> Grid<usize> {
let width = input.lines().next().unwrap().len();
let height = input.lines().count();

let mut grid = Grid::new(width, height);
for (y, line) in input.lines().enumerate() {
for (x, col) in line.chars().enumerate() {
assert!(col.is_ascii_digit());
*grid.cell_mut((x, y).into()).unwrap() = col as usize - '0' as usize;
}
}

grid
}

Shell session
$cargo run (warnings omitted) Finished dev [unoptimized + debuginfo] target(s) in 0.00s Running target/debug/day8 grid at (0, 0): Some(3) grid at (3, 0): Some(7) grid at (0, 2): Some(6) grid at (2, 10): None grid at (10, 2): None thread 'main' panicked at 'not yet implemented: answer part 1', src/main.rs:12:5 note: run with RUST_BACKTRACE=1 environment variable to display a backtrace  Okay! Now let's solve that problem. ## The CPU-heavy solution I'm going to reach for some Rust Nightly APIs for this one because I don't understand why those haven't been stabilized yet. You know the drill, let's add a rust-toolchain.toml file: TOML markup [toolchain] channel = "nightly-2022-12-09"  And, as it turns out we don't need any attributes to enable that API, we can just use it, so, let's! Iterators appreciators, now is your time: Rust code fn main() { let grid = parse_grid(include_str!("sample-input.txt")); let all_coords = (0..grid.height()).into_iter().flat_map(|y| { (0..grid.width()) .into_iter() .map(move |x| GridCoord::from((x, y))) }); let num_visible_cells = all_coords .filter(|&coord| { let coord_height = grid.cell(coord).unwrap(); let deltas: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)]; deltas.iter().any(|&(dx, dy)| { // all cells going in one of the 4 possible directions, until // the edge of the grid let mut cells_in_ine = (1..).into_iter().map_while(|i| { let coord = GridCoord { x: coord.x.checked_add_signed(dx * i)?, y: coord.y.checked_add_signed(dy * i)?, }; grid.cell(coord) }); cells_in_ine.all(|height| height < coord_height) }) }) .count(); dbg!(num_visible_cells); }  This gives the proper answer for the sample input: Shell session $ cargo run
Compiling day8 v0.1.0 (/home/amos/bearcove/aoc2022/day8)
Finished dev [unoptimized + debuginfo] target(s) in 0.48s
Running target/debug/day8
[src/main.rs:32] num_visible_cells = 21


And the real input, too!

## The memory-heavy solution

The thing with that earlier solution is that it iterates over the same cells a bunch of times. In truth, we don't need to consider each cell in isolation, we could consider each row twice and each column twice.

Like that:

Rust code
fn main() {
let grid = parse_grid(include_str!("sample-input.txt"));

let all_rows = (0..grid.height()).into_iter().flat_map(|y| {
let l: Box<dyn Iterator<Item = GridCoord>> = Box::new(
(0..grid.width())
.into_iter()
.map(move |x| GridCoord::from((x, y))),
);
let r = Box::new(
(0..grid.width())
.into_iter()
.rev()
.map(move |x| GridCoord::from((x, y))),
);
[l as Box<dyn Iterator<Item = GridCoord>>, r].into_iter()
});

let all_cols = (0..grid.width()).into_iter().flat_map(|x| {
let t = Box::new(
(0..grid.height())
.into_iter()
.map(move |y| GridCoord::from((x, y))),
);
let b = Box::new(
(0..grid.height())
.into_iter()
.rev()
.map(move |y| GridCoord::from((x, y))),
);
[t as Box<dyn Iterator<Item = GridCoord>>, b].into_iter()
});

let all_lines = all_rows.chain(all_cols);
for line in all_lines {
let positions = line.collect::<Vec<_>>();
// note: dbg!() uses the extended format (:#?) which is too verbose
println!("{positions:?}");
}
}

Shell session
$cargo run [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)] [(4, 0), (3, 0), (2, 0), (1, 0), (0, 0)] [(0, 1), (1, 1), (2, 1), (3, 1), (4, 1)] [(4, 1), (3, 1), (2, 1), (1, 1), (0, 1)] [(0, 2), (1, 2), (2, 2), (3, 2), (4, 2)] [(4, 2), (3, 2), (2, 2), (1, 2), (0, 2)] [(0, 3), (1, 3), (2, 3), (3, 3), (4, 3)] [(4, 3), (3, 3), (2, 3), (1, 3), (0, 3)] [(0, 4), (1, 4), (2, 4), (3, 4), (4, 4)] [(4, 4), (3, 4), (2, 4), (1, 4), (0, 4)] [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)] [(0, 4), (0, 3), (0, 2), (0, 1), (0, 0)] [(1, 0), (1, 1), (1, 2), (1, 3), (1, 4)] [(1, 4), (1, 3), (1, 2), (1, 1), (1, 0)] [(2, 0), (2, 1), (2, 2), (2, 3), (2, 4)] [(2, 4), (2, 3), (2, 2), (2, 1), (2, 0)] [(3, 0), (3, 1), (3, 2), (3, 3), (3, 4)] [(3, 4), (3, 3), (3, 2), (3, 1), (3, 0)] [(4, 0), (4, 1), (4, 2), (4, 3), (4, 4)] [(4, 4), (4, 3), (4, 2), (4, 1), (4, 0)]  Now that we have all those lines as iterators, we can simply count how many items are in increasing order for each line: Shell session $ cargo add itertools
(cut)

Rust code
// at the top of src/main.rs
use itertools::Itertools;

fn main() {
// (omitted: building our mega-iterator)

let all_lines = all_rows.chain(all_cols);
let num_visible = all_lines
.map(|it| {
it.map(|coord| grid.cell(coord).unwrap())
.tuple_windows()
.take_while(|(prev, curr)| prev <= curr)
.count()
+ 1
})
.sum::<usize>();
dbg!(num_visible);
}


The problem is, that gives us the wrong answer:

Shell session
$cargo run Compiling either v1.8.0 Compiling itertools v0.10.5 Compiling day8 v0.1.0 (/home/amos/bearcove/aoc2022/day8) Finished dev [unoptimized + debuginfo] target(s) in 2.07s Running target/debug/day8 [src/main.rs:49] num_visible = 38  Because a bunch of cells are counted twice. We can see that if we return coordinates instead: Rust code  let all_lines = all_rows.chain(all_cols); let all_visible = all_lines.flat_map(|it| { let mut it = it .map(|coord| (coord, *grid.cell(coord).unwrap())) .peekable(); // the first cell from the edge is always visible let first = it.peek().unwrap().0; std::iter::once(first).chain(it.tuple_windows().map_while( |((_prev_coord, prev_height), (curr_coord, curr_height))| { if prev_height <= curr_height { Some(curr_coord) } else { None } }, )) }); let coords = all_visible.collect_vec(); println!("found {} coords: {:?}", coords.len(), coords);  Shell session $ cargo run
Compiling day8 v0.1.0 (/home/amos/bearcove/aoc2022/day8)
Finished dev [unoptimized + debuginfo] target(s) in 0.47s
Running target/debug/day8
found 38 coords: [(0, 0), (4, 0), (3, 0), (0, 1), (1, 1), (2, 1), (4, 1), (0, 2), (4, 2), (3, 2), (2, 2), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3), (4, 3), (0, 4), (1, 4), (4, 4), (3, 4), (0, 0), (0, 4), (0, 3), (0, 2), (1, 0), (1, 1), (1, 2), (1, 4), (2, 0), (2, 1), (2, 4), (2, 3), (3, 0), (3, 4), (4, 0), (4, 4), (4, 3)]


For example, (0, 0) appears twice!

And that's why I'm calling this solution "memory-heavy": we can get rid of duplicates by collecting everything into a HashSet. We don't even need to do it directly, that's what itertools's unique method does:

Rust code
    //             there it is 👇
let coords = all_visible.unique().collect_vec();

Shell session
$cargo run Compiling day8 v0.1.0 (/home/amos/bearcove/aoc2022/day8) Finished dev [unoptimized + debuginfo] target(s) in 0.50s Running target/debug/day8 found 23 coords: [(0, 0), (4, 0), (3, 0), (0, 1), (1, 1), (2, 1), (4, 1), (0, 2), (4, 2), (3, 2), (2, 2), (1, 2), (0, 3), (1, 3), (2, 3), (4, 3), (0, 4), (1, 4), (4, 4), (3, 4), (1, 0), (2, 0), (2, 4)]  Mhh. That's somehow still the wrong answer: we're only supposed to have 21 visible cells for the sample input. Let's filter out the ones on the edge to find our mistake: Rust code  // exclude the edges let all_visible = all_visible.filter(|coord| { coord.x > 0 && coord.x < grid.width() - 1 && coord.y > 0 && coord.y < grid.height() - 1 });  Shell session $ cargo run
Compiling day8 v0.1.0 (/home/amos/bearcove/aoc2022/day8)
Finished dev [unoptimized + debuginfo] target(s) in 0.62s
Running target/debug/day8
found 7 coords: [(1, 1), (2, 1), (3, 2), (2, 2), (1, 2), (1, 3), (2, 3)]


Looking at this, (2, 2) should not be visible: it's hidden by taller trees from the top, left, and bottom, and by a tree of the same height from the right:

 3  0  3  7  3
2  5  1  2
6 (3) 2
3  3  4  9
3  5  3  9  0


However, our prev_height <= curr_height check lets that slip.

We can change it to prev_height < curr_height, but that's incorrect, too! Since it'll now think this one is hidden:

 3  0  3  7  3
2  5  1  2
(5)<3> 3  2
3  3  5  4  9
3  3  9  0


Since the <3> is hidden by the three on its right. There's a bunch of ways to fix that (and at that point, I'm starting to think that solution is a bad idea), one of them is to use coalesce, so that when we consider this line from the right:

 6  5  3  3  2 <-


We're actually looking at this:

 6  5     3  2 <-


And so we have 4 cells visible.

Our code becomes:

Rust code
    let all_lines = all_rows.chain(all_cols);
let all_visible = all_lines.flat_map(|it| {
let mut it = it
.map(|coord| (coord, *grid.cell(coord).unwrap()))
.peekable();
// the first cell from the edge is always visible
let first = it.peek().unwrap().0;
std::iter::once(first).chain(
it.coalesce(|(a_coord, a_height), (b_coord, b_height)| {
if a_height == b_height {
Ok((a_coord, a_height))
} else {
Err(((a_coord, a_height), (b_coord, b_height)))
}
})
.tuple_windows()
.map_while(|((_prev_coord, prev_height), (curr_coord, curr_height))| {
if prev_height < curr_height {
Some(curr_coord)
} else {
None
}
}),
)
});
// exclude the edges
// let all_visible = all_visible.filter(|coord| {
//     coord.x > 0 && coord.x < grid.width() - 1 && coord.y > 0 && coord.y < grid.height() - 1
// });
let coords = all_visible.unique().collect_vec();

println!("found {} coords: {:?}", coords.len(), coords);


And it gives the correct answer for the sample input, but not my actual puzzle input.

So... bad idea? We give up?

Well... I like the concept, so I give it some more thought.

Consider this input:

-> 010203
^^ ^ ^


We have four trees visible here: 0, 1, 2 and 3. But our strategy from earlier doesn't work, because they're separated by shorter trees:

line: [(0, 0), (1, 0)]


I think we can just coalesce harder, to do this transform:

-> 010203
01 2 3

Rust code
                it.coalesce(|(a_coord, a_height), (b_coord, b_height)| {
if b_height <= a_height {
Ok((a_coord, a_height))
} else {
Err(((a_coord, a_height), (b_coord, b_height)))
}
})


And finally, that solution works.

## Part 2

In part 2, we must find the tree with the highest "scenic score", which is the product of how many trees you can see from a given tree.

They give for example this 5:

    
^
 <(5)>>
v
    
v
    

    


The example goes on:

• Looking up, its view is not blocked; it can see 1 tree (of height 3).
• Looking left, its view is blocked immediately; it can see only 1 tree (of height 5, right next to it).
• Looking right, its view is not blocked; it can see 2 trees.
• Looking down, its view is blocked eventually; it can see 2 trees (one of height 3, then the tree of height 5 that blocks its view).

And you know what, I think I've had enough iterators for one day.

Okay.. maybe a couple. So first, how many trees are vsible in a given direction:

Rust code
fn visible_trees_in_dir(grid: &Grid<usize>, coord: GridCoord, (dx, dy): (isize, isize)) -> usize {
let line = (1..).into_iter().map_while(|i| {
let coord = GridCoord {
};
Some(*grid.cell(coord)?)
});

let mut total = 0;
let our_height = *grid.cell(coord).unwrap();
for height in line {
total += 1;
if height >= our_height {
break;
}
}
total
}


(I found this part of the puzzle weird and confusing btw, because now trees don't hide each other: you can see trees of height 7, 6, 5 from a tree of size 7 for some reason. I'd like to see the 3D action replay on that one).

Then, a function to calculate the scenic score:

Rust code
fn scenic_score(grid: &Grid<usize>, coord: GridCoord) -> usize {
let dirs: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
dirs.into_iter()
.map(|(dx, dy)| visible_trees_in_dir(grid, coord, (dx, dy)))
.product()
}


(Note: I usually used take_while(...).count() + 1 for this but it's wrong: if we're at the edge, the score must be zero, not one).

And then, we bring it all together:

Rust code
fn main() {
let grid = parse_grid(include_str!("input.txt"));

let all_coords = (0..grid.height())
.into_iter()
.flat_map(|y| (0..grid.width()).map(move |x| GridCoord::from((x, y))));

let best_place = all_coords
.map(|coord| (coord, scenic_score(&grid, coord)))
.max_by_key(|(_, score)| *score)
.unwrap();

println!("{best_place:?}");
}
`

And just like that, we're done with day 8! 