Home Log in

Dec 14, 2020

14 min #rust · #advent-of-code

Day 3 (Advent of Code 2020)

From the series Advent of Code 2020

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

Hello all, and welcome back to Advent of Code 2020, featuring Cool Bear.

Hey y'all!

Let's get right to it.

The problem statement for Day 3 is as follows: we're given a map, that looks like this:

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

And we imagine that it repeats infinitely to the right, like so:

..##.........##....... (etc.)
#...#...#..#...#...#.. (etc.)
.#....#..#..#....#..#. (etc.)
..#.#...#.#..#.#...#.# (etc.)
.#...##..#..#...##..#. (etc.)
..#.##.......#.##..... (etc.)
.#.#.#....#.#.#.#....# (etc.)
.#........#.#........# (etc.)
#.##...#...#.##...#... (etc.)
#...##....##...##....# (etc.)
.#..#...#.#.#..#...#.# (etc.)

Our sled starts from the top-left position and each time it moves 3 to the right and one to the bottom. The question is, how many trees are we going to encounter if we follow that path?

There's probably a couple ways to go about this, but when I see a problem like this, I think of a 2D map (with x-wrapping). It brings me back to my gamedev days!

Shell session

$ cargo new day3
     Created binary (application) `day3` package

Let's try to think in terms of types again.

We're going to need to represent positions on the map somehow. We could pass x, y or col, row to every function, or we could make a type for that.

We'll used signed numbers, so that we could technically represent positions to the left of 0, assuming the map wraps around on both the left and right side:

Rust code

#[derive(Debug, Clone, Copy, PartialEq)]
struct Vec2 {
    x: i64,
    y: i64,
}

For convenience, we'll allow building a Vec2 from a tuple:

Rust code

impl From<(i64, i64)> for Vec2 {
    fn from((x, y): (i64, i64)) -> Self {
        Self { x, y }
    }
}

Let's even write a test for that:

Rust code

#[test]
fn test_tuple() {
    let v: Vec2 = (5, 8).into();
    assert_eq!(v.x, 5);
    assert_eq!(v.y, 8);
}

We're also going to want a type that represents what's in a tile:

Rust code

#[derive(Clone, Copy, PartialEq)]
enum Tile {
    Open,
    Tree,
}

By default, all tiles are open:

Rust code

impl Default for Tile {
    fn default() -> Self {
        Self::Open
    }
}

We'll also add a Debug implementation that writes out a graphical representation of the tile:

Rust code

use std::fmt;

impl fmt::Debug for Tile {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let c = match self {
            Tile::Open => '.',
            Tile::Tree => '#',
        };
        write!(f, "{}", c)
    }
}

Our Map type can be a struct, with only a couple fields: its size, and a Vec of all the tiles it contains:

Rust code

struct Map {
    size: Vec2,
    tiles: Vec<Tile>,
}

And from there, we'll need a couple methods:

Rust code

impl Map {
    fn new(size: Vec2) -> Self {
        todo!()
    }

    fn set(&mut self, pos: Vec2, tile: Tile) {
        todo!()
    }

    fn get(&self, pos: Vec2) -> Tile {
        todo!()
    }
}

Let's start with the easiest one: new.

We're storing all tiles in a flat array, in row-major order, which means we're storing all tiles from the top row first, then we move on to the second row, etc.

All we need to do in new is fill it out with the default value:

Rust code

impl Map {
    fn new(size: Vec2) -> Self {
        let num_tiles = size.x * size.y;
        Self {
            size,
            tiles: (0..num_tiles)
                .into_iter()
                .map(|_| Default::default())
                .collect(),
        }
    }
}

Let's also implement Debug for the map, so we can know what's on it:

Rust code

impl fmt::Debug for Map {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for row in 0..self.size.y {
            for col in 0..self.size.x {
                write!(f, "{:?}", self.get((col, row).into()))?;
            }
            writeln!(f)?;
        }
        Ok(())
    }
}

This relies on get, so... we need to start thinking about get.

The first thing we want to do with the pos argument to get is to "wrap" the X position, so our map conceptually extends forever to the right. We'll also extend it to the left, for consistency.

Let's use a helper function for that:

Rust code

impl Map {
    fn normalize_pos(&self, pos: Vec2) -> Option<Vec2> {
        if pos.y < 0 || pos.y >= self.size.y {
            None
        } else {
            let x = if pos.x < 0 {
                // wrap around for positions to the left of 0
                self.size.x - (pos.x % self.size.x)
            } else {
                // wrap around for positions to the right of self.size.x
                pos.x % self.size.x
            };
            Some((x, pos.y).into())
        }
    }
}

Note that this function will return None for positions outside the map: since, conceptually, our map is infinitely wide, but it has a finite height.

Then, we can make a second helper function that returns the index of a tile in our flat storage:

Rust code

impl Map {
    fn index(&self, pos: Vec2) -> Option<usize> {
        self.normalize_pos(pos)
            .map(|pos| (pos.x + pos.y * self.size.x) as _)
    }
}

Just like normalize_pos, it'll return None for positions that do not exist on the map (above or below it).

For get, let's take a simpler approach and not return an Option<Tile>, but a Tile instead - we'll just pretend every tile outside the map is is open:

Rust code

impl Map {
    fn get(&self, pos: Vec2) -> Tile {
        self.index(pos).map(|i| self.tiles[i]).unwrap_or_default()
    }
}

As for set, we'll assume every tile outside the map is immutable:

Rust code

impl Map {
    fn set(&mut self, pos: Vec2, tile: Tile) {
        if let Some(index) = self.index(pos) {
            self.tiles[index] = tile
        }
    }
}

Okay, that's... quite a bit of code, what was the question again?

Shh bear, I'm playing with maps! Maps are fun.

Let's build a simple map and check our Debug implementation:

Rust code

fn main() {
    let map = {
        let mut m = Map::new((6, 6).into());
        let points = [(1, 1), (4, 1), (1, 3), (4, 3), (2, 4), (3, 4)];
        for p in (&points).iter().copied() {
            m.set(p.into(), Tile::Tree);
        }
        m
    };
    println!("{:?}", map);
}

Shell session

$ cargo run --quiet
......
.#..#.
......
.#..#.
..##..
......

Awww is that a smiley face? That's adorable!

What can I say: when I'm not busy being a Rust shill, I'm a big softie.

But... what is it you're doing right now.

Having fun! With maps!

Let's try to actually answer the question from part 1.

Although... we could do with a few more tests. In particular, I'd love to test that our normalize_pos method works properly.

Rust code

#[test]
fn test_normalize_pos() {
    let m = Map::new((2, 2).into());
    assert_eq!(m.normalize_pos((0, 0).into()), Some((0, 0).into()));
    assert_eq!(m.normalize_pos((1, 0).into()), Some((1, 0).into()));
    assert_eq!(m.normalize_pos((2, 0).into()), Some((0, 0).into()));
    assert_eq!(m.normalize_pos((-1, 0).into()), Some((1, 0).into()));
    assert_eq!(m.normalize_pos((-2, 0).into()), Some((0, 0).into()));
    assert_eq!(m.normalize_pos((0, -1).into()), None);
    assert_eq!(m.normalize_pos((0, 2).into()), None);
}

Shell session

$ cargo t
   Compiling day3 v0.1.0 (/home/amos/ftl/aoc2020/day3)
    Finished test [unoptimized + debuginfo] target(s) in 0.40s
     Running target/debug/deps/day3-158fe24cc8d106d4

running 2 tests
test test_normalize_pos ... FAILED
test test_tuple ... ok

failures:

---- test_normalize_pos stdout ----
thread 'test_normalize_pos' panicked at 'assertion failed: `(left == right)`
  left: `Some(Vec2 { x: 3, y: 0 })`,
 right: `Some(Vec2 { x: 1, y: 0 })`', src/main.rs:103:5

Ah. It's not.

Modulos can be tricky, especially with negative values. Let's try something else:

Rust code

    /// Wrap the x coordinate so the map extends infinitely to the
    /// left and the right. Returns `None` for coordinates above 0
    /// or below `self.size.y`.
    fn normalize_pos(&self, pos: Vec2) -> Option<Vec2> {
        if pos.y < 0 || pos.y >= self.size.y {
            None
        } else {
            let x = pos.x % self.size.x;
            // wrap around for left side (negative X coordinates)
            let x = if x < 0 { self.size.x + x } else { x };
            Some((x, pos.y).into())
        }
    }

Shell session

$ cargo test --quiet

running 2 tests
..
test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Better! And, just for the road, let's test index as well:

Rust code

#[test]
fn test_index() {
    let m = Map::new((3, 5).into());
    assert_eq!(m.index((0, 0).into()), Some(0));
    assert_eq!(m.index((2, 0).into()), Some(2));
    assert_eq!(m.index((0, 1).into()), Some(3));
    assert_eq!(m.index((2, 1).into()), Some(5));
}

Shell session

$ cargo test --quiet

running 3 tests
...
test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Good!

Is it one of these where you build a tower of abstractions and then the solution to the problem is nice and short?

One can only hope so! I can't actually tell what's beyond Part 1 before we solve it so... let's see if it pays off.

So, for the question, we first need to determine our itinerary, and then count the number of trees we encounter.

Wait, don't we need to parse the map first?

Oh right! The map.

Let's put our input in input.txt, as usual, and this time we'll use include_bytes, so we get a nice &'static [u8].

Next up, we'll want to actually parse the map. Again, there's probably a bunch of ways to do this, but here's one that seems like it should be fast:

Rust code

    fn parse(input: &[u8]) -> Self {
        let mut columns = 0;
        let mut rows = 1;
        for &c in input.iter() {
            if c == b'\n' {
                rows += 1;
                columns = 0;
            } else {
                columns += 1;
            }
        }

        let mut iter = input.iter().copied();
        let mut map = Self::new((columns, rows).into());
        for row in 0..map.size.y {
            for col in 0..map.size.x {
                let tile = match iter.next() {
                    Some(b'.') => Tile::Open,
                    Some(b'#') => Tile::Tree,
                    c => panic!("Expected '.' or '#', but got: {:?}", c),
                };
                map.set((col, row).into(), tile);
            }
            iter.next();
        }
        map
    }

What? No fancy error handling today?

Nope! Not today.

Let's take it for a spin:

Rust code

fn main() {
    let map = Map::parse(include_bytes!("input.txt"));
    dbg!(map.size);
    println!("{:?}", map);
}

Looks close enough!

Ah, visual testing. Very rigorous. Much correct.

Will you let me have fun?

Now to answer the actual question:

Rust code

fn main() {
    let map = Map::parse(include_bytes!("input.txt"));
    let itinerary = (0..map.size.y).into_iter().map(|y| Vec2::from((y * 3, y)));
    let num_trees = itinerary.filter(|&pos| map.get(pos) == Tile::Tree).count();
    println!("We encountered {} trees", num_trees);
}

Shell session

$ cargo run --quiet
We encountered 148 trees

Ding ding ding, we have a winner!

Moving on.

Part 2

The second part of the problem is really more of the same, except we have different moving patterns:

Right 1, down 1.
Right 3, down 1. (the pattern we already checked.)
Right 5, down 1.
Right 7, down 1.
Right 1, down 2.

For each of these patterns, we encounter a different number of trees - we're supposed to find them all, then multiply them together.

Oooh, ooh! Can we make a function to generate a list of positions given a pattern?

Sure! What would be the type of such a function?

Well, it could take a Vec2... and return a Vec<Vec2>?

Didn't you forget something? When do we know where to stop?

Oh right! I guess it could also take a Map so we know how tall it is.

Take ownership of a Map? Or just borrow it by taking a &Map?

Mhhhhh just borrow it?

Bingo.

Rust code

fn generate_itinerary(map: &Map, delta: Vec2) -> Vec<Vec2> {
    let mut pos = Vec2::from((0, 0));
    let mut res: Vec<_> = Default::default();

    while map.normalize_pos(pos).is_some() {
        res.push(pos);
        pos.x += delta.x;
        pos.y += delta.y;
    }
    res
}

Mhh, could we implement += on Vec2?

Sure, why not.

Rust code

use std::ops::AddAssign;

impl AddAssign for Vec2 {
    fn add_assign(&mut self, rhs: Self) {
        self.x += rhs.x;
        self.y += rhs.y;
    }
}

And then:

Rust code

fn generate_itinerary(map: &Map, delta: Vec2) -> Vec<Vec2> {
    let mut pos = Vec2::from((0, 0));
    let mut res: Vec<_> = Default::default();

    while map.normalize_pos(pos).is_some() {
        res.push(pos);
        pos += delta;
    }
    res
}

We better test that function, too:

Rust code

#[test]
fn test_generate_itinerary() {
    assert_eq!(
        &generate_itinerary(&Map::new((5, 5).into()), (1, 1).into()),
        &[
            (0, 0).into(),
            (1, 1).into(),
            (2, 2).into(),
            (3, 3).into(),
            (4, 4).into(),
        ],
        "right 1 down 1, 5x5 map"
    );

    assert_eq!(
        &generate_itinerary(&Map::new((5, 5).into()), (3, 1).into()),
        &[
            (0, 0).into(),
            (3, 1).into(),
            (6, 2).into(),
            (9, 3).into(),
            (12, 4).into(),
        ],
        "right 3 down 1, 5x5 map"
    );

    assert_eq!(
        &generate_itinerary(&Map::new((5, 5).into()), (2, 2).into()),
        &[(0, 0).into(), (2, 2).into(), (4, 4).into(),],
        "right 2 down 2, 5x5 map"
    );
    assert_eq!(
        &generate_itinerary(&Map::new((9, 9).into()), (2, 5).into()),
        &[(0, 0).into(), (2, 5).into(),],
        "right 2 down 5, 9x9 map"
    )
}

Shell session

$ cargo test --quiet

running 4 tests
....
test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Cool!

Now, let's actually answer the question:

Rust code

fn main() {
    let map = Map::parse(include_bytes!("input.txt"));

    // from the problem statement
    let deltas: &[Vec2] = &[
        (1, 1).into(),
        (3, 1).into(),
        (5, 1).into(),
        (7, 1).into(),
        (1, 2).into(),
    ];
    let answer = deltas
        .iter()
        .copied()
        // generate all itineraries
        .map(|delta| generate_itinerary(&map, delta))
        // count trees
        .map(|itin| {
            itin.into_iter()
                .filter(|&pos| map.get(pos) == Tile::Tree)
                .count()
        })
        // multiply everything together
        .product::<usize>();

    println!("The answer is {}", answer);
}

Shell session

$ cargo run --quiet
The answer is 727923200

Correct again!

That's all for today! Until next time, take care.

You're reading the Advent of Code 2020 series.

Thanks to my sponsors: Ives van Hoorne, Ryan, Yves, Kristoffer Winther Balling, SeniorMars, Daniel Wagner-Hall, Diego Roig, anichno, Chris Thackrey, Paul Marques Mota, Leo Shimonaka, jatescher, Michael, clement, Braidon Whatley, Luke Yue, playest, henrique-pinto, Beth Rennie, Jelle Besseling and 227 more

Comment on /r/fasterthanlime

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

Donate on GitHub Donate on Patreon

Here's another article just for you:

Futures Nostalgia

Apr 03, 2022

1 hour 4 min #rust · #async · #futures · #tower · #hyper

Up until recently, hyper was my favorite Rust HTTP framework. It's low-level, but that gives you a lot of control over what happens.

Here's what a sample hyper application would look like:

Shell session

$ cargo new nostalgia
     Created binary (application) `nostalgia` package

Shell session

$ cd nostalgia
$ cargo add hyper@0.14 --features "http1 tcp server"
    Updating 'https://github.com/rust-lang/crates.io-index' index
      Adding hyper v0.14 to dependencies with features: ["http1", "tcp", "server"]
$ cargo add tokio@1 --features "full"
    Updating 'https://github.com/rust-lang/crates.io-index' index
      Adding tokio v1 to dependencies with features: ["full"]

Part 2

Day 3 (Advent of Code 2020)

Part 2

Contents