Thanks to my sponsors: Valentin Mariette, David White, Ben Mitchell, Daniel Silverstone, Henrik Tudborg, Alejandro Angulo, Christian Bourjau, Michal Hošna, Steven Pham, Paul Schuberth, James Brown, Corey Alexander, Nicolas Riebesel, Shane Lillie, Matt Heise, René Ribaud, Matěj Volf, Andronik, Horváth-Lázár Péter, qrpth and 230 more
9 min
Day 3 (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!
$ 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)]
struct Vec2 {
x: i64,
y: i64,
}
For convenience, we'll allow building a Vec2 from a tuple:
impl From<(i64, i64)> for Vec2 {
fn from((x, y): (i64, i64)) -> Self {
Self { x, y }
}
}
Let's even write a test for that:
#[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:
#[derive(Clone, Copy, PartialEq)]
enum Tile {
Open,
Tree,
}
By default, all tiles are open:
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:
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:
struct Map {
size: Vec2,
tiles: Vec<Tile>,
}
And from there, we'll need a couple methods:
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:
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:
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:
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:
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:
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:
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:
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);
}
$ 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]
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);
}
$ 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`.
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())
}
}
$ 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]
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));
}
$ 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:
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:
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:
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);
}
$ 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.
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.
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:
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:
#[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"
)
}
$ 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:
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);
}
$ cargo run --quiet
The answer is 727923200
Correct again!
That's all for today! Until next time, take care.
Here's another article just for you:
Surviving Rust async interfaces
28 min
I used to be afraid of async Rust. It's easy to get into trouble!
But thanks to the work done by the whole community, async Rust is getting easier to use every week. One project I think is doing particularly great work in this area is async-std.
Let's say we want to compute the SHA3-256 hash of a file. It's very easy to do with synchronous I/O: