Advent of Code 2023 Day 13

Day 13: Point of Incidence

https://adventofcode.com/2023/day/13

You arrive at Lava Island. There is a distinct lack of lava for an island named “Lava Island”.

The place you arrived at is full of mirrors. It’s hard to see where they are -because of their mirrorness, you see-.

Your input today are several patterns of what you see as you walk.

An example input looks like this:

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

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

# are tiles of ash
. are tiles of rocks

By analyzing the patterns, you can figure out where the mirrors are.

Parsing

An enum to keep track of what a tile holds:

enum Tile {
    Ash,
    Rock,
}

Because that enum has 2 variants, I assume many people chose booleans for this, or even flipping on/off bits in a list of numbers (or even better, one number!).

The input represents a list of 2D grids:

fn parse(input: &str) -> Vec<VecDeque<Vec<Tile>>> {
    input
        .split("\n\n")
        .map(|block| {
            block
                .lines()
                .map(|line| {
                    line.chars()
                        .map(|c| match c {
                            '.' => Tile::Ash,
                            '#' => Tile::Rock,
                            _ => panic!("at the disco"),
                        })
                        .collect()
                })
                .collect()
        })
        .collect()
}

I chose to represent rows as a VecDeque as opposed to a Vec, more on why later.

Non Rustacean friends reading this: basically, it’s a list you can reverse. Chances are you don’t even have to think about this in a language like Python or JavaScript.

Part 1

To find the reflection in each pattern, you need to find a perfect reflection across either a horizontal line between two rows or across a vertical line between two columns.

A reflection line does not have to be perfectly in the middle. If one half of the reflection is larger than the other half (in other words: it has nowhere to reflect onto), those extra lines can be ignored.

In the example, the first pattern has a vertical reflection line between column 5 and 6:

123456789
    ><
#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.
    ><
123456789

Each pattern has a numerical value, to find it:

If the pattern has a vertical reflection:

the number of columns to the left of that line

If the pattern has a horizontal reflection:

the number of rows above that line multiplied by 100

The question asks for the sum of all number values for a pattern.

So, some skeleton code that uses the parsing logic above:

let grid = parse(input);
grid.iter()
    .map(/* get number for each pattern */)
    .sum()

Helpers

I use a helper that returns the offset a 2D grid reflects at horizontally.

A grid is not guaranteed to have a reflection point, so I express that as an Option<usize>. Either it has a reflection line, and I return its offset, or it doesn’t reflect, and I return nothing.

This finds the first offset where a grid is perfectly mirrorred.

First, I divide the grid into 2 halves. Then I check if those two halves are identical, making sure to take into account the length of the smallest half.

This helper is also why I chose a VecDeque earlier, I reverse the first half, so I can easier compare the two halves. A normal Vec wouldn’t let me do that.

fn reflects_at(grid: &VecDeque<Vec<Tile>>) -> Option<usize> {
    (1..grid.len()).find(|&offset| {
        let half1 = grid.iter().take(offset).rev();
        let half2 = grid.iter().skip(offset);
        let mut combined = half1.zip(half2); // the shortest half determines how long this is!
        combined.all(|(row1, row2)| row1 == row2)
    })
}

So, if I pass a regular grid into this, I get the row offset it reflects at. To check which offset it reflects at vertically, I pass a 2D grid of columns into that same function.

Now, for each pattern I can check if it has a vertical mirrorring point. If it doesn’t, I transform the grid of rows into a grid of columns and do the check again.

Code

se std::collections::VecDeque;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Ash,
    Rock,
}

// parse input to a list of 2D grids
fn parse(input: &str) -> Vec<VecDeque<Vec<Tile>>> {
    input
        .split("\n\n")
        .map(|block| {
            block
                .lines()
                .map(|line| {
                    line.chars()
                        .map(|c| match c {
                            '.' => Tile::Ash,
                            '#' => Tile::Rock,
                            _ => panic!("at the disco"),
                        })
                        .collect()
                })
                .collect()
        })
        .collect()
}

fn reflects_at(grid: &VecDeque<Vec<Tile>>) -> Option<usize> {
    (1..grid.len()).find(|&offset| {
        let half1 = grid.iter().take(offset).rev();
        let half2 = grid.iter().skip(offset);
        let mut combined = half1.zip(half2); // the shortest half determines how long this is!
        combined.all(|(row1, row2)| row1 == row2)
    })
}

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    grid.iter()
        .map(|grid| {
            // check horizontal
            if let Some(i) = reflects_at(grid) {
                return i * 100;
            }

            // check vertical
            let cols = (0..grid[0].len())
                .map(|i| grid.iter().map(|row| row[i]).collect())
                .collect();
            if let Some(i) = reflects_at(&cols) {
                return i;
            }

            // no reflection found
            0
        })
        .sum()
}

Part 2

Each mirror has one smudge. Exactly one # or # should be the opposite type.

Helpers

The reflects_at helper changes a bit.

Instead of checking for a perfect mirrorring, I now check for exactly 1 different tile in the two halves.

I count how many differences a potential mirror has, that amount should be exactly 1.

fn reflects_at(grid: &VecDeque<Vec<Tile>>) -> Option<usize> {
    (1..grid.len()).find(|&offset| {
        let half1 = grid.iter().take(offset).rev();
        let half2 = grid.iter().skip(offset);
        let combined = half1.zip(half2); // the shortest half determines how long this is!
        let differences: usize = combined
            .map(|(row1, row2)| row1.iter().zip(row2.iter()).filter(|(a, b)| a != b).count())
            .sum();

        differences == 1
    })
}

Code

use std::collections::VecDeque;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Ash,
    Rock,
}

fn parse(input: &str) -> Vec<VecDeque<Vec<Tile>>> {
    input
        .split("\n\n")
        .map(|block| {
            block
                .lines()
                .map(|line| {
                    line.chars()
                        .map(|c| match c {
                            '.' => Tile::Ash,
                            '#' => Tile::Rock,
                            _ => panic!("at the disco"),
                        })
                        .collect()
                })
                .collect()
        })
        .collect()
}

fn reflects_at(grid: &VecDeque<Vec<Tile>>) -> Option<usize> {
    (1..grid.len()).find(|&offset| {
        let half1 = grid.iter().take(offset).rev();
        let half2 = grid.iter().skip(offset);
        let combined = half1.zip(half2); // the shortest half determines how long this is!
        let differences: usize = combined
            .map(|(row1, row2)| row1.iter().zip(row2.iter()).filter(|(a, b)| a != b).count())
            .sum();

        differences == 1
    })
}

pub fn part_2(input: &str) -> usize {
    let grid = parse(input);
    grid.iter()
        .map(|grid| {
            // check horizontal
            if let Some(i) = reflects_at(grid) {
                return i * 100;
            }

            // check vertical
            let cols = (0..grid[0].len())
                .map(|i| grid.iter().map(|row| row[i]).collect())
                .collect();
            if let Some(i) = reflects_at(&cols) {
                return i;
            }

            // no reflection found
            0
        })
        .sum()
}

The differences between part1 and part2 are minor, so I made that helper function take a variable amount of smudges.

Final code

use std::collections::VecDeque;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Ash,
    Rock,
}

// parse input to a list of 2D grids
fn parse(input: &str) -> Vec<VecDeque<Vec<Tile>>> {
    input
        .split("\n\n")
        .map(|block| {
            block
                .lines()
                .map(|line| {
                    line.chars()
                        .map(|c| match c {
                            '.' => Tile::Ash,
                            '#' => Tile::Rock,
                            _ => panic!("at the disco"),
                        })
                        .collect()
                })
                .collect()
        })
        .collect()
}

fn reflects_at(grid: &VecDeque<Vec<Tile>>, smudges: usize) -> Option<usize> {
    (1..grid.len()).find(|&offset| {
        let half1 = grid.iter().take(offset).rev();
        let half2 = grid.iter().skip(offset);
        let combined = half1.zip(half2); // the shortest half determines how long this is!
        let found_smudges: usize = combined
            .map(|(row1, row2)| row1.iter().zip(row2.iter()).filter(|(a, b)| a != b).count())
            .sum();

        found_smudges == smudges
    })
}

pub fn part_1(input: &str) -> usize {
    let grid = parse(input);
    grid.iter()
        .map(|grid| {
            // check horizontal
            if let Some(i) = reflects_at(grid, 0) {
                return i * 100;
            }

            // check vertical
            let cols = (0..grid[0].len())
                .map(|i| grid.iter().map(|row| row[i]).collect())
                .collect();
            if let Some(i) = reflects_at(&cols, 0) {
                return i;
            }

            // no reflection found
            0
        })
        .sum()
}

pub fn part_2(input: &str) -> usize {
    let grid = parse(input);
    grid.iter()
        .map(|grid| {
            // check horizontal
            if let Some(i) = reflects_at(grid, 1) {
                return i * 100;
            }

            // check vertical
            let cols = (0..grid[0].len())
                .map(|i| grid.iter().map(|row| row[i]).collect())
                .collect();
            if let Some(i) = reflects_at(&cols, 1) {
                return i;
            }

            // no reflection found
            0
        })
        .sum()
}

Date

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 13

Day 13: Point of Incidence

Parsing

Part 1

Helpers

Code

Part 2

Helpers

Code

Final code