aoc/year2021/
day13.rs

1//! # Transparent Origami
2//!
3//! There are 2 possible approaches to tracking the position of dots after each fold:
4//! * A `HashSet` that will collapse duplicate entries
5//! * An array of sufficient dimensions to track every possible coordinate.
6//!
7//! We will use both approaches for speed, the first in part one and the second in part two.
8//!
9//! For part two we can determine the final size of the paper by taking the *last* x and y
10//! coordinates from the fold instructions. It's then faster and more convenient to process
11//! each point completely and update the final location, than to step through intermediate folds.
12use crate::util::grid::*;
13use crate::util::hash::*;
14use crate::util::iter::*;
15use crate::util::parse::*;
16use crate::util::point::*;
17
18#[derive(Clone, Copy)]
19pub enum Fold {
20    Horizontal(i32),
21    Vertical(i32),
22}
23
24pub struct Input {
25    points: Vec<Point>,
26    folds: Vec<Fold>,
27}
28
29/// Parse the input into collections of [`Point`] and [`Fold`] structs.
30pub fn parse(input: &str) -> Input {
31    let (prefix, suffix) = input.split_once("\n\n").unwrap();
32
33    let points: Vec<_> = prefix.iter_signed().chunk::<2>().map(|[x, y]| Point::new(x, y)).collect();
34
35    let folds: Vec<_> = suffix
36        .lines()
37        .map(|line| match line.split_once('=').unwrap() {
38            ("fold along x", x) => Fold::Horizontal(x.signed()),
39            ("fold along y", y) => Fold::Vertical(y.signed()),
40            _ => unreachable!(),
41        })
42        .collect();
43
44    Input { points, folds }
45}
46
47/// Fold once then count dots. The sample data folds along `y` and my input folded along `x`,
48/// testing both possibilities.
49pub fn part1(input: &Input) -> usize {
50    let fold = input.folds[0];
51    input.points.iter().map(|&p| apply_fold(fold, p)).collect::<FastSet<_>>().len()
52}
53
54/// Decode secret message.
55///
56/// The output is a multi-line string to allow integration testing. The final dimensions of the
57/// paper are found from the last `x` and `y` fold coordinates.
58pub fn part2(input: &Input) -> String {
59    let (width, height) = input.folds.iter().fold((0, 0), |(width, height), &fold| match fold {
60        Fold::Horizontal(x) => (x, height),
61        Fold::Vertical(y) => (width, y),
62    });
63
64    let mut grid = Grid::new(width + 1, height, '.');
65
66    for &start in &input.points {
67        let end = input.folds.iter().fold(start, |point, &fold| apply_fold(fold, point));
68        grid[end + RIGHT] = '#';
69    }
70
71    (0..height).for_each(|y| grid[Point::new(0, y)] = '\n');
72    grid.bytes.iter().collect()
73}
74
75#[inline]
76fn apply_fold(fold: Fold, point: Point) -> Point {
77    match fold {
78        Fold::Horizontal(x) if point.x >= x => Point::new(2 * x - point.x, point.y),
79        Fold::Vertical(y) if point.y >= y => Point::new(point.x, 2 * y - point.y),
80        _ => point,
81    }
82}
aoc/year2021/day13.rs

aoc/year2021/
day13.rs
