102 lines
3.2 KiB
Python
102 lines
3.2 KiB
Python
#!/usr/bin/env python
|
|
|
|
from copy import deepcopy
|
|
from enum import Enum, auto
|
|
from functools import cache
|
|
from itertools import chain
|
|
import sys
|
|
from typing import Iterable, List, Optional, Tuple
|
|
|
|
NEIGHBOURS = [(dx, dy) for dy in (-1, 0, 1) for dx in (-1, 0, 1) if not dx == dy == 0]
|
|
|
|
class Tile(Enum):
|
|
FLOOR = '.'
|
|
FREE = 'L'
|
|
OCCUPIED = '#'
|
|
|
|
class Layout:
|
|
def __init__(
|
|
self,
|
|
s: str,
|
|
max_neighbour_steps: Optional[int],
|
|
occupied_neighbours_to_leave: int):
|
|
self._store = [[Tile(c) for c in line] for line in s.splitlines()]
|
|
self.num_rows = len(self._store)
|
|
self.num_cols = len(self._store[0])
|
|
self.max_neighbour_steps = max_neighbour_steps
|
|
self.occupied_neighbours_to_leave = occupied_neighbours_to_leave
|
|
|
|
def tiles(self) -> Iterable[Tile]:
|
|
return chain.from_iterable(self._store)
|
|
|
|
def get(self, row: int, col: int) -> Tile:
|
|
return self._store[row][col]
|
|
|
|
def set(self, row: int, col: int, t: Tile) -> None:
|
|
self._store[row][col] = t
|
|
|
|
def step(self) -> bool:
|
|
new_tiles = []
|
|
|
|
for row in range(self.num_rows):
|
|
for col in range(self.num_cols):
|
|
num_neighbours = self.count_neighbours(row, col)
|
|
tile = self.get(row, col)
|
|
new_tile = None
|
|
if tile == Tile.FREE and num_neighbours == 0:
|
|
new_tile = Tile.OCCUPIED
|
|
elif tile == Tile.OCCUPIED and num_neighbours >= self.occupied_neighbours_to_leave:
|
|
new_tile = Tile.FREE
|
|
|
|
if new_tile is not None:
|
|
new_tiles.append((row, col, new_tile))
|
|
|
|
for row, col, tile in new_tiles:
|
|
self.set(row, col, tile)
|
|
|
|
return len(new_tiles) != 0
|
|
|
|
def _find_neighbour(self, row: int, col: int, direction: Tuple[int, int]) -> Optional[Tuple[int, int]]:
|
|
steps = 0
|
|
while self.max_neighbour_steps is None or steps < self.max_neighbour_steps:
|
|
row += direction[0]
|
|
col += direction[1]
|
|
if row < 0 or row >= self.num_rows:
|
|
break
|
|
if col < 0 or col >= self.num_cols:
|
|
break
|
|
|
|
if self.get(row, col) != Tile.FLOOR:
|
|
return (row, col)
|
|
steps += 1
|
|
|
|
return None
|
|
|
|
@cache
|
|
def _neighbour_coords(self, row: int, col: int) -> List[Tuple[int, int]]:
|
|
coords = []
|
|
for direction in NEIGHBOURS:
|
|
neighbour = self._find_neighbour(row, col, direction)
|
|
if neighbour is not None:
|
|
coords.append(neighbour)
|
|
return coords
|
|
|
|
def neighbours(self, row: int, col: int) -> Iterable[Tile]:
|
|
for nrow, ncol in self._neighbour_coords(row, col):
|
|
yield self.get(nrow, ncol)
|
|
|
|
def count_neighbours(self, row: int, col: int) -> int:
|
|
return sum(1 for tile in self.neighbours(row, col) if tile == Tile.OCCUPIED)
|
|
|
|
|
|
def run(layout: Layout) -> int:
|
|
while layout.step():
|
|
pass
|
|
|
|
return len([t for t in layout.tiles() if t == Tile.OCCUPIED])
|
|
|
|
if __name__ == '__main__':
|
|
layout_str = sys.stdin.read()
|
|
print(run(Layout(layout_str, 1, 4)))
|
|
print(run(Layout(layout_str, None, 5)))
|