Dec 09, 2022

8 min #rust · #advent-of-code · #iterators

Day 8 (Advent of Code 2022)

From the series Advent of Code 2022

18

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

In the day 8 problem, our input is a height map:

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:

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:

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:

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

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

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

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

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:

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

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:?}");
    }
}

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

$ cargo add itertools
(cut)

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

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

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

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

    //             there it is 👇
    let coords = all_visible.unique().collect_vec();

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

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

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

    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.

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

                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:

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:

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:

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

Comment on /r/fasterthanlime

(JavaScript is required to see this. Or maybe my stuff broke)

Here's another article just for you:

A terminal case of Linux

Sep 24, 2021

29 min #rust · #linux

Has this ever happened to you?

You want to look at a JSON file in your terminal, so you pipe it into jq so you can look at it with colors and stuff.

Cool Bear's Hot Tip

That’s a useless use of cat.

…oh hey cool bear. No warm-up today huh.

Sure, fine, okay, I’ll read the darn man page for jq… okay it takes a “filter” and then some files. And the filter we want is.. . which, just like files, means “the current thing”: