Thanks to my sponsors: Matthew T, Manuel Hutter, Sylvie Nightshade, Hadrien G., Adam Lassek, Dylan Anthony, Jack Duvall, Laine Taffin Altman, Geoff Cant, Diego Roig, Enrico Zschemisch, Zoran Zaric, Ronen Ulanovsky, James Rhodes, John VanEnk, Christian Bourjau, Marie Janssen, clement, Marcin Kołodziej, Moritz Lammerich and 243 more
8 min
Day 8 (Advent of Code 2022)
👋 This page was last updated ~2 years ago. Just so you know.
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!
Here's another article just for you:
The HTTP crash course nobody asked for
1 hour 3 min
HTTP does a pretty good job staying out of everyone's way.
If you're reading this article, there's a solid chance it was delivered to you over HTTP. Even if you're reading this from an RSS reader or something. And you didn't even have to think about it!
"Not having to think about it" is certainly a measure of success for a given technology. By contrast, . I wish I didn't.