Thanks to my sponsors: Sean Bryant, nyangogo, Tyler Schmidtke, Richard Pringle, Evan Relf, you got maiL, Aleksandre Khokhiashvili, jer, L0r3m1p5um, Zachary Thomas, ofrighil, Justin Ossevoort, Max Heaton, avborhanian, Chris Biscardi, compwhizii, David White, Manuel Hutter, Raine Tingley, Cass and 235 more
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:
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:
Aiming for correctness with types
The Nature weekly journal of science was first published in 1869. And after one and a half century, it has finally completed one cycle of carcinization, by publishing an article about the Rust programming language.
It's a really good article.
What I liked about this article is that it didn't just talk about performance, or even just memory safety - it also talked about correctness.