Advent of Code 2022 - Day 08

ericwburden

Eric Burden

Posted on December 12, 2022

Advent of Code 2022 - Day 08

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)
}

Enter fullscreen mode Exit fullscreen mode

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
}

Enter fullscreen mode Exit fullscreen mode

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()
}

Enter fullscreen mode Exit fullscreen mode

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!

💖 💪 🙅 🚩
ericwburden
Eric Burden

Posted on December 12, 2022

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Advent of Code 2022 - Day 25
rust Advent of Code 2022 - Day 25

January 6, 2023

Advent of Code 2022 - Day 11
rust Advent of Code 2022 - Day 11

December 12, 2022

Advent of Code 2022 - Day 09
rust Advent of Code 2022 - Day 09

December 12, 2022

Advent of Code 2022 - Day 08
rust Advent of Code 2022 - Day 08

December 12, 2022

Advent of Code 2022 - Day 10
rust Advent of Code 2022 - Day 10

December 12, 2022