Day 3 (Advent of Code 2020)

This article is part of the Advent of Code 2020 series.

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:

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.

This article was made possible thanks to my patrons: Steven McGuire, Chad Birch, Chris Emery, Bob Ippolito, John Van Enk, metabaron, Isak Sunde Singh, Ali Yazdani, Philipp Gniewosz, Mads Johansen, lukvol, Ives van Hoorne, Jan De Landtsheer, Daniel Strittmatter, Evgeniy Dubovskoy, Alex Rudy, Romet Tagobert, Douglas Creager, Gus W, Corey Alexander, Molly Howell, knutwalker, Zachary Dremann, Sebastian Ziebell, Julien Roncaglia, Amber Kowalski, T, Juniper Wilde, Paul Kline, Kristoffer Ström, Astrid Bek, Yoh Deadfall, Justin Ossevoort, taziden, Harsh Shandilya, Tomáš Duda, Jeremy Banks, Rasmus Larsen, Torben Clasen, Sam Rose, C J Silverio, Walther, Pete Bevin, Shane Sveller, Thomas Schultz, Ivan Dubrov, jer, Wonwoo Choi, João Veiga, Richard Pringle, Adam Perry, Benjamin Röjder Delnavaz, Matt Jadczak, tavr, Mara Bos, Jonathan Knapp, Maximilian, Seth Stadick, brianloveswords, Sean Bryant, Ember, Sebastian Zimmer, Fernando, Makoto Nakashima, Geert Depuydt, Geoff Cant, Geoffroy Couprie, Michael Alyn Miller, o0Ignition0o, Zaki, Raphael Gaschignard, Romain Ruetschi, Ignacio Vergara, Pascal, Jane Lusby, Nicolas Goy, Ted Mielczarek, Someone, Ryszard Sommefeldt, Aurora.

This article is part 3 of the Advent of Code 2020 series.

Read the next part

If you liked this article, please support my work on Patreon!

Become a Patron

Looking for the homepage?
Another article: A new website for 2020