commit518936a44c837c36208afebb8bedf1b4eff7a15fparent72078d6a148a05a9ca40f4872f548fff2ffdaefbAuthor:Eamon Caddigan <eamon.caddigan@gmail.com>Date:Mon, 13 Dec 2021 14:00:13 -0500 Solution to day 13, part 1Diffstat:

A | day13_part1.py | | | 108 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |

1 file changed, 108 insertions(+), 0 deletions(-)diff --git a/day13_part1.py b/day13_part1.py@@ -0,0 +1,108 @@ +#!/usr/bin/env python +"""Advent of Code 2021, day 13 (part 1): Transparent Oragami +Fold a grid of dots repeatedly to reveal a pattern""" + +# Another very numpy problem IMO. I've definitely become more comfortable with +# numpy's interface, and how it differs from interacting with arrays and +# matricies in R and MATLAB. So thanks, Advent of Code! + +from typing import Tuple, List +from itertools import takewhile +import re +import numpy as np +from utils import get_puzzle_input + +EXAMPLE_INPUT = \ +"""6,10 +0,14 +9,10 +0,3 +10,4 +4,11 +6,0 +6,12 +4,1 +0,13 +10,12 +3,4 +3,0 +8,4 +1,10 +2,14 +8,10 +9,0 + +fold along y=7 +fold along x=5 +""" + +def parse_input(input_string: str) -> Tuple[np.ndarray, List[Tuple[int, int]]]: + """Read the dot positions and folding instructions, and return a tuple containing: + * A 2d boolean array of dots + * A list of folding instructions, each consisting of a tuple giving the + * axis (an int, 0 or 1) and position (also an int)""" + # In numpy, axis 0 is rows, and 1 is columns. So a folding direction of y=7 + # tells us to fold *at* y=7 (looking at the example, we're supposed to use + # zero-based indexing, so yay Python here I guess). I'll talk more about + # folding later, but I just want to specify how folds will be specified: + # axis (0 for a y fold, 1 for an x fold) and position. + + # I'm having fun with Python's generators: this will let us swallow up all + # the coordinate lines, and then deal with the folding instructions later + line_gen = (line for line in input_string.rstrip('\n').split('\n')) + + # Coordinates are given in x,y pairs and we'll change them to + # numpy-friendly row,col order + coordinates = np.flip( + np.array([l.split(',') for l in takewhile(lambda x: x, line_gen)]) + .astype(int), + axis=1 + ) + + # Create the dot grid that we'll be folding + dotgrid = np.zeros(np.apply_along_axis(max, 0, coordinates) + 1, + dtype=bool) + dotgrid[coordinates[:,0], coordinates[:,1]] = True + + # Parse the folding instructions: we just want to yank out the axis (y = 0, + # x = 1) and the value. Regex is overkill but I'm getting reaquainted with + # python's funky re module here + matches = (re.match(r"fold along (?P<axis>x|y)=(?P<value>\d+)", l) \ + for l in line_gen) + instructions = [({'y': 0, 'x': 1}[m.group('axis')], int(m.group('value'))) \ + for m in matches if m is not None] + + return (dotgrid, instructions) + +def fold_dotgrid(dotgrid: np.ndarray, instruction: Tuple[int, int]) -> np.ndarray: + """Apply a fold (specified by axis--0 for rows, 1 for cols--and position) + to the dotgrid, and return a new dotgrid""" + # Hack: if we'll do all folds along axis 0, and if 1 is requested we'll + # transpose the results before and after folding + if instruction[0]: + return np.transpose( + fold_dotgrid(np.transpose(dotgrid), (0, instruction[1])) + ) + + # Ugh I hate doing slice math + folded_grid = dotgrid.copy()[0:instruction[1], :] + folded_grid[2*instruction[1] - dotgrid.shape[0] + 1:, :] |= np.flip( + dotgrid[instruction[1]+1:, :], + axis=0 + ) + + return folded_grid + +def solve_puzzle(input_string: str) -> int: + """Return the numeric solution to the puzzle""" + dotgrid, instructions = parse_input(input_string) + return fold_dotgrid(dotgrid, instructions[0]).sum() + +def main() -> None: + """Run when the file is called as a script""" + assert solve_puzzle(EXAMPLE_INPUT) == 17 + print("Number of dots visible after the first fold:", + solve_puzzle(get_puzzle_input(13))) + +if __name__ == "__main__": + main()