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. Because each fold cuts the remaining paper in
11//! half, the layout of points that map to the same condensed positions is periodic. It's faster
12//! and more convenient to process each point completely using modular math to go straight to
13//! the condensed position without worrying about any intermediate folds.
14use crate::util::grid::*;
15use crate::util::hash::*;
16use crate::util::iter::*;
17use crate::util::parse::*;
18use crate::util::point::*;
19
20#[derive(Clone, Copy)]
21pub enum Fold {
22    Horizontal(i32),
23    Vertical(i32),
24}
25
26pub struct Input {
27    points: Vec<Point>,
28    folds: Vec<Fold>,
29}
30
31/// Parse the input into collections of [`Point`] and [`Fold`] structs.
32pub fn parse(input: &str) -> Input {
33    let (prefix, suffix) = input.split_once("\n\n").unwrap();
34
35    let points: Vec<_> = prefix.iter_signed().chunk::<2>().map(|[x, y]| Point::new(x, y)).collect();
36
37    let folds: Vec<_> = suffix
38        .lines()
39        .map(|line| match line.split_once('=').unwrap() {
40            ("fold along x", x) => Fold::Horizontal(x.signed()),
41            ("fold along y", y) => Fold::Vertical(y.signed()),
42            _ => unreachable!(),
43        })
44        .collect();
45
46    Input { points, folds }
47}
48
49/// Fold once then count dots. The sample data folds along `y` and my input folded along `x`,
50/// testing both possibilities.
51pub fn part1(input: &Input) -> usize {
52    let fold = input.folds[0];
53    input.points.iter().map(|&p| apply_fold(fold, p)).collect::<FastSet<_>>().len()
54}
55
56/// Decode secret message.
57///
58/// The output is a multi-line string to allow integration testing. The final dimensions of the
59/// paper are found from the last `x` and `y` fold coordinates.
60pub fn part2(input: &Input) -> String {
61    let (width, height) = input.folds.iter().fold((0, 0), |(width, height), &fold| match fold {
62        Fold::Horizontal(x) => (x, height),
63        Fold::Vertical(y) => (width, y),
64    });
65
66    // All larger folds repeat a periodic mapping pattern given by the final fold.
67    let mut grid = Grid::new(width + 1, height, '.');
68    let period_x = 2 * (width + 1);
69    let period_y = 2 * (height + 1);
70
71    for &start in &input.points {
72        let x = start.x % period_x;
73        let x = if x > width { period_x - x - 2 } else { x };
74        let y = start.y % period_y;
75        let y = if y > height { period_y - y - 2 } else { y };
76        let end = Point::new(x, y);
77        grid[end + RIGHT] = '#';
78    }
79
80    (0..height).for_each(|y| grid[Point::new(0, y)] = '\n');
81    grid.bytes.iter().collect()
82}
83
84#[inline]
85fn apply_fold(fold: Fold, point: Point) -> Point {
86    match fold {
87        Fold::Horizontal(x) if point.x >= x => Point::new(2 * x - point.x, point.y),
88        Fold::Vertical(y) if point.y >= y => Point::new(point.x, 2 * y - point.y),
89        _ => point,
90    }
91}
aoc/year2021/day13.rs

aoc/year2021/
day13.rs
