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    // The first column is reserved for newlines, so shift each point one to the right.
67    let mut grid = Grid::new(width + 1, height, '.');
68
69    for &Point { x, y } in &input.points {
70        grid[Point::new(reflect(x, width), reflect(y, height)) + RIGHT] = '#';
71    }
72
73    (0..height).for_each(|y| grid[Point::new(0, y)] = '\n');
74    grid.bytes.iter().collect()
75}
76
77fn apply_fold(fold: Fold, point: Point) -> Point {
78    match fold {
79        Fold::Horizontal(x) if point.x >= x => Point::new(2 * x - point.x, point.y),
80        Fold::Vertical(y) if point.y >= y => Point::new(point.x, 2 * y - point.y),
81        _ => point,
82    }
83}
84
85/// All larger folds repeat a periodic mapping pattern given by the final fold, so a single
86/// modulo followed by a reflection back into range replaces every intermediate fold.
87fn reflect(value: i32, max: i32) -> i32 {
88    let period = 2 * (max + 1);
89    let value = value % period;
90    if value > max { period - value - 2 } else { value }
91}
aoc/year2021/day13.rs

aoc/year2021/
day13.rs
