import copy
from typing import List
from typing import Tuple

problem = """LLLL.LLLLL.LLLLLLLLLLLLLLLL.L.LLLLLL.LLLL..L.LLLLLLLL.LLLLLL.LLLL..LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
LLLLLLLLLLLLLLLLLLLLLLLLLLL.LLL.LLLLLLLLL.L..LLLLLLLL.LLLLLL.LLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLL.LLLLLLLLLLL.LLLL.LLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLL.LL.LLLL.LL.LLLLLLLLLLLLLLLLLLLL
LLL.LLLLLLLLLLL.LLLL.LLLLLLLLLL.LL.L.LLLLLLL.LLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLL.LLLLL.LLLLLLLL
LLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLL.LLL.LLLL.LLLLLLLLLLL.LLLLLLLLLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLL.LLLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLLLLLL.LLLLLLLLLLLLLL
...L..LL.LL.LLL....L......L..L.....L.....L....L.LL.....LL..L.L...LL.L...LL..L.L...L.LL...L..LL..L.
LLLLLLLLLLLLLLLLLL.L.LLLLLL.LLLLLLLL.LLLLL.L.LLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLL.LLLLL.LLLLLLLL.LLLLL
LLLLLLLLL.LLLLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLL.LLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLLLLLLLLLLLLLLLLLLL.L.LLLL.L.LLLLL.L.LLLLLLLL.LLLLLLLLLLLL.LLLLLLL.LLLLLLLL.LLLLL.LLLLLLLL
LLLLLLL..L.LLLLLLLL..LLL.LL.LLLLLL.L.LLLLLLL.LLLLLLLL.LLLLLL.LLLLL.LL.LLLL.LLLLLLLL.LLLL.LLLLLLLLL
...L..L.L.L......L....L.L..L...L.L..L.L...LL.LL....L...L........L.L.LLL....L..L..L...L.L..L..LL...
LLLLLLLLLL.LLLLLLLLLLLLLLLL.L.LLLLLL.LLLLLLL.LLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLL.L.LLLLLLLLLLLLLLLL
LLLLLLLLLLLLLLLLLLLL.LLLL.L.LLLLLLLLLLLLLLL..LLLLLLLL.LLLLLL.LLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLLL
LLL.LLL.LL.LLLLLLLLL.LLLLL..LLLLLLLL.LLLLLLLLLLLLLLL..LLLLLLLLLLLL.LLLLLLL.LLLLLLLL.LLL.LLLLLLLLLL
.LLLLLLLLL.LL.LLLLLL.LLL.LLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLLLLL.LL.LLLLLLLLLLL
LLLLL.LLLLLLLLLLLLLL.LLLLLL.LLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL
.LLLLLLLLLLLLLLLLLLL.L.LLLL.LLLLLLLL.LLLLLLLLLLLLLLLLLLL..LL.LLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL
L....LL.....L......LLL......L.LLL..L....L.L....L....LL.L.LL.LL........LL....L.L.L..LLLL.......L...
LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLL.LLL.LLL.LLLLLLLL.LLLLLLLLLLLLLL
.LL..LL.LL.LLLLLLLLL.LL.LLLLLLLLLLLL.LLLLLLL.LLLLL.LLLLLLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLL
LLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLL.LL.LLLLLL.LLLLL.LLLLLLL.L.LL.LLLLLLLLLLLLLLLLLL
LLLLLLLLLL..LLLLLLLL.LLLL.L.LLL.LLLLLLLLLLLL.LLLLLLLL.LLLLLL.LLLL..LLLLLLLLLL..LLLL.LLLLLLLLLLLLLL
LLL.LLLLLL.LLLLLLLLL.LLLLLL.LLLLLLL..LLLLLLL..LLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL
.LLLLLLLLLLLLLLLLLLL.LLLLLL.LL.LLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
LLLLLLLLLLLLLLLLLLLL.LL.LLL.LLLLLLLL.LLLLLLL.LLLLLLLL..LLL.L.LLLLL.LLLLLLL.LLLLLL...LLLLLLLLLLLLLL
LLL.LLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLL.LLLL
LLLL.LLLLL...LLLLLLLLLLL.LL.LLLLLLLL.LLLLLLL.LLLLLLLLLLLLLL..LLLLL.LLLLLLL..LLLLLLL.LLLLLLLLLLLLLL
..L...LLL........LL....L.....L.....L..L..L.....L.L.LL...L......LLLLL.L.L...........L.LL.....LL...L
LLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLL.L.LLL.LLL.LLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLL.LLLLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLL.LLLLLL
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLL.LLL
LLLLLLLLLLLLLLLL.LLLLLLLLLL.LLLLLLLLLLLLL.LL.LL.LLLLLLLLLLLL.LLLLL.LLLLLLLLLLLL.LL.LLL.LLLLLLLLLLL
LLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLL...LLLLLLLLLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLL.LL
LLLLLLL.LL.LLLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLL..LLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLLLLL
....L..L.L.LL..LLL..L....LL...L.L..LL.L......L...LLL.L.L.L.....L.......L......LL.....L..L.L..LL...
LLLLLLLLLL.LLLLLLLLL.LLLLLL.LLLLLLLL.LLLLLL.LLLLLLLLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLL.LLLLLLLLLLLLL.L
LLLLLLLLLL.LLLLLLLLL.LLLL.L.LLL.LLLL.LLLLLLL.LLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLLLLL.LLLLLL.LLLLLLLLLLLLLL...LLLLLL.LLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLL.LLLLLLLLLLLL.LLLLLLLLL..LLLLLLLLLLLLLLLLLL.LLLLLLL.LLLL.LLLLLLL.LLLLLLLL.LLL.LLLLLLLLLL
LLLLLLLLLL.L.LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL.LLLL.LLL.LLLLLL.LLLLLLLLLLLLLLLLLLLLLL.LLL.LLLLLLLLLL
LL.LLLLLLL.LLLLLLLLL.LLLLLL.LLLLLLLL.LLLLLLLL.LLLLLLL.LLL.LL.LLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLLLLL
..LL.LLL...LLL.....L.L.L......L......L........L.LL......LLL..LL..L..L.LLL..LL..LL.L.....L.LL....L.
LLLLLLLLLL.LL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLL.LLLLLLLL..LLLL.LLLLLLLL
LLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.LL.LLLLLL.L.LLLLLLLLL.L.LLLLL.LL.L.LLLLLLLLLLLL
LLLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLLLL.LLLLLLLLLLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLLL.LLLLLLL.LL.LLLLL.LLLLLLLLLLL.LL
LLLLLLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLLLLLL.LLLLLLLLLL.LLLLL.LLL.LLL.LLLLL.LL.LLLLLLLLLLLLLL
L..L..LL..LLL...L......L.....L...LL..L..L.....L.L...LL......L.L.LLL.L..L....L....L...L.L........LL
LLLLLLLLLL.LLLLLLLLLLLLLLLLLLLL.LLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLL..LLLLLLLLLLLLLL
LLLLLL.LLL.LLLLLLLLL.LLLLLLLLLLLLLLL.L.LL.LLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLL
L.LLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLLL.LLLL.L.LLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLL.LLL.LL.LL.LLLLLLLLL.LL.LL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLL.LLLLL.LL.LLLLLLLLLLLLLL
LL.LLLLLLLLLLLLLL.LL.LLLLLLLLLLLLLL..LLLLLLLLLL.LLL.L..LLLLL.LLLLL..LLLLLL.LLLLLLLLLLLLLLLLLLLLLLL
LLLLLLLLLLLLLL.LLLLLLLLLLLL.LLLLLLLL.LLL.LLLLLLLLLLLL.LLLLLL.LLLLL.LLLLLLL..LLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLL.LLL.LLLLL.LL.LLLLLLLLLLLL.LLLLLLL.LLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLL.LL.L.LLLLLLL.LLL.L.
LLLLLLLLLLLLLLLLLLLL.LLLL.LLLLLLLLLL.LLL.LLL.LLLLLLLL.LLLLLL.LLLLLLLLLLLLLLLLL.L.LL.LLLLLLLLLL.LLL
..L....L....L....L........L...L....L..LL.L.L..L.LLLL.L.LLL...L...L..LL..L...L....L....L.......L.L.
LLLLLLLLLL..LLL.LLLLLLLLLLL.LLLLLLLL.LLL.LLL..LLLLLLL.LLLLLL.LLLLL.LLLLLLLLLLLLLLL..LL..LLLLLLLLLL
LLLLLLLLLL.LLLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLL.LL.LLLLL.LLLLLL.LLLLLLLLLLLL..LLLLLLLLLLLLLLLLLLLLLLL
LLLLLLLLL.LLLLLLLLLLLLLLLLL..LLLLLLL.LLLLLLLLLLLLLLLL.LLLLLL.LLLLL.LLLLLLLLLLLLLLLL.LLLL.LLLLLLLLL
LLLLLLLLLL.LLLLLLLLL.LLLLLL..LLLLLLL..LLLLLL.LL.LLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLLLL.L
L.LLLLLLLL.LLLLLLLLL.LL.LLL.LLLLLLLLLLLLLLL..LLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLL..LLL.LLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLLLLLLL.LLLLL..LLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL
L.....L..LLL.....LL.L..L..LL....LLLLL.LL..L.......L...LL.....LL...L...........L.....L.L..L.....L.L
LLLLLLLLLL.LLL.LLLLL.LLLLLL.LLLLLLLL.LLLLLLL.LLLLLLLLL.LLLL..LLL.LLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLLL
LLLLLLLLLL..LLLLL.LL.LLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLL.LLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLL.LLLLLLLLL.LLLLLL.LLLLLLLL.LLLLLLL.LLLLLLLL.LLLL.L.LLL.LLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLL.LLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLL.LL.LLLLLLLLLLLLLLL
LLLLL.LLLL.LLLLLLL.LLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLL.LLLL..LLLLLLL.LLLLLLLL.LLLLLLLLLLLLLL
LLLLLLLLLLLLLLLLLLLL..LLLLL.LLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLLL.LLLLLL..LLLLLLLL.LLLLLLLLLLLLLL
........LLLLLL.LL.L..L...L...LLL....L.......LLLL..L.LL.L..L.L.LLL...L...L.......L..L.....L.L.L..LL
LLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLL.LL.LLL..LLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLL
LLLLLLLLLL.LLLLLLLLL.LLLLLL.LLLLLLLLLLLLLLL..LLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLL.LLLLLLLLLL
L.LLLLL.LLLLLLLLLLLL.LLLLLL.LLLLLLLLLLL.LLLL.LLL.LLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLLL
LLLLLL.LLL.LLLLLLLLLLLLL.LLLLLLLLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLLL.LLL.L.L.LLLLLLLL.LLLLLLLLLLLLLL
LLL.LLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
LLLLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLL.LL.LLLLLLLLLLLLLLLLLLLLL.LLLLLLL..LLLLLLL.LLLLLLLLLLLLLL
..LL..L....L.......L....L....LL...L.L..L.........LL..L..LL.L....LLL.L.LLL...L.....LL.....LL.LL....
LLLLLLLLLL.LLLLLL.LL.LLLLLLLL..LLLLL.LLLLLLLLLLLLLLLL.LLLLLL.L.LLLLLLLLLLL.LLLLLLLL.LLLLLLLLLL.LLL
L.LLLLLLLLLLLL.LLLLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLL.LL.LLLLLL.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLL.LLLLLL
LLLLLLLLLL.LLLLLLLLL.LLL.LL.LLLLLLLL.L.LLLLLLLLLLLLLLLLLLLLL.L.LLL.LLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.
LLLLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLL
LLLLL.LLLL.LLLLLLLLL.LLLLLL.LLLL.LLL..LLLLLL.LLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLL.LLLLL.LLLLLLLLLLLLLL
LLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLL.LLLLLLLLL.LLLL
LLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLL.L.LLLLLLLLLLLLLL.LLLLLL.LLLLL.LLLLLLLLLLLLLLLL.LL.LLLLLLLLLLL
.L.L....L........L....LL...L...L...L..L.............LL.LL..L.L.L...LL.......LLL.......LLL.L.L.L..L
LLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLL.LL.LLLLLLLLLLLLLL.L.LLLLL..LLLLL.LLLLLLL.LLLLLLLL.LLLL.LLLLLLLLL
LLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLL.LLLLLLLL.LLLLLL.LLLLLLL
LLLLLLLLLL..LLLLLLLL.LLLLLL..LLLLLLL.LLLLLLLLLLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLLLLL.LLLLLLLLLLLLL
LLLLLLLLLL.L.LLLLLLL.LLLLLLLLLLLLLL.LLLLLLLL.LLL.LLLL.LLLLLLLLL.LLLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLLL
LLLLL.LLLLLLLLLLLLLL.LLLLLL.LLLLLLLL.LLLLLLLLLLLLLL.L.LLLLLL.LLLLL.LLLLLLL.LLLLLLLL.L.LLLLLLLLLLLL
"""

example = """L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL"""


def filled_neighbors_search(board: List[List[str]], i: int, j: int, slope: Tuple[int, int]):
    if i < 0 or i >= len(board):
        return 0
    if j < 0 or j >= len(board[0]):
        return 0
    if board[i][j] == 'L':
        return 0
    if board[i][j] == '#':
        return 1

    return filled_neighbors_search(board, i + slope[0], j + slope[1], slope)


def num_filled_neighbors(board: List[List[str]], i: int, j: int):
    filled_neighbors = 0
    if i > 0 and board[i - 1][j] == '#':
        filled_neighbors += 1
    if i < len(board) - 1 and board[i + 1][j] == '#':
        filled_neighbors += 1
    if j > 0 and board[i][j - 1] == '#':
        filled_neighbors += 1
    if j < len(board[0]) - 1 and board[i][j + 1] == '#':
        filled_neighbors += 1

    # diagonals
    if i > 0 and j > 0 and board[i - 1][j - 1] == '#':
        filled_neighbors += 1
    if i < len(board) - 1 and j < len(board[0]) - 1 and board[i + 1][j + 1] == '#':
        filled_neighbors += 1
    if i > 0 and j < len(board[0]) - 1 and board[i - 1][j + 1] == '#':
        filled_neighbors += 1
    if i < len(board) - 1 and j > 0 and board[i + 1][j - 1] == '#':
        filled_neighbors += 1

    return filled_neighbors


def next_round_part_2(board: List[List[str]]):
    # each of the 8 possible directions we can go from a particular seat
    slopes = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]
    new_board = copy.deepcopy(board)

    changed = False
    for i in range(len(board)):
        for j in range(len(board[0])):
            filled_neighbors = 0
            for slope in slopes:
                filled_neighbors += filled_neighbors_search(board, i + slope[0], j + slope[1], slope)
            if board[i][j] == 'L' and filled_neighbors == 0:
                new_board[i][j] = '#'
                changed = True
            elif board[i][j] == '#' and filled_neighbors >= 5:
                new_board[i][j] = 'L'
                changed = True

    return new_board, changed


def next_round(board: List[List[str]]):
    # is a shallow copy enough?
    new_board = copy.deepcopy(board)

    changed = False
    for i in range(len(board)):
        for j in range(len(board[0])):
            filled_neighbors = num_filled_neighbors(board, i, j)
            if board[i][j] == 'L' and filled_neighbors == 0:
                new_board[i][j] = '#'
                changed = True
            elif board[i][j] == '#' and filled_neighbors >= 4:
                new_board[i][j] = 'L'
                changed = True

    return new_board, changed


if __name__ == '__main__':
    # conways game of plane seats
    board = [list(row) for row in problem.splitlines()]
    board_2 = copy.deepcopy(board)
    # part 1
    next_board, changed = next_round(board)
    while changed:
        next_board, changed = next_round(next_board)
    print(len([seat for row in next_board for seat in row if seat == '#']))

    # part 2, search in all directions for first seat rather than one space away
    next_board, changed = next_round_part_2(board_2)
    while changed:
        next_board, changed = next_round_part_2(next_board)
    print(len([seat for row in next_board for seat in row if seat == '#']))