Advent of Code 2023, Day 13

❄️ Back to Advent of Code 2023 solutions homepage ❄️

# Imports
from aoc23.utils import read_input

input_13 = read_input(13)

Part 1

In the first part of the day 13 puzzle, we are provided with a number of arrays containing ash (.) and rocks (#), and are told that these grids contain mirrors which are aligned with one of the two coordinate axes. The task is to identify in each of the grids a perfect vertical or horizontal reflection.

First, process the provided input:

def process_input(input_list: list[str]) -> list[list[str]]:
    out = []
    this_grid = []
    for line in input_list:
        if line == '':
            out.append(this_grid)
            this_grid = []
        else:
            this_grid.append(line)
    out.append(this_grid)
    return out

processed_input = process_input(input_13)

Consider the first grid as an example:

for line in processed_input[0]:
    print(line)

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

By inspection, we can see that the mirror lies vertically, between the 9th and 10th columns of the array.

First, note that we need only consider the case of horizontal mirrors, lying between the rows of the array; the search for vertical mirrors can be done by taking the transpose of the grid, and applying the same analysis as for the horizontal case.

The strategy will be to consider each mirror placement in turn, and compare the two halves of the grid either side of the mirror. By summing the number of differences between each corresponding pair of strings, and then summing over all pairs, we obtain a sum of all the differences between the two halves. Exact matches will have 0 differences.

def summarise_notes(grid: list[str], num_differences=0) -> int:
    # n columns, m rows
    n = len(grid[0])
    m = len(grid)
    
    # A neat way to transpose a list of strings!
    transposed_grid = list(map(lambda x: ''.join(x), zip(*grid)))
    
    # Check each potential row/column mirror position
    # Exact reflections will have 0 differences
    potential_horizontal_line = [sum_differences(grid[j::-1], grid[j+1:]) 
                                 for j in range(m-1)]
    potential_vertical_line = [sum_differences(transposed_grid[i::-1], transposed_grid[i+1:]) 
                               for i in range(n-1)]
    
    # Compute the summaries by finding entries with 0 differences
    horizontal_summary = sum([100*(j+1) 
                              for j, val in enumerate(potential_horizontal_line) 
                              if val == num_differences])
    vertical_summary = sum([i+1 
                            for i, val in enumerate(potential_vertical_line) 
                            if val == num_differences])
    
    # Puzzle leaves open possibility of multiple mirror lines
    return horizontal_summary + vertical_summary

This function relies on this helper function, which compares the two halves of the grid created by each mirror placement:

def sum_differences(half_1: list[str], half_2: list[str]) -> int:
   # Only compare the overlapping portions
    min_length = min(len(half_1), len(half_2))
    half_1 = half_1[:min_length]
    half_2 = half_2[:min_length]
    
    # For each half of the array, compare the corresponding strings
    # Sum the number of differences between each pair
    diffs = [
        sum([char_1 != char_2 for char_1, char_2 in zip(string_1, string_2)]) 
        for string_1, string_2 in zip(half_1, half_2)
    ]
    
    return sum(diffs)

The puzzle provides a couple of examples, as well as the expected summary values:

assert summarise_notes([
    '#.##..##.',
    '..#.##.#.',
    '##......#',
    '##......#',
    '..#.##.#.',
    '..##..##.',
    '#.#.##.#.'
]) == 5

assert summarise_notes([
    '#...##..#',
    '#....#..#',
    '..##..###',
    '#####.##.',
    '#####.##.',
    '..##..###',
    '#....#..#'
]) == 400
print('Success!')

Success!

Running this across all grids in the input file:

sum(map(summarise_notes, processed_input))

40006

So the answer to part 1 is: 40006.

Part 2

In the second part, instead of finding exact reflections in each grid, we are asked to find almost-exact reflections - ones in which each half differ by only a single character. Thankfully (but not coincidentally), the function from earlier has an additional argument, designed in order to find almost-exact matches instead. This makes use of the fact that the function computes the total number of differences between each half, and the only way for this to equal 1 is for there to be a single character mismatch.

Checking this against the provided examples verifies that the function still works with the modification:

assert summarise_notes([
    '#.##..##.',
    '..#.##.#.',
    '##......#',
    '##......#',
    '..#.##.#.',
    '..##..##.',
    '#.#.##.#.'
], num_differences=1) == 300

assert summarise_notes([
    '#...##..#',
    '#....#..#',
    '..##..###',
    '#####.##.',
    '#####.##.',
    '..##..###',
    '#....#..#'
], num_differences=1) == 100
print('Success!')

Success!

Running this one more time against the full list of input arrays gives:

sum(map(lambda x: summarise_notes(x, 1), processed_input))

28627

And so the part 2 answer is: 28627.

❄️ Back to Advent of Code 2023 solutions homepage ❄️