Home

# Day 8 (Advent of Code 2022) From the series 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
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 {
};
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 [5] 1  2
6 [5](3)[3] 2
3  3 [5] 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] 5  1  2
[6](5)<3> 3  2
3  3  5  4  9
3 [5] 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`:

```[3] [0] [3] [7] [3]
^
[2] [5]<(5)>[1]>[2]
v
[6] [5] [3] [3] [2]
v
[3] [3] [5] [4] [9]

[3] [5] [3] [9] [0]
```

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!