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::hash::*;
13use crate::util::iter::*;
14use crate::util::parse::*;
15use crate::util::point::*;
16
17#[derive(Clone, Copy)]
18pub enum Fold {
19    Horizontal(i32),
20    Vertical(i32),
21}
22
23pub struct Input {
24    points: Vec<Point>,
25    folds: Vec<Fold>,
26}
27
28/// Parse the input into collections of [`Point`] and [`Fold`] structs.
29pub fn parse(input: &str) -> Input {
30    let (prefix, suffix) = input.split_once("\n\n").unwrap();
31
32    let points: Vec<_> = prefix.iter_signed().chunk::<2>().map(|[x, y]| Point::new(x, y)).collect();
33
34    let folds: Vec<_> = suffix
35        .lines()
36        .map(|line| match line.split_once('=').unwrap() {
37            ("fold along x", x) => Fold::Horizontal(x.signed()),
38            ("fold along y", y) => Fold::Vertical(y.signed()),
39            _ => unreachable!(),
40        })
41        .collect();
42
43    Input { points, folds }
44}
45
46/// Fold once then count dots. The sample data folds along `y` and my input folded along `x`
47/// testing both possibilities.
48pub fn part1(input: &Input) -> usize {
49    match input.folds[0] {
50        Fold::Horizontal(x) => {
51            input.points.iter().map(|&p| fold_horizontal(x, p)).collect::<FastSet<_>>().len()
52        }
53        Fold::Vertical(y) => {
54            input.points.iter().map(|&p| fold_vertical(y, p)).collect::<FastSet<_>>().len()
55        }
56    }
57}
58
59/// Decode secret message.
60///
61/// The output is a multi-line string to allow integration testing. The final dimensions of the
62/// paper are found from the last `x` and `y` fold coordinates.
63pub fn part2(input: &Input) -> String {
64    let mut width = 0;
65    let mut height = 0;
66
67    for &fold in &input.folds {
68        match fold {
69            Fold::Horizontal(x) => width = x,
70            Fold::Vertical(y) => height = y,
71        }
72    }
73
74    let mut grid = vec![false; (width * height) as usize];
75
76    for point in &input.points {
77        let mut point = *point;
78
79        for &fold in &input.folds {
80            point = match fold {
81                Fold::Horizontal(x) => fold_horizontal(x, point),
82                Fold::Vertical(y) => fold_vertical(y, point),
83            }
84        }
85
86        grid[(point.y * width + point.x) as usize] = true;
87    }
88
89    let mut code = String::new();
90    for y in 0..height {
91        code.push('\n');
92        for x in 0..width {
93            let c = if grid[(y * width + x) as usize] { '#' } else { '.' };
94            code.push(c);
95        }
96    }
97    code
98}
99
100/// Fold point at `x` coordinate, doing nothing if the point is to the left of the fold line.
101#[inline]
102fn fold_horizontal(x: i32, p: Point) -> Point {
103    if p.x < x { p } else { Point::new(2 * x - p.x, p.y) }
104}
105
106/// Fold point at `y` coordinate, doing nothing if the point is above the fold line.
107#[inline]
108fn fold_vertical(y: i32, p: Point) -> Point {
109    if p.y < y { p } else { Point::new(p.x, 2 * y - p.y) }
110}
aoc/year2021/day13.rs

aoc/year2021/
day13.rs
