It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!
Day 08 - Treetop Tree House
Find the problem description HERE.
The Input - The Forest Obscures the Trees
Parsing for today’s input is really straightforward. My approach here is just to turn the big block of numbers (as text) into a two-dimensional Vec of…numbers! I’ll keep a bit of metadata with that grid, but that’s pretty much it.
/// Represents our overall view of the trees. Really just a two-dimensional vector
/// of the input characters, converted to numbers, with the number of rows and
/// columns brought along for the ride.
#[derive(Debug)]
struct TreeView {
row_len: usize,
col_len: usize,
trees: Vec<Vec<u8>>,
}
/// Parser a TreeView from the input file. No parser combinators today, since they're
/// almost entirely unnecessary for this one.
impl From<&str> for TreeView {
fn from(input: &str) -> Self {
let row_len = input.lines().count();
let col_len = input.lines().next().unwrap().len();
// I like this syntax of assigning little closures to variables for
// use in iterator chains. It reminds me of a Julia "style".
let line_to_nums = |s: &str| s.chars().map(|c| c as u8 - b'0').collect();
let trees: Vec<Vec<_>> = input.lines().map(line_to_nums).collect();
TreeView {
row_len,
col_len,
trees,
}
}
}
const INPUT: &str = include_str!("../../input/08/input.txt");
/// Read the input file and convert it to a `TreeView`
pub fn read() -> TreeView {
TreeView::from(INPUT)
}
No nom parsing today, it just seemed like too much overkill to warrant it.
Part One - You Can’t See Me
Oooh, the elves have a quadcopter! I don’t care if they’re being controlled by a benevolent (if mischievous) AI, they have the best toys! Which, in retrospect, seems like something I should probably have understood about elves before now. For this first part, we need to identify which trees can be seen from the outside of the grid, meaning there are no trees the same height or taller in front of them. I’ll be honest, I really tried to write a nicer implementation for this part, but in the end it’s really just a bunch of loops.
/// Solve Day 8, Part 1
fn solve(input: &TreeView) -> u32 {
// Start with a two-dimensional vector the same size as the input,
// filled with `false`. So far, we can't see any trees!
let mut visibility_map = vec![vec![false; input.col_len]; input.row_len];
// For each row of trees...
for row_idx in 0..input.row_len {
// The tallest tree found so far has a height of 0
let mut tallest = 0;
// For each column from left to right...
for col_idx in 0..input.col_len {
// Take the tree at that position
let tree = input.trees[row_idx][col_idx];
// If it's taller than the current `tallest` OR it's on the left
// or right edge, then set that tree to visible and update the
// tallest found so far.
if tree > tallest || col_idx == 0 || col_idx == (input.col_len - 1) {
visibility_map[row_idx][col_idx] = true;
tallest = tree;
}
}
// Reset `tallest` and do the same thing again from right to left. There's
// no need to attend to the edges again on this round.
tallest = 0;
for col_idx in 0..input.col_len {
let tree = input.trees[row_idx][col_idx];
if tree > tallest {
visibility_map[row_idx][col_idx] = true;
tallest = tree;
}
}
}
// Now scan the columns from top to bottom and bottom to top
for col_idx in 0..input.col_len {
// Same deal, except this time we'll also trigger the visibility update
// on the top and bottom rows, as well.
let mut tallest = 0;
for row_idx in 0..input.row_len {
let tree = input.trees[row_idx][col_idx];
if tree > tallest || row_idx == 0 || row_idx == (input.row_len - 1) {
visibility_map[row_idx][col_idx] = true;
tallest = tree;
}
}
// If you guess "reset the tallest height and scan from bottom to top",
// the you guessed right!
tallest = 0;
for row_idx in (0..input.row_len).rev() {
let tree = input.trees[row_idx][col_idx];
if tree > tallest {
visibility_map[row_idx][col_idx] = true;
tallest = tree;
}
}
}
// Count the number of visible trees in the visibility map and return the count
let found = visibility_map
.iter()
.flat_map(|row| row.iter())
.filter(|x| **x)
.count() as u32
}
I actually wrote a version that used iterators and scans that was quite a bit more concise, but it also ran in about twice the time as the version above. In the end, I decided the syntax wasn’t bad enough to warrant the slowdown. I could probably factor out the four inner loops if I really wanted to, but I figure that would be harder to follow.
Part Two - A Room With a View
Yeah, I mean, if you’re going to build a treehouse, picking the tree with the best view is just a no-brainer. We can help pick out which tree that is by checking the sightlines in cardinal directions from each tree and identifying the one that can see over the most other trees. As before, I wrote a version of this code that used lots of iterators and scans, but…super slow. So,for loops it is!
use std::cmp::{max, min};
/// Solve Day 8, Part 2
fn solve(input: &TreeView) -> u32 {
// This time, we'll instantiate a 2D vector the same size and shape as our
// view of the trees, just filled with zeros!
let mut scenic_score_map = vec![vec![0u32; input.col_len]; input.row_len];
// Pre-computing a list of all the row/column indices so we only have
// one `for` loop below instead of two. Keeps the nesting down.
let indices = (0..input.row_len).flat_map(|r| (0..input.col_len).map(move |c| (r, c)));
// For each tree location in the forest...
for (row_idx, col_idx) in indices {
// If we're on an edge of the map, just skip it. It'll be zero regardless.
if row_idx == 0
|| col_idx == 0
|| row_idx == (input.row_len - 1)
|| col_idx == (input.col_len - 1)
{
continue;
}
// The tree at our current location
let tree = input.trees[row_idx][col_idx];
// From our tree, loop up and count the number of trees visible. We do this
// by iterating over the positions in the same column and in rows above our
// current tree until we either reach the edge or hit a tree our own height.
let mut can_see_up = 0;
for seek_idx in (0..row_idx).rev() {
let found = input.trees[seek_idx][col_idx];
can_see_up += 1;
if found >= tree {
break;
}
}
// Same deal, just looking down.
let mut can_see_down = 0;
for seek_idx in (row_idx + 1)..input.row_len {
let found = input.trees[seek_idx][col_idx];
can_see_down += 1;
if found >= tree {
break;
}
}
// Same deal, just looking left
let mut can_see_left = 0;
for seek_idx in (0..col_idx).rev() {
let found = input.trees[row_idx][seek_idx];
can_see_left += 1;
if found >= tree {
break;
}
}
// Same deal, just looking right
let mut can_see_right = 0;
for seek_idx in (col_idx + 1)..input.col_len {
let found = input.trees[row_idx][seek_idx];
can_see_right += 1;
if found >= tree {
break;
}
}
// Calculate the scenic score of this tree as the product of all the
// counts from looking up, down, left, and right
scenic_score_map[row_idx][col_idx] =
can_see_up * can_see_down * can_see_left * can_see_right;
}
// Now we just loop over the 2D map and return the largest score found
scenic_score_map
.iter()
.flat_map(|row| row.iter())
.copied()
.max()
.unwrap()
.into()
}
Again, it’s quite a bit of code, but there’s nothing really complicated going on there. The biggest performance improvement is just stopping on each sightline when a tree as tall as yours or taller is encountered. Otherwise, it’s loops and breaks all the way down!
Wrap Up
I spent way too much time on today’s puzzle figuring out that just because you_can_ use iterarators doesn’t mean you should use iterators. It was also an object lesson in the idea that you have to test performance because your intuition about what code will run faster can be very wrong at times. Sometimes, simplest really is best! Other than that, this was our first “2D Grid” puzzle of Advent of Code, and as such, it didn’t disappoint! I’m sure we’ll see more puzzles like this in days to come. I hope to see you there!
Top comments (0)