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: Christian Oudard, Ronen Cohen, Matt Welke, Ivan Towlson, Nathan Lincoln, Daniel Wagner-Hall, Felix Weis, Henrik Sylvester Pedersen, Thor Kamphefner, VALENTIN MARIETTE, Kamran Khan, Cole Kurkowski, Arjen Laarhoven, Jeremy Kaplan, Jon Reynolds, Vicente Bosch, Chirag Jain, Ville Mattila, Marie Janssen, Vladyslav Batyrenko, Cameron Clausen, Pierre Guillaume Herveou, Agam Brahma, spike grobstein, Daniel Franklin, Jon Gjengset, Tex, Nick Thomas, Blaž Tomažič, Johan, Paul Marques Mota, Jakub Fijałkowski, Mitchell Hamilton, Ruben Duque, Brad Luyster, Max von Forell, Jake S, Justin, Dimitri Merejkowsky, Chris Biscardi, mrcowsy, René Ribaud, Alex Doroshenko, Julian, Vincent, Steven McGuire, Jack DeNeut, Chad Birch, Martin-Louis Bright, Chris Emery, Bob Ippolito, Jomer, John Van Enk, metabaron, Isak Sunde Singh, DaVince, Philipp Gniewosz, Richard Hill, Simon Rüegg, Roman Levin, V, Max Fermor, Mads Johansen, lukvol, Ives van Hoorne, Greg Stoll, Jan De Landtsheer, Scott Munro, Михаил Захаркин, Daniel Strittmatter, Evgeniy Dubovskoy, Sandro, Alex Rudy, Jake Rodkin, Shane Lillie, Romet Tagobert, Geekingfrog, Douglas Creager, Corey Alexander, Molly Howell, Jeff Crocker, knutwalker, Zachary Dremann, Olivier Peyrusse, Sebastian Ziebell, Julien Roncaglia, eigentourist, Amber Kowalski, Charlton Eivind Rodda, Jan Schiefer, Edil Kratskih, Chris Emerson, Matthew Campbell, Krasimir Slavkov, Juniper Wilde, Paul Kline, Pascal Hartig, Samir Talwar, TD, Kristoffer Ström, Henning Schmick, Ryan Levick, Antoine Boegli, Astrid Bek, Ryan, Yoh Deadfall, Justin Ossevoort, Jeremy, Tomáš Duda, playest, Meghana Gupta, Sebastian Dröge, Adam, Nick Gerace, Jeremy Banks, Rasmus Larsen, exelotl, Ramnivas Laddad, Yury Mikhaylov, Torben Clasen, Sam Rose, Nickolas Fotopoulos, C J Silverio, Walther, Pete Bevin, Shane Sveller, Marcel Jackwerth, Brian Dawn, Clara Schultz, Robert Cobb, jer, Wonwoo Choi, Hawken Rives, João Veiga, Dave Gauer, David Cornu, Richard Pringle, Adam Perry, Yann Schwartz, Jaseem Abid, Zinahe Asnake, Ryan Blecher, Benjamin Röjder Delnavaz, Grégoire Hubert, Matt Jadczak, Nazar Mokrynskyi, Julian Hofer, Mara Bos, Brandon, Jonathan Knapp, Maximilian, Seth Stadick, brianloveswords, Sean Bryant, Ember, Sebastian Zimmer, Makoto Nakashima, Geert Depuydt, Geoff Cant, Geoffroy Couprie, Michael Alyn Miller, Vengarioth, o0Ignition0o, Zaki, Raphael Gaschignard, Romain Ruetschi, Ignacio Vergara, Pascal, Cassie Jones, Pat Monaghan, Jane Lusby, Nicolas Goy, Suhib Sam Kiswani, Henry Goffin, Ted Mielczarek, Random832, Ryszard Sommefeldt, Jesús Higueras, 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?