The day 8 challenge is to find a good spot for a treetop tree house in a forest. The elves explain a previous expedition has planted these trees as a reforestation effort, now they would like to determine what a good location for a tree house is.
The given input is a height map of rectangular shape (the forest), where each number represents the height of a single tree.
30373
25512
65332
33549
35390
Each number in the input represents one tree. Tree heights range from 0 to 9 from shortest to tallest.
Part 1
The elves ask you to determine whether there is enough tree cover to keep a tree house hidden. For this all trees need to be
counted which cannot be seen from outside the grid.
A tree is visible when all other trees in at least one direction left, right, up or down consists of shorter trees.
All trees at the edges are visible, therefore only the inner trees have to be considered.
For example the tree at position (2, 2) (center) has a height of 3 & is invisible.
- to the north it is blocked by a tree of height
5 - to the east is is blocked by a tree of same height
3 - to the south it is blocked by a
5 - to the west it is blocked by a
5
The task is to find the number of visible trees from the outside!
To determine the number of visible trees we need to determine the number of invisible ones. We know the total number of trees inside the forest and can deduct the invisible ones from it.
First let's parse the content of the input file into a grid structure. For that we put the heightmap into a single Vec instead
of a nested structure, which is a common approach. To reference a single entry the grid width & height are taken into account
to calculate an offset into the Vec. We will see later how this works.
#[derive(Debug)]
struct TreeGrid {
pub width: usize,
pub height: usize,
trees: Vec<u8>,
}
impl TreeGrid {
pub fn new() -> Self {
Self {
width: 0,
height: 0,
trees: Vec::new(),
}
}
pub fn add_line(mut self, mut line: Vec<u8>) -> Self {
self.width = line.len();
self.height += 1;
self.trees.append(&mut line);
self
}
pub fn visibles(&self) -> usize {
self.trees.len() - self.invisibles()
}
pub fn invisibles(&self) -> usize {
todo!()
}
}
fn parse(input: &str) -> TreeGrid {
input
.lines()
.map(str::trim)
.filter(|&line| !line.is_empty())
.fold(TreeGrid::new(), |grid, line: &str| {
let trees = line
.chars()
.filter_map(|c| c.to_string().parse::<u8>().ok())
.collect::<Vec<_>>();
grid.add_line(trees)
})
}
fn main() {
let grid = parse(include_str!("input.txt"));
}
This time it's fairly easy to parse the content, thankfully all rows contain the same number of tree heights. The parse function
splits the input as usual, moves any trailing / leading whitespace and removes empty lines. The latter is not strictly necessary but allows
for more readable formatting of data in the test module.
The Iterator::fold method takes an initial object, an empty TreeGrid and then iterates over all lines. The initial object is also passed into the closure as it is the return object of the closure.
To give an example to illustrate how fold works.
let numbers = [1, 2, 3, 4, 5];
let result = numbers.iter().fold(1, |product, value| product * value);
println!("Product: {}", result);
In this example the initial value in fold is 1, which is inferred as an i32. The closure takes two parameters the result of the previous iteration and the current number from the numbers array.
The closure needs to return an object of the same type i32. The closure multiplies the previous result with the number and returns it
thus calculating the product of all numbers as in 1 * 2 * 3 * 4 * 5.
Back to our case the fold closure splits the &str line into char entries & converts them into u8 values. We expect to only parse
numbers here, therefore no error handling is required. The program would panic if it encounters a non-digit character.
The new row of tree heights is then added to the grid variable. For convenience does TreeGrid::add_line return itself to be able
to simply return it in the closure. Otherwise we would to modify it first and then pass the grid variable as last line.
To see that all things are parsed correctly, the std::fmt::Display trait
can be implemented to output a representation of the height map. For this kind of struct this makes sense & can be helpful when debugging
the program.
impl Display for TreeGrid {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
for row in self.trees.chunks(self.width) {
for tree in row {
write!(f, "{}", tree)?;
}
write!(f, "\n")?;
}
Ok(())
}
}
By implementing Display for the TreeGrid struct it's easy to output the content to stdout using println.
fn main() {
let grid = parse(include_str!("input.txt"));
println!("{}", grid);
}
Copying the sample input from above into the input.txt should output the same height map.
To solve the first part we need a way to iterate over all inner trees (remember the edges are always visible) and to determine for each
tree if it's visible or not. For that method TreeGrid::invisibles will be implemented now.
To get things started a nested for loop will be used to iterate over all rows & columns of the forest. Then for each tree
the different directions are scanned.
impl TreeGrid {
pub fn invisibles(&self) -> u64 {
let mut invisibles = 0;
let directions: [(i32, i32); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];
for y in 1..(self.height - 1) as i32 {
for x in 1..(self.width - 1) as i32 {
let tree = self.get(x, y).unwrap() // should not fail
let is_invisible = directions.iter().all(|dir| {
let (mut dx, mut dy) = (x, y);
let mut steps = Vec::new();
while let Some(neighbor) = self.get(dx + dir.0, dy + dir.1) {
steps.push(neighbor);
dx += dir.0;
dy += dir.1;
}
steps.iter().any(|&neighbor| tree <= neighbor)
});
if is_invisible {
invisibles += 1;
}
}
}
invisibles
}
fn get(&self, x: i32, y: i32) -> Option<u8> {
if 0 <= x && x < self.width as i32 && 0 <= y && y < self.height as i32 {
Some(self.trees[(y * self.width as i32 + x) as usize])
} else {
None
}
}
}
fn main() {
let grid = parse(include_str!("input.txt"));
println!("Part 1: {}", part1(&grid));
}
#[cfg(test)]
mod tests {
#[test]
fn check_part1() {
let tree_grid = parse(INPUT);
assert_eq!(21, part1(&tree_grid));
}
}
The basic logic is to check for each inner tree if it's invisible. For each direction left, right, up & down
the list of trees (steps) is determined that need to be checked from the given tree to the edge.
The directions variable holds the movement vectors for each direction.
Once we get outside the forest the method TreeGrid::get will return a None otherwise it returns the height as a Some.
We consider a tree to be invisible when there is at least one other neighbor tree that is of the same height or taller in each direction.
Running the tests should result in sucess. Running the program should provide the first solution. yeah
Personally this can be improved quite a bit. The list of steps is generated for each direction & consists of all neighbors until the edge by using multiple variables to keep track of states.
Another reason to improve here is, the neighboring trees are determined before they are checked, which is particularly useful when
trees are found that are taller or even sized.
Another approach that should lead to more concise code is to implement our own Iterator.
Iterators
When we iterate or step the other trees in a direction the same logic is involved, except direction and starting tree differ.
What looks more promising is to have a directional iterator that steps to the next tree until either a condition is met to cancel or the edge of the grid is reached. Iterators run their closures lazily, meaning the result is evaluated, e.g. via collect, only when asked otherwise no iteration is performed.
Iterator methods also can also be used to stop iteration early (e.g. find) in case a given condition is met.
The logic inside the nested for loop can be improved further. After refactoring the code should be readable but more concise.
The most important aspect of the Iterator trait is only the single method next needs to be implemented. All other methods available in Iterator
implement their logic by calling next, therefore implementing the trait unlocks the full set of methods for us.
The std::iter::Iterator trait interface looks like:
trait Iterator {
type Item;
fn next(&mut self) -> Option<Self::Item>;
}
There are few resources out there that do a greab job of introduction iterators, the article Iterators written by Michael-F-Bryan is a good introduction. Ludwig's Creating an Iterator in Rust is also a good read that digs a bit deeper into iterators.
We start by implementing a Steps iterator to advance steps from the current position along a given direction. A common practice is to create
a new struct that holds all the information required to implement this Iterator.
struct Steps<'a> {
grid: &'a TreeGrid,
pos: (i32, i32),
dir: (i32, i32),
}
The struct Steps holds a reference to the TreeGrid a pos position for the tree by a tuple and a direction in field dir.
Both pos and dir declare a tuple of (i32, i32) to give positions. Using tuples like this feels a bit clunky, the underlying concept is a 2-dimensional vector or position. Therefore we extract this concept into its own struct named Pos.
#[derive(Debug, Clone, Copy)]
struct Pos {
x: i32,
y: i32,
}
impl Pos {
pub fn new(x: i32, y: i32) -> Self {
Self { x, y }
}
}
The Steps struct becomes then:
struct Steps<'a> {
grid: &'a TreeGrid,
pos: Pos,
dir: Pos,
}
impl<'a> Steps<'a> {
pub fn new(grid: &'a TreeGrid, pos: Pos, dir: Pos) -> Self {
Self { grid, pos, dir }
}
}
Another interesting part of the Steps struct is the lifetime annotation for its field grid in the type &'a TreeGrid. The struct takes a reference to TreeGrid. When we declare the struct without a lifetime annotation the compiler complains
error[E0106]: missing lifetime specifier
--> src/main.rs:42:11
|
42 | grid: &TreeGrid,
| ^ expected named lifetime parameter
|
help: consider introducing a named lifetime parameter
|
41 ~ struct Steps<'a> {
42 ~ grid: &'a TreeGrid,
This is the borrow checker telling us a lifetime parameter is required, because the Steps struct does not own the TreeGrid but holds a reference to it, therefore it needs to know about its lifetime.
The annotation helps the compiler determine for how long the reference lives, in this case at least as long as the object we borrow lives but not longer. It's then not possible to create a Steps struct without a TreeGrid, which means Steps cannot outlive TreeGrid.
The Steps::new method helps us to create this struct. An implementation of the Iterator may look then as follows:
impl<'a> Iterator for Steps<'a> {
type Item = u8;
fn next(&mut self) -> Option<Self::Item> {
self.pos.x = self.pos.x + self.dir.x;
self.pos.y = self.pos.y + self.dir.y;
self.grid.get(self.pos.x, self.pos.y)
}
}
The pos property is advanced by the direction dir. Then the tree height from TreeGrid is fetched using the get method. This works because
TreeGrid::get returns an Option<u8> which matches the return type of the next function. There is still room for improvement here, in particular the calculation of the next pos value.
For mathmatical calculations if often is more concise to implement traits to support using + or += on custom types. In this case we could implement std::ops::Add (+) or AddAssign (+=). Let's implement both and update the Steps implementation.
impl std::ops::Add for Pos {
type Output = Pos;
fn add(self, rhs: Self) -> Self::Output {
Pos::new(self.x + rhs.x, self.y + rhs.y)
}
}
impl std::ops::AddAssign for Pos {
fn add_assign(&mut self, rhs: Self) {
self.x += rhs.x;
self.y += rhs.y;
}
}
impl<'a> Iterator for Steps<'a> {
type Item = u8;
fn next(&mut self) -> Option<Self::Item> {
self.pos += self.dir;
self.grid.get(self.pos)
}
}
We also refactor the function interface of TreeGrid::get to accept a Pos as well. Now the functio can be refactored to use the Steps iterator.
impl TreeGrid {
pub fn invisibles(&self) -> u64 {
let mut invisibles = 0;
let directions: [(i32, i32); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];
for y in 1..(self.height - 1) as i32 {
for x in 1..(self.width - 1) as i32 {
let tree = self.get(x, y).unwrap() // should not fail
let is_invisible = directions.iter().all(|dir| {
self.steps(Pos::new(x, y), Pos::new(dir.0, dir.1))
.any(|neighbor| tree <= neighbor)
});
if is_invisible {
invisibles += 1;
}
}
}
invisibles
}
fn steps(&self, pos: Pos, dir: Pos) -> Steps {
Steps::new(self, pos, dir)
}
}
This reads a bit better, but there is a chance to refactor even further. One, the directions variable uses still tuples, for which we will
re-use Pos instead of adding another type.
The content of directions does not change, we'll extract that into a constant.
impl TreeGrid {
const DIRECTIONS: [Pos; 4] = [
Pos::new(0, -1), // up
Pos::new(0, 1), // right
Pos::new(-1, 0), // left
Pos::new(1, 0), // down
];
}
Once refactored the new code will raise a compile error, because Pos::new is a non-const function.
Let's update the function into a const function.
impl Pos {
// 👇
pub const fn new(x: i32, y: i32) -> Self {
Self { x, y }
}
}
The updated method TreeGrid::invisibles:
impl TreeGrid {
pub fn invisibles(&self) -> u64 {
let mut invisibles = 0;
for y in 1..(self.height - 1) as i32 {
for x in 1..(self.width - 1) as i32 {
let tree = self.get(x, y).unwrap();
let is_invisible = Self::DIRECTIONS.iter().all(|&dir| {
self.steps(Pos::new(x, y), dir)
.any(|neighbor| tree <= neighbor)
});
if is_invisible {
invisibles += 1;
}
}
}
invisibles
}
}
Iterating over all rows & columns needs to take care of boundaries, only inner trees are considered by using width & height.
The pair x, y provides the tree coordinates, while tree is the height. We could leave it at that or use a tree iterator that
iterates over all inner trees. This resembles the Steps in a way but instead of only yielding the height, we want position and tree height.
struct TreeIter<'a> {
grid: &'a TreeGrid,
pos: Pos,
}
impl<'a> TreeIter<'a> {
pub fn new(grid: &'a TreeGrid) -> Self {
Self {
grid,
pos: Pos::new(1, 1),
}
}
}
impl<'a> Iterator for TreeIter<'a> {
type Item = (Pos, u8);
fn next(&mut self) -> Option<Self::Item> {
todo!()
}
}
Similar to the Steps struct we maintain what is required to iterate over all elements. The Iterator returns a Option<(Pos, u8)> to hold
position and height. The internal pos field is initially set to the first inner tree at 1, 1.
The boundary checks & ranges from the nested for loop above will be covered in the next method to ensure only inner trees are visited.
pos will be updated for each iteration similar to how Cathode-Ray Tube works.
impl<'a> Iterator for TreeIter<'a> {
type Item = (Pos, u8);
fn next(&mut self) -> Option<Self::Item> {
let pos = self.pos + Pos::new(1, 0);
let pos = if pos.x >= self.grid.width as i32 - 1 {
Pos::new(1, pos.y + 1)
} else {
pos
};
self.pos = pos;
if pos.y >= self.grid.height as i32 - 1 {
None
} else {
Some((pos, self.grid.get(pos).expect("Failed to get tree")))
}
}
}
Using the TreeIter iterator we can walk all inner trees, yield its position and height in each iteration.
The updated version of TreeGrid::invisibles with the new iterator then looks like:
impl TreeGrid {
pub fn invisibles(&self) -> u64 {
let mut invisibles = 0;
for (pos, tree) in self.trees() {
let is_invisible = Self::DIRECTIONS.iter().all(|&dir| {
self.steps(pos, dir)
.any(|neighbor| tree <= neighbor)
});
if is_invisible {
invisibles += 1;
}
}
invisibles
}
fn trees(&self) -> TreeIter {
TreeIter::new(self)
}
}
This refactoring changes the nested for loop into a single for loop that yield position and height for every inner tree.
Because we are using iterators here we can refactor even further and eliminate the invisibles variable completely.
What the algorithm does is to count all invisible trees, therefore we can filter over all trees and simply count at the end.
impl TreeGrid {
pub fn invisibles(&self) -> usize {
self.trees()
.filter(|&(pos, tree)| {
Self::DIRECTIONS
.iter()
.all(|&dir| self.steps(pos, dir).any(|neighbor| tree <= neighbor))
})
.count()
}
}
And that's it. What I like about this approach the most is the method itself became more concise while still expressing the algorithm conceptually. By using iterators we were able to compose the function blocks separately without having to reveal or grasp all the lower level details.
Update, upon further inspection of the TreeIter I wondered why the iterator itself looks so verbose. It does its job as it is,
but I checked the itertools crate again. I remembered there was a method to span elements over ranges in a 2-dimensional fashion.
What the nested for loop over the x & y coordinates does is a cartesian product.
The itertools crate provides such a function named cartesian_product to get the product of two iterators.
Using the cartesian product between of two ranges we can generate all coordinate pairs for all trees, yield the position & height of each tree.
This will eliminate the TreeIter completely.
impl TreeGrid {
// 👇 - replaces function
fn trees(&self) -> impl Iterator<Item = (Pos, u8)> + '_ {
(1..self.width as i32 - 1)
.cartesian_product(1..self.height as i32 - 1)
.map(|(x, y)| (Pos::new(x, y), self.get(Pos::new(x, y)).unwrap()))
.into_iter()
}
}
The logic is still the same but we got rid of TreeIter, this works because the return type was not bound to it, but rather uses
the more generic trait interface. Happy times.
Part 2
The second part of the task is to find the best spot for a tree house. The elves have one wish the tree house should see a lot of trees. Trees at the edge are ignored as they will have one direction without any trees. To measure the distance the tree under consideration should provide good sight in all directions. As before the directions left, right, up and down are scanned. This time the view line ends when there is a tree of same height or taller than the candidate.
Given the example input
30373
25512
65332
33549
35390
the tree at position 2, 1 with a height of 5 has the viewing distances 1 (up), 1 (left), 2 (right) and 2 (down).
A scenic score is calculated as the product of these viewing distances, therefore 1 * 1 * 2 * 2 results in 4
The task is to find the tree with the higest scenic score. We expand the code with a test from the given sample.
impl TreeGrid {
pub fn best_scenic(&self) -> Option<usize> {
todo!()
}
}
fn part2(grid: &TreeGrid) -> usize {
grid.best_scenic()
.expect("Failed to find the most scenic tree")
}
fn main() {
let grid = parse(include_str!("input.txt"));
println!("Part 1: {}", part1(&grid));
println!("Part 2: {}", part2(&grid));
}
#[cfg(test)]
mod tests {
//
#[test]
fn check_part2() {
let tree_grid = parse(INPUT);
assert_eq!(8, part2(&tree_grid));
}
}
The code adds the logic to set up a solution for the 2nd part. What's left to implement is method TreeGrid::best_scenic.
The idea this time is to determine the scenic value for every inner tree. The trees on the edges do not have to be considered,
their scores result in 0.
One aspect I was struggling with was to come up with the condition to break scanning a given direction, when a tree of the same size or taller is found. One approach I choose in such situation is to extract & seperate this specific out of into its own function. This help me figure out what a working version may look like while the higher level structure matches the algorithm.
We will use the iterators from before. This way the logic follows a similar pattern but with a different outcome.
pub fn scan_trees(tree: u8, iter: impl Iterator<Item = u8>) -> usize {
let mut count = 0;
for neighbor in iter {
count += 1;
if neighbor >= tree {
break;
}
}
count
}
Here a new function named scan_trees takes the height of the current tree and the list of heights for all next steps.
The iter parameter is quite generic, we could also have used the Steps type directly and have passed that in.
Depending on the context one iterator might be more useful over the other, even when their interfaces, in particular the type they return is the same.
What the type impl Iterator<Item = u8> expresses is that any type that meets this trait bound can be passed in. For our purpose
this is type Steps. The completed TreeGrid::best_scenic method can look like:
impl TreeGrid {
pub fn best_scenic(&self) -> Option<usize> {
self.trees()
.map(|(pos, tree)| {
Self::DIRECTIONS.iter().fold(1, |product, &dir| {
product * scan_trees(tree, self.steps(pos, dir))
})
})
.max()
}
}
The trees method returns an impl Iterator<Item = (Pos, u8)> + '_ over all inner trees (see above),
for each pos & tree height the scenic score is determined by multiplying distances of all directions.
The scores are calculated for all inner trees. The last call to max returns the one with the highest score.
Once the function is in place, we can check the tests again. Running the program should now return the solution for the second part.