advent_of_code_2021

My attempts to work through the 2021 Advent of Code problems.
git clone https://git.eamoncaddigan.net/advent_of_code_2021.git
Log | Files | Refs | README | LICENSE

commit f3fa62f6f9672706ac5f44c628fcdfd705df2842
parent bbe48acdc50b4999423ed00bd15b2c0d23d9e1cf
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date:   Mon, 20 Dec 2021 09:22:55 -0500

Solution to day 20, part 1

Diffstat:
Aday20_part1.py | 105+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 105 insertions(+), 0 deletions(-)

diff --git a/day20_part1.py b/day20_part1.py @@ -0,0 +1,105 @@ +#!/usr/bin/env python +"""Advent of Code 2021, day 20 (part 1): Trench Map +Iteratively apply an 'image enhancement algorithm' to a map of the trench +floor""" + +# I peeked at the puzzle input to see if I wanted to use sparse or dense +# matrices for this, and it looks like dense (i.e., 2d numpy arrays) is the way +# to go. +# +# For the record, I made the (apparently very common) mistake of assuming that +# the "world" remained 0 across all enhancements, and did submit an incorrect +# answer before I figured it out. + +from typing import Tuple +from functools import reduce +import numpy as np +from utils import get_puzzle_input + +EXAMPLE_INPUT = \ +"..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..##" + \ +"#..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###" + \ +".######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#." + \ +".#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#....." + \ +".#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.." + \ +"...####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#....." + \ +"""..##..####..#...#.#.#...##..#.#..###..#####........#..####......#..# + +#..#. +#.... +##..# +..#.. +..### +""" + +def parse_input(input_string: str) -> Tuple[np.ndarray, np.ndarray]: + """Given the puzzle input, return a tuple containing the image data (a 2d + numpy array of integers) and a lookup table (a 1d numpy array of integers)""" + # I'm ditching the '#' / '.' representation right away; we want zeroes and + # ones here + lines = input_string.rstrip('\n').split('\n') + lookup_table = np.array([{'#': 1, '.': 0}[c] for c in lines[0]]) + image_data = np.array( + [[{'#': 1, '.': 0}[c] for c in l] for l in lines[2:]] + ) + return (image_data, lookup_table) + +def dilate_image(image_data: np.ndarray, + dilate_with: int) -> np.ndarray: + """Given an n x m image matrix, return a (n + 2) x (m + 2) matrix of the + same image padded around with `dilate_with`""" + new_image = np.zeros((image_data.shape[0] + 2, image_data.shape[1] + 2), + dtype=int) + dilate_with + new_image[1:-1, 1:-1] = image_data[:, :] + return new_image + +def find_pixel_indices(image_data: np.ndarray, + world_state: int) -> np.ndarray: + """Use each pixel's neighborhood to convert it to an index (in the range + 0..512); given an n x m image returns an (n + 2) x (m + 2) set of indices""" + # Using dilate this way is "inefficient", but it's fast enough that the I + # think it's a good ease of programming / speed of execution tradeoff. + image_dilated = dilate_image(dilate_image(image_data, world_state), + world_state) + image_indices = dilate_image(np.zeros_like(image_data), 0) + for exponent in range(9): + col_offset = 2 - exponent % 3 + row_offset = 2 - exponent // 3 + image_indices += 2**exponent * image_dilated[ + row_offset:row_offset+image_indices.shape[0], + col_offset:col_offset+image_indices.shape[1] + ] + return image_indices + +def enhance_image_once(image_data: np.ndarray, + world_state: int, + lookup_table: np.ndarray) -> Tuple[np.ndarray, int]: + """For each pixel in the image, consider its 8-connected neighborhood; + these values represent bits in an integer, which is then used to index into + a lookup table to find the new value for the pixel and a new `world_state`""" + # World state is either 0 or 1. If it's 0, every unexamined pixel in the + # world is replaced with `lookup_table[0]`, and if it's 1 they're replaced + # with `lookup_table[511]` + return (lookup_table[find_pixel_indices(image_data, world_state)], + int(lookup_table[{0: 0b0, 1: 0b111111111}[world_state]])) + +def enhance_image(image_data: np.ndarray, lookup_table: np.ndarray, + num_enhancements: int) -> Tuple[np.ndarray, int]: + """Apply the enhancement `num_enhancements` times, starting with an initial + `world_state` of 0""" + return reduce(lambda x, y: enhance_image_once(x[0], x[1], lookup_table), + range(num_enhancements), + (image_data, 0)) + +def solve_puzzle(input_string: str) -> int: + """Return the numeric solution to the puzzle""" + return enhance_image(*((parse_input(input_string)) + (2,)))[0].sum() + +def main() -> None: + """Run when the file is called as a script""" + assert solve_puzzle(EXAMPLE_INPUT) == 35 + print("Total number of lit pixels:", + solve_puzzle(get_puzzle_input(20))) + +if __name__ == "__main__": + main()