Day 8 (Advent of Code 2022)
fasterthanlime
This article is part of the Advent of Code 2022 series.
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:
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:
// 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:
// 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()));
todo!("answer part 1");
}
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
}
$ 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:
[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:
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:
$ 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:
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:?}");
}
}
$ 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:
$ cargo add itertools (cut)
// 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:
$ 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:
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);
$ 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:
// there it is 👇
let coords = all_visible.unique().collect_vec();
$ 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:
// 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
});
$ 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:
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
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:
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 {
x: coord.x.checked_add_signed(dx * i)?,
y: coord.y.checked_add_signed(dy * i)?,
};
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:
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:
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!
This article is part 8 of the Advent of Code 2022 series.
If you liked what you saw, please support my work!
