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 643d9f271aa734ea1e15efecede9faff003ddc13
parent b9bb6aca87645ca2d1bb28b4e2fe81c9fcdc32ba
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date:   Tue,  4 Jan 2022 21:37:54 -0500

Merge branch 'day25' into main

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

diff --git a/day25_part1.py b/day25_part1.py @@ -0,0 +1,123 @@ +#!/usr/bin/env python +"""Advent of Code 2021, day 25 (part 1): Sea Cucumber +Simulate the movement of sea cucumbers""" + +# Going to use NumPy again. I'm going to represent the seafloor grid using +# integers, with 0 corresponding to an empty space, 1 corresponding to an +# east-moving sea cucumber, and 2 corresponding to a south-moving sea cucumber. +# E.g., the puzzle input: +# +# v...>>.vv> +# .vv>>.vv.. +# >>.>v>...v +# >>v>>.>.v. +# v>v.vv.v.. +# >.>>..v... +# .vv..>.>v. +# v.v..>>v.v +# ....v..v.> +# +# Becomes: +# +# 2000110221 +# 0221102200 +# 1101210002 +# 1121101020 +# 2120220200 +# 1011002000 +# 0220010120 +# 2020011202 +# 0000200201 + +#from typing import Tuple, List, NewType + +import numpy as np + +from utils import convert_input_to_array, get_puzzle_input + +EXAMPLE_INPUT = \ +"""v...>>.vv> +.vv>>.vv.. +>>.>v>...v +>>v>>.>.v. +v>v.vv.v.. +>.>>..v... +.vv..>.>v. +v.v..>>v.v +....v..v.> +""" + +def parse_input(input_string: str) -> np.ndarray: + """Given the puzzle input, return a 2d numpy array""" + return convert_input_to_array( + input_string + .replace('.', '0') + .replace('>', '1') + .replace('v', '2') + ) + +def shift_up(cucumber_map: np.ndarray) -> np.ndarray: + """Return the entire map shifted down""" + return np.vstack((cucumber_map[1:, :], cucumber_map[0, :])) + +def shift_down(cucumber_map: np.ndarray) -> np.ndarray: + """Return the entire map shifted down""" + return np.vstack((cucumber_map[-1, :], cucumber_map[0:-1, :])) + +def is_empty(cucumber_map: np.ndarray, direction: str) -> np.ndarray: + """Given a cucumber map, check if the adjacent space in the given direction + is empty""" + if direction == 'east': + return np.transpose(is_empty(np.transpose(cucumber_map), 'south')) + # So actually we just need to check that the space to the south is empty + # (remembering that we wrap around to the top row from the bottom + assert direction == 'south' + return shift_up(cucumber_map) == 0 + +def shift_selected(cucumber_map: np.ndarray, movers: np.ndarray) -> np.ndarray: + """Shift the selected elements down one row""" + new_map = cucumber_map.copy() + new_map[shift_down(movers).nonzero()] = cucumber_map[movers.nonzero()] + new_map[movers.nonzero()] = 0 + return new_map + +def move_herd(cucumber_map: np.ndarray, direction: str) -> np.ndarray: + """Move the herd in the given direction""" + movers = is_empty(cucumber_map, direction) + if direction == 'east': + movers &= cucumber_map == 1 + new_map = np.transpose(shift_selected(np.transpose(cucumber_map), + np.transpose(movers))) + elif direction == 'south': + movers &= cucumber_map == 2 + new_map = shift_selected(cucumber_map, movers) + else: + raise ValueError('Direction must be "east" or "south"') + return new_map + +def step_herd(cucumber_map: np.ndarray) -> np.ndarray: + """Move the whole herd east, and then south""" + return move_herd(move_herd(cucumber_map, 'east'), 'south') + +def run_until_stuck(cucumber_map: np.ndarray) -> int: + """Keep stepping the herd through its moves until it stops moving""" + herd_position = cucumber_map + for step_number in range(1_000_000): + new_position = step_herd(herd_position) + if (new_position == herd_position).all(): + return step_number+1 + herd_position = new_position + raise RuntimeError('Failed to lock up after very many steps') + +def solve_puzzle(input_string: str) -> int: + """Return the numeric solution to the puzzle""" + return run_until_stuck(parse_input(input_string)) + +def main() -> None: + """Run when the file is called as a script""" + assert solve_puzzle(EXAMPLE_INPUT) == 58 + print("Steps for cucumbers to become stuck:", + solve_puzzle(get_puzzle_input(25))) + +if __name__ == "__main__": + main()