Previous: Advent of Code 2020 – Day 2: validating passwords
I decided to take a shot at Advent of Code 2020 to exercise my Rust knowledge. Here’s the task for Day 3:
Day 3: Password Philosophy
(…)
Due to the local geology, trees in this area only grow on exact
integer coordinates in a grid. You make a map (your puzzle input) of
the open squares (.
) and trees (#
) you can see. For example:
..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#
These aren’t the only trees, though; due to something you read about
once involving arboreal genetics and biome stability, the same pattern
repeats to the right many times:
..##.........##.........##.........##.........##.........##....... --->
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##..... --->
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.# --->
You start on the open square (.
) in the top-left corner and need to
reach the bottom (below the bottom-most row on your map).
The toboggan can only follow a few specific slopes (you opted for a
cheaper model that prefers rational numbers); start by counting all
the trees you would encounter for the slope right 3, down 1:
From your starting position at the top-left, check the position that
is right 3 and down 1. Then, check the position that is right 3 and
down 1 from there, and so on until you go past the bottom of the map.
The locations you’d check in the above example are marked here with
O
where there was an open square and X
where there was a tree:
..##.........##.........##.........##.........##.........##....... --->
#..O#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....X..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#O#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..X...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.X#.......#.##.......#.##.......#.##.......#.##..... --->
.#.#.#....#.#.#.#.O..#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........X.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.X#...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...#X....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...X.#.#..#...#.#.#..#...#.#.#..#...#.# --->
In this example, traversing the map using this slope would cause you
to encounter 7
trees.
Starting at the top-left corner of your map and following a slope of
right 3 and down 1, how many trees would you encounter?
(…)
Part Two
Time to check the rest of the slopes – you need to minimize the
probability of a sudden arboreal stop, after all.
Determine the number of trees you would encounter if, for each of the
following slopes, you start at the top-left corner and traverse the
map all the way to the bottom:
- Right 1, down 1.
- Right 3, down 1. (This is the slope you already checked.)
- Right 5, down 1.
- Right 7, down 1.
- Right 1, down 2.
In the above example, these slopes would find 2
, 7
, 3
, 4
, and
2
tree(s) respectively; multiplied together, these produce the
answer 336
.
What do you get if you multiply together the number of trees
encountered on each of the listed slopes?
The full story can be found on the website.
src/day_3.rs
use {
anyhow::{anyhow, bail, ensure, Result},
itertools::Itertools,
ndarray::prelude::*,
std::io::{self, prelude::*},
};
pub const PATH: &str = "./data/day_3/input";
#(derive(Clone, Copy, Debug, Eq, Hash, PartialEq))
pub enum Pixel {
Empty,
Tree,
}
impl Pixel {
pub fn from_char(c: char) -> Result<Self> {
match c {
'.' => Ok(Self::Empty),
'#' => Ok(Self::Tree),
_ => bail!("invalid pixel"),
}
}
}
#(derive(Clone, Debug, Eq, Hash, PartialEq))
pub struct Terrain {
pixels: Array2<Pixel>,
}
impl Terrain {
pub fn parse_from<R: BufRead>(reader: R) -> Result<Self> {
TerrainParser::parse(reader.lines())
}
pub fn slope_count(&self, delta_x: usize, delta_y: usize) -> usize {
assert!(delta_y != 0, "delta_y is zero");
let pixels = &self.pixels;
(0..pixels.nrows())
.step_by(delta_y)
.zip((0..).step_by(delta_x).map(|x| x % pixels.ncols()))
.filter(|pos| pixels(*pos) == Pixel::Tree)
.count()
}
}
#(derive(Debug))
struct TerrainParser {
pixels: Vec<Pixel>,
width: usize,
height: usize,
}
impl TerrainParser {
fn parse<R: BufRead>(mut lines: io::Lines<R>) -> Result<Terrain> {
let first_line =
lines.next().ok_or_else(|| anyhow!("empty terrain"))??;
let mut parser = Self::parse_first_line(&first_line)?;
for line in lines {
parser = parser.parse_line(&line?)?;
}
let TerrainParser {
pixels,
width,
height,
} = parser;
Ok(Terrain {
pixels: Array2::from_shape_vec((height, width), pixels)?,
})
}
fn parse_first_line(line: &str) -> Result<Self> {
let pixels: Vec<_> =
line.chars().map(Pixel::from_char).try_collect()?;
let width = pixels.len();
ensure!(width != 0, "zero-width terrain");
Ok(Self {
pixels,
width,
height: 1,
})
}
fn parse_line(mut self, line: &str) -> Result<Self> {
let expected_len = self.pixels.len() + self.width;
self.pixels.reserve_exact(self.width);
itertools::process_results(
line.chars().map(Pixel::from_char),
|pixels| self.pixels.extend(pixels),
)?;
ensure!(self.pixels.len() == expected_len, "jagged terrain");
self.height += 1;
Ok(self)
}
}
#(cfg(test))
mod tests {
use {super::*, std::io::BufReader};
#(test)
fn pixel_from_char() {
assert_eq!(Pixel::from_char('.').unwrap(), Pixel::Empty);
assert_eq!(Pixel::from_char('#').unwrap(), Pixel::Tree);
assert!(Pixel::from_char(' ').is_err());
}
#(test)
fn terrain_parse_from() -> anyhow::Result<()> {
fn parse(input: &str) -> Result<Terrain> {
Terrain::parse_from(BufReader::new(input.as_bytes()))
}
let expected = Array2::from_shape_vec(
(3, 3),
(Pixel::Empty, Pixel::Tree)
.iter()
.copied()
.cycle()
.take(9)
.collect(),
)?;
assert_eq!(parse(".#.n#.#n.#.n")?.pixels, expected);
assert!(parse("").is_err());
assert!(parse(". #").is_err());
assert!(parse(".n##").is_err());
Ok(())
}
#(test)
fn terrain_slope_count() -> anyhow::Result<()> {
// .#.
// #.#
// .#.
// #.#
let pixels = Array2::from_shape_vec(
(4, 3),
(Pixel::Empty, Pixel::Tree)
.iter()
.copied()
.cycle()
.take(12)
.collect(),
)?;
let terrain = Terrain { pixels };
assert_eq!(terrain.slope_count(1, 1), 1);
assert_eq!(terrain.slope_count(2, 1), 3);
assert_eq!(terrain.slope_count(3, 1), 2);
assert_eq!(terrain.slope_count(1, 2), 1);
Ok(())
}
}
src/bin/day_3_1.rs
use {
anyhow::Result,
aoc_2020::day_3::{self as lib, Terrain},
std::{fs::File, io::BufReader},
};
fn main() -> Result<()> {
let file = BufReader::new(File::open(lib::PATH)?);
let count = Terrain::parse_from(file)?.slope_count(3, 1);
println!("{}", count);
Ok(())
}
src/bin/day_3_2.rs
use {
anyhow::Result,
aoc_2020::day_3::{self as lib, Terrain},
std::{fs::File, io::BufReader},
};
const SLOPES: &((usize; 2)) = &((1, 1), (3, 1), (5, 1), (7, 1), (1, 2));
fn main() -> Result<()> {
let file = BufReader::new(File::open(lib::PATH)?);
let terrain = Terrain::parse_from(file)?;
let product: usize = SLOPES
.iter()
.map(|&(delta_x, delta_y)| terrain.slope_count(delta_x, delta_y))
.product();
println!("{}", product);
Ok(())
}
Crates used: anyhow
1.0.37 itertools
0.10.0 ndarray
0.14.0
cargo fmt
and cargo clippy
have been applied.