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 1 and the second in part 2.
8//!
9//! For part 2 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    match input.folds[0] {
51        Fold::Horizontal(x) => {
52            input.points.iter().map(|&p| fold_horizontal(x, p)).collect::<FastSet<_>>().len()
53        }
54        Fold::Vertical(y) => {
55            input.points.iter().map(|&p| fold_vertical(y, p)).collect::<FastSet<_>>().len()
56        }
57    }
58}
59
60/// Decode secret message.
61///
62/// The output is a multi-line string to allow integration testing. The final dimensions of the
63/// paper are found from the last `x` and `y` fold coordinates.
64pub fn part2(input: &Input) -> String {
65    let (width, height) = input.folds.iter().fold((0, 0), |(width, height), &fold| match fold {
66        Fold::Horizontal(x) => (x, height),
67        Fold::Vertical(y) => (width, y),
68    });
69
70    let mut grid = Grid::new(width + 1, height, '.');
71
72    for &start in &input.points {
73        let end = input.folds.iter().fold(start, |point, &fold| match fold {
74            Fold::Horizontal(x) => fold_horizontal(x, point),
75            Fold::Vertical(y) => fold_vertical(y, point),
76        });
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/// Fold point at `x` coordinate, doing nothing if the point is to the left of the fold line.
85#[inline]
86fn fold_horizontal(x: i32, p: Point) -> Point {
87    if p.x < x { p } else { Point::new(2 * x - p.x, p.y) }
88}
89
90/// Fold point at `y` coordinate, doing nothing if the point is above the fold line.
91#[inline]
92fn fold_vertical(y: i32, p: Point) -> Point {
93    if p.y < y { p } else { Point::new(p.x, 2 * y - p.y) }
94}
aoc/year2021/day13.rs

aoc/year2021/
day13.rs
