Advent of Code 2021 - Day 13

Problem description

We are given a sheet of transparent paper, with dots printed on it and instructions to fold it up. The objective is to find the password printed on the paper.

The input data is in 2 parts. First, a list of dots coordinates, then a list of fold instructions. There are 2 folding instructions types, as the paper can either be folded up (instructions fold along y=<y0>), or left (instructions fold along x=<x0>).

Data structures

We define a structure with two unsigned integers for dots coordinates, and an enumeration for folding instructions.

#[derive(Copy, Clone, Eq, PartialEq, Hash)]
pub struct Dot {
    x: usize,
    y: usize
}

pub enum Folding {
    X(usize),
    Y(usize)
}

The folding function

The core of our program is the folding function, called fold(). It takes 2 arguments (a set of dots and the folding instruction) and returns the resulting set.

To compute new dots coordinates, the following function is used : Let $z$ the folding coordinate and $z_0$ the folding line position, we have :

This simple mathematical function is implemented as follows :

pub fn fold(dots: &HashSet<Dot>, folding: &Folding) -> HashSet<Dot> {
    let mut folded_dots = HashSet::new();

    for dot in dots {
        match *folding {
            Folding::Y(y) => { 
                if dot.y < y {
                    folded_dots.insert(Dot {x: dot.x, y: dot.y});
                }
                else {
                    folded_dots.insert(Dot {x: dot.x, y: 2 * y - dot.y});
                }
            },
            Folding::X(x) => {
                if dot.x < x {
                    folded_dots.insert(Dot {x: dot.x, y: dot.y});
                }
                else {
                    folded_dots.insert(Dot {x: 2 * x - dot.x, y: dot.y});
                }
            }
        }
    }
    folded_dots
}

Part 1

In the first part of the puzzle, only the first folding operation is applied to the transparent paper.

pub fn solve_part1(input: &Vec<String>) -> usize {
    let (dots, foldings) = parse_instructions(input);

    fold(&dots, &foldings[0]).len()
}

I was close to giving a wrong answer, as I was (wrongfully) convinced that the folding instruction to apply was described in the second-to-last line of the input file (as the test input had two folding instructions). My test passed, but the first answer I got by running the program with the actual input file was incorrect.

Part 2

This part is a bit special. The solve_part2() function does not (at least in the current code version) return an integer or a string, but a vector of strings. That can be seen a a 2-dimensional array of characters.

We compute the final dots set, by applying the instructions one after another, but also the size of

pub fn solve_part2(input: &Vec<String>) -> Vec<String> {
    let (dots, foldings) = parse_instructions(input);
    let mut last_folded = dots.clone();
    let mut xmax = dots.iter().map(|d| d.x).max().unwrap();
    let mut ymax = dots.iter().map(|d| d.y).max().unwrap();

    for f in foldings {
        let folded = fold(&last_folded, &f);
        match f {
            Folding::X(x) => xmax = xmax.min(x),
            Folding::Y(y) => ymax = ymax.min(y)
        }
        last_folded = folded.clone();
    }

    let mut paper = vec![String::new(); ymax];
    for y in 0..ymax {
        for x in 0..xmax {
            let ch = match last_folded.contains(&Dot {x, y}) {
                true => '#',
                false => ' '
            };
            paper[y].push(ch);
        }
    }

    paper
}

With my input data, I got this result :

###..####.#..#.####.#....###...##..#..#.
#..#....#.#.#.....#.#....#..#.#..#.#..#.
#..#...#..##.....#..#....#..#.#....####.
###...#...#.#...#...#....###..#.##.#..#.
#.#..#....#.#..#....#....#....#..#.#..#.
#..#.####.#..#.####.####.#.....###.#..#.

This is obviously not the data entered in the Advent of Code website. The characters must be “decoded” from this image, to extract the password. I performed this operation manually (like 99 % of the contestants I think), and I entered the answer RZKZLPGH.

Future developments

A homemade OCR (optical character recognition) module will certainely be added in a few days, so as to make the solve_part2() return a String (the password entered in the Advent of Code website). I will describe it in another article.