Day 8: Treetop Tree House
https://adventofcode.com/2022/day/8
TL;DR: my solution in Rust
The explained solution is based on (and almost identical to) Henry's solution.
Thank you Henry!
The expedition visits a perfectly rectangular grid of trees the elves planted on a previous visit.
The elves would like to build a treehouse in one of the trees.
They sent up a drone to measure the height of each tree, expressed in a single digit: 0-9.
Your input is the height of every tree in the grid.
An example input looks like this:
30373
25512
65332
33549
35390
Parsing the input
Turn that input into a 2 dimensional list.
- Each item is a row.
- Each row is a list of digits.
fn parse() -> Vec<Vec<u32>> {
let input = std::fs::read_to_string("src/day08.txt").unwrap();
input
.lines()
.map(|line| line.chars().map(|c| c.to_digit(10).unwrap()).collect())
.collect()
}
Part 1
The question asks to count the number of trees that are visible from outside the grid when looking directly along a row or column.
A tree is visible if all of the other trees between it and an edge of the grid are shorter than it.
Only consider trees in the same row or column.
That means you can only look in 4 directions from each tree: up, down, left, and right.
All of the trees around the edge of the grid are visible.
The goal is to determine the visibilty of every tree in the grid.
If a tree is visible from multiple directions, only count it once.
Then count the amount of visible trees.
In pseudocode, that would be:
all_trees
.map(/* determine visibility of this tree */)
.filter(/* keep visible trees */)
.count()
The interesting part is the step where we figure out if a tree is visible (from any direction).
Loop through every set of indexes in the grid. (the height of a tree is found by indexing into our parsed input: grid[row_idx][col_idx]
)
Because all the trees along the edges are visible, skip those.
At the end of the loop, add the amount of trees along the 4 edges to the amount of visible trees you just calculated.
A neat way to loop through all indexes in a grid is the
cartesian_product
method.It's the same thing as doing a manual double for loop.
for row_idx in 0..len { for col_idx in 0..len { // your logic } }
The skeleton code now looks like this:
use itertools::Itertools;
let grid = parse();
let len = grid.len();
// loop through coordinates of all trees that are not at an edge
(1..len - 1)
.cartesian_product(1..len - 1)
.map(|(y, x)| {
// Is this tree visible from any direction? true/false
todo!();
})
.filter(|visible| *visible)
.count()
// add number of trees at edges, they are all visible
+ (len - 1) * 4
The most important sentence for part1: A tree is visible if all of the other trees between it and an edge of the grid are shorter than it.
A helper function
For a given pair of indexes, this function returns a 4 lists.
Each list holds the remaining trees in one direction of the grid (up, down, left, right),
from the perspective of the tree at those indexes.
Implementation
Extract the current row
and column
from the grid for a set of indexes.
Split those variables in 2 based on the col
, and row
index respectively.
- The split
column
returns the trees to thetop
, and to thebottom
of therow
index. - The split
row
returns the trees to theleft
, and to theright
of thecol
index.
Confusing
row
andcol
is a very common thing to do when indexing into a rectangular grid
Because this function returns the trees visible from the perspective of the tree at that pair of indexes,
the the up
, and the left
lists need to be reversed.
fn directions(grid: &[Vec<u32>], x: usize, y: usize) -> [Vec<u32>; 4] {
let row = grid[y].clone();
let column = grid.iter().map(|row| row[x]).collect::<Vec<u32>>();
let (up, down) = column.split_at(y);
let (left, right) = row.split_at(x);
let up = up.iter().copied().rev().collect();
let left = left.iter().copied().rev().collect();
let right = right[1..].to_vec();
let down = down[1..].to_vec();
[up, down, left, right]
}
Back to the main solution.
Updated skeleton code:
use itertools::Itertools;
let grid = parse();
let len = grid.len();
(1..len - 1)
.cartesian_product(1..len - 1)
.map(|(y, x)| {
directions(&grid, x, y)
.iter()
// is the tree at x,y visible from this direction: true/false
.map(|direction| { todo!(); })
// count a tree that is visible from multiple directions only once
.any(|visible| visible)
})
.filter(|visible| *visible)
.count()
+ (len - 1) * 4
And that "most important sentence" is the way we figure out if a tree is visible.
Reminder of that sentence: A tree is visible if all of the other trees between it and an edge of the grid are shorter than it.
Final code
use itertools::Itertools;
fn parse() -> Vec<Vec<u32>> {
let input = std::fs::read_to_string("src/day08.txt").unwrap();
input
.lines()
.map(|line| line.chars().map(|c| c.to_digit(10).unwrap()).collect())
.collect()
}
fn directions(grid: &[Vec<u32>], x: usize, y: usize) -> [Vec<u32>; 4] {
let row = grid[y].clone();
let column = grid.iter().map(|row| row[x]).collect::<Vec<u32>>();
let (up, down) = column.split_at(y);
let (left, right) = row.split_at(x);
let up = up.iter().copied().rev().collect();
let left = left.iter().copied().rev().collect();
let right = right[1..].to_vec();
let down = down[1..].to_vec();
[up, down, left, right]
}
pub fn part_1() -> usize {
let trees = parse();
let len = trees.len();
(1..len - 1)
.cartesian_product(1..len - 1)
.map(|(y, x)| {
let height = trees[y][x];
directions(&trees, x, y)
.iter()
.map(|direction| direction.iter().all(|h| *h < height))
.any(|visible| visible)
})
.filter(|visible| *visible)
.count()
+ (len - 1) * 4
}
Part 2
The elves would like to be able to see a lot of trees from their treehouse.
The question asks what the highest scenic score possible is.
A scenic score is a way to express how good the viewing distance in each direction is.
It's the product of the amount of trees that are visible in the 4 directions.
To measure the viewing distance from a given tree, look up, down, left, and right from that tree;
stop if you reach an edge or at the first tree that is the same height or taller than the tree under consideration.
(If a tree is right on the edge, at least one of its viewing distances will be zero.)
The goal is to calculate a scenic score for every tree, and find that maximum of those scores.
In pseudocode that would be:
all_trees
.map(/* calculate scenic score */)
.max()
.unwrap()
The main setup for part2 is the same as part1.
The interesting part is inside that .map
where we convert a pair of indexes to a scenic score.
For a given pair of indexes, that map first determines how many trees are visible in every direction.
Then it takes the product of those 4 numbers to get the tree's scenic score.
In skeleton code:
use itertools::Itertools;
let grid = parse();
let len = grid.len();
(1..len - 1)
.cartesian_product(1..len - 1)
.map(|(y, x)| {
directions(&grid, x, y)
.iter()
// how many trees are visible in this direction?
.map(|direction| { todo!(); })
// multiply the results of each direction to calculate the scenic score
.product()
})
.max()
.unwrap()
The most important sentence in the question for part2: To measure the viewing distance from a given tree, look up, down, left, and right from that tree; stop if you reach an edge or at the first tree that is the same height or taller than the tree under consideration.
And that “most important sentence” is the way we figure out how many trees are visible in a direction.
Final code
use itertools::Itertools;
fn parse() -> Vec<Vec<u32>> {
let input = std::fs::read_to_string("src/day08.txt").unwrap();
input
.lines()
.map(|line| line.chars().map(|c| c.to_digit(10).unwrap()).collect())
.collect()
}
fn directions(grid: &[Vec<u32>], x: usize, y: usize) -> [Vec<u32>; 4] {
let row = grid[y].clone();
let column = grid.iter().map(|row| row[x]).collect::<Vec<u32>>();
let (up, down) = column.split_at(y);
let (left, right) = row.split_at(x);
let up = up.iter().copied().rev().collect();
let left = left.iter().copied().rev().collect();
let right = right[1..].to_vec();
let down = down[1..].to_vec();
[up, down, left, right]
}
pub fn part_2() -> usize {
let trees = parse();
let len = trees.len();
(1..len - 1)
.cartesian_product(1..len - 1)
.map(|(y, x)| {
let height = trees[y][x];
directions(&trees, x, y)
.iter()
.map(|direction| {
direction
.iter()
.position(|h| *h >= height)
.map(|p| p + 1)
.unwrap_or_else(|| direction.len())
})
.product::<usize>()
})
.max()
.unwrap()
}
Top comments (0)