Home
Log in
Avatar for fasterthanlime fasterthanlime
Dec 09, 2022 clock icon 16 min #rust · #advent-of-code · #iterators

Day 8 (Advent of Code 2022)

From the series Advent of Code 2022
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

👋 This page was last updated ~2 years ago. Just so you know.

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:

Rust code
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:

Rust code
// 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:

Rust code
// 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
}
Shell session
$ 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:

TOML markup
[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:

Rust code
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:

Shell session
$ 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:

Rust code
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:?}");
    }
}
Shell session
$ 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:

Shell session
$ cargo add itertools
(cut)
Rust code
// 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:

Shell session
$ 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:

Rust code
    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);
Shell session
$ 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:

Rust code
    //             there it is 👇
    let coords = all_visible.unique().collect_vec();
Shell session
$ 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:

Rust code
    // 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
    });
Shell session
$ 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:

Rust code
    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.

Bear

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
Rust code
                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:

Rust code
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:

Rust code
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:

Rust code
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!

You're reading the Advent of Code 2022 series.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Reddit logo Comment on /r/fasterthanlime

If you liked what you saw, please support my work!

Github logo Donate on GitHub Patreon logo Donate on Patreon

Here's another article just for you:

The HTTP crash course nobody asked for
Oct 20, 2022
clock icon 1 hour 59 min #http · #rust

HTTP does a pretty good job staying out of everyone's way.

If you're reading this article, there's a solid chance it was delivered to you over HTTP. Even if you're reading this from an RSS reader or something. And you didn't even have to think about it!

"Not having to think about it" is certainly a measure of success for a given technology. By contrast, . I wish I didn't.

Read more