# Day 3 (Advent of Code 2020)

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

- Part 2

### Contents

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!

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

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

For convenience, we'll allow building a `Vec2`

from a tuple:

implFrom<(i64,i64)>forVec2{fnfrom((x,y):(i64,i64))->Self{Self{x,y}}}

Let's even write a test for that:

#[test]fntest_tuple(){letv: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:

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

By default, all tiles are open:

implDefaultforTile{fndefault()->Self{Self::Open}}

We'll also add a `Debug`

implementation that writes out a graphical
representation of the tile:

usestd::fmt;implfmt::DebugforTile{fnfmt(&self,f:&mutfmt::Formatter<'_>)-> fmt::Result{letc =matchself{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:

structMap{size:Vec2,tiles:Vec<Tile>,}

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

implMap{fnnew(size:Vec2)->Self{todo!()}fnset(&mutself,pos:Vec2,tile:Tile){todo!()}fnget(&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:

implMap{fnnew(size:Vec2)->Self{letnum_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:

implfmt::DebugforMap{fnfmt(&self,f:&mutfmt::Formatter<'_>)-> fmt::Result{forrowin0..self.size.y{forcolin0..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:

implMap{fnnormalize_pos(&self,pos:Vec2)->Option<Vec2>{ifpos.y<0|| pos.y>=self.size.y{None}else{letx =ifpos.x<0{// wrap around for positions to the left of 0self.size.x-(pos.x%self.size.x)}else{// wrap around for positions to the right of self.size.xpos.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:

implMap{fnindex(&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:

implMap{fnget(&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:

implMap{fnset(&mutself,pos:Vec2,tile:Tile){ifletSome(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:

fnmain(){letmap ={letmutm =Map::new((6,6).into());letpoints =[(1,1),(4,1),(1,3),(4,3),(2,4),(3,4)];forpin(&points).iter().copied(){m.set(p.into(),Tile::Tree);}m};println!("{:?}", map);}

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

#[test]fntest_normalize_pos(){letm =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);}

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

/// 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`.fnnormalize_pos(&self,pos:Vec2)->Option<Vec2>{ifpos.y<0|| pos.y>=self.size.y{None}else{letx = pos.x%self.size.x;// wrap around for left side (negative X coordinates)letx =ifx <0{self.size.x+ x}else{x};Some((x,pos.y).into())}}

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

#[test]fntest_index(){letm =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));}

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

fnparse(input:&[u8])->Self{letmutcolumns =0;letmutrows =1;for&cininput.iter(){ifc ==b'\n'{rows +=1;columns =0;}else{columns +=1;}}letmutiter = input.iter().copied();letmutmap =Self::new((columns,rows).into());forrowin0..map.size.y{forcolin0..map.size.x{lettile =matchiter.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:

fnmain(){letmap =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:

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

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

fngenerate_itinerary(map:&Map,delta:Vec2)->Vec<Vec2>{letmutpos =Vec2::from((0,0));letmutres:Vec<_>=Default::default();whilemap.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.

usestd::ops::AddAssign;implAddAssignforVec2{fnadd_assign(&mutself,rhs:Self){self.x+= rhs.x;self.y+= rhs.y;}}

And then:

fngenerate_itinerary(map:&Map,delta:Vec2)->Vec<Vec2>{letmutpos =Vec2::from((0,0));letmutres:Vec<_>=Default::default();whilemap.normalize_pos(pos).is_some(){res.push(pos);pos += delta;}res}

We better test that function, too:

#[test]fntest_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")}

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

fnmain(){letmap =Map::parse(include_bytes!("input.txt"));// from the problem statementletdeltas:&[Vec2]=&[(1,1).into(),(3,1).into(),(5,1).into(),(7,1).into(),(1,2).into(),];letanswer = 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);}

$ cargo run --quiet The answer is 727923200

Correct again!

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

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

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

## Latest video View all

I ported some Advent of Code solutions from C/C++ to Rust, and used the opportunity to compare performance. When I couldn't explain why they performed differently, I had no choice but to disassemble both and look at what the codegen was like!