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 gridsfn 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 horizontalif let Some(i) = reflects_at(grid) {return i * 100;}// check verticallet 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 found0}).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 horizontalif let Some(i) = reflects_at(grid) {return i * 100;}// check verticallet 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 found0}).sum()}
The differences between part1 and part2 are minor, so I made that helper function take a variable amount of smudges.
Final code
1use std::collections::VecDeque;23#[derive(Debug, Clone, Copy, PartialEq, Eq)]4enum Tile {5 Ash,6 Rock,7}89// parse input to a list of 2D grids10fn parse(input: &str) -> Vec<VecDeque<Vec<Tile>>> {11 input12 .split("\n\n")13 .map(|block| {14 block15 .lines()16 .map(|line| {17 line.chars()18 .map(|c| match c {19 '.' => Tile::Ash,20 '#' => Tile::Rock,21 _ => panic!("at the disco"),22 })23 .collect()24 })25 .collect()26 })27 .collect()28}2930fn reflects_at(grid: &VecDeque<Vec<Tile>>, smudges: usize) -> Option<usize> {31 (1..grid.len()).find(|&offset| {32 let half1 = grid.iter().take(offset).rev();33 let half2 = grid.iter().skip(offset);34 let combined = half1.zip(half2); // the shortest half determines how long this is!35 let found_smudges: usize = combined36 .map(|(row1, row2)| row1.iter().zip(row2.iter()).filter(|(a, b)| a != b).count())37 .sum();3839 found_smudges == smudges40 })41}4243pub fn part_1(input: &str) -> usize {44 let grid = parse(input);45 grid.iter()46 .map(|grid| {47 // check horizontal48 if let Some(i) = reflects_at(grid, 0) {49 return i * 100;50 }5152 // check vertical53 let cols = (0..grid[0].len())54 .map(|i| grid.iter().map(|row| row[i]).collect())55 .collect();56 if let Some(i) = reflects_at(&cols, 0) {57 return i;58 }5960 // no reflection found61 062 })63 .sum()64}6566pub fn part_2(input: &str) -> usize {67 let grid = parse(input);68 grid.iter()69 .map(|grid| {70 // check horizontal71 if let Some(i) = reflects_at(grid, 1) {72 return i * 100;73 }7475 // check vertical76 let cols = (0..grid[0].len())77 .map(|i| grid.iter().map(|row| row[i]).collect())78 .collect();79 if let Some(i) = reflects_at(&cols, 1) {80 return i;81 }8283 // no reflection found84 085 })86 .sum()87}
Series navigation for: Advent of Code 2023