initial = '''.LLLL.L.LLLL.LL.LLL.L.LLLLLLL.LLLLL.LLLLLLLLLLLLL.LLLL.LLL.LLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLL.LLL..LLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL
LLLLLLLLLLLL.LL.LLLLL.LLLL.L.LLLL.LLLLLL.L.LLL.LL..LLL.LLLLLLLLLLLLLLLLLL.L.LLL.LLLLLLL.LLLLL
LLLLLLLLLLLLLLL.LLLLL.LLLLLL.LLLLLLL.LLLLL.LLLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.L.LLL
LL.LLLL.LLLLLLL.L.LLL.LLLLLL.L.LL.LLLLLLLL.LLLLLLLLL.LLLL.LLLLLL.LLLLLLLL.LL.LL.LLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLL.LLLLLLL.LLL.LLLLL.LLLLLLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LLLL.L.LLLLLLLLLLLL
LLLLLLL.LLLLLLL.LLLLLLLLLLLL.LL.L.LLLLLLLL.LLLLLLLLLLL.LLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLL.LLLL.
LLLLLLLLLLLLLLL.LLLLLLLLLLL..LLLL.LLLLLLLL.LLLLLL.LL.L.LLLLL.LLL.LLLLLLLLLLLLL.LLLLLLL.L.LLLL
....L..L.....L......LL...L.LL.......L...L.L......L.L.LLL....L..L....L.LL..LLL....LL..L..L...L
LLLLLLLLLLLLL.L.LLLLLLLLLLLL.LLLLLL.LLLLLL.LLLLLL.LLLLLLLLLLLLLL.LLLL.LLL.LLLLL.LLLLLLLLLLLL.
LLLLLLL.LLLLLLL.LLLLLLLLLL.L.LLLL.LLLLL.LL.LLLLLL.LLLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL
LLLLLLL.LLLLLLL.LLLLL.LLLLLL.LLLL.LLLLLLLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.LLLLL
LLLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLL.LLLLL.LL.LL.LLLLLLLL.LLLLLLLLLLLLLLLLLL..LLLL.LLLLLLLLLLLLL
LLLL.LL.LLLLLLLLLLLLL.LLLLLL.LLLL.LLLLLLLL.LLLLLL.LLLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.L.LLL
LLLLLLL..LLLLLL.LLLLL..LLLLL.LLLL.LLLLLLLLLLL.LLL.LLL..LLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLL..LLLL
...L...L..LL....L.......L...L.......LL........LL.....LL....L.....LL............L..LL....L....
LLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLL.LLLLLLLL.LLLLLL.LLLL..LLLLLLLL.LLLLLLLL.LLL.L.LLLLLLLLLLLLL
LLLLLLL.LLLLLLL.LLLLLLLLLLLL.L.LLLLLLLLLLL.LLLLL.LLLLLLL..LLLLLL.LLLLLL.LLLLLLLLLLLLL.L.LLLLL
LLLLLLL.LLLLLLLLLL.L..LLLLLLLLLLL.L.L.LLLLLLLLLLL.LLLL.LLLLL.LLL.LLLLLLLL.LLLLLLLLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLL.LLLLLL.LLLL.LLLLLLLLLLLLL.L.LLLL.LLLLLLLLL.LLLLLLLL..LLLL.LLLLLLLLLLLLL
LLLLLLLLLLLL.LL.LLLLL.LLLLLL.LLLLLLLLLLLLL..LLLLL.LLLL.LLLLL.LLL.LLLLLLLL.LL.LLLLLLLLLL...LLL
LLLLLLLLLLLLLLL.LLLLL.LLLLLL.LLLLLLLLLLLLLLLLLLLL.L.LLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL
LLLLLLL.LLLLLLL.LLLLLLLLLLLL.L.LL.LLLLLL.LLLLLLLL.LLLLLLLLLLLLLL.LL.LLLLL.LLLLL.LLLLLLL.LLLLL
LLLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLL.LLLLLLLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLL.L.LLLLL
...........LL.....L.LL....L....L..LL..LL.L.LLLL........LL.L.LL..L......L...LL...LL..L.L......
LLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLL.LLLLL.LL.LLLLLL.LLLL.LLL.LLLLL..LLLLLLLLLLLLLLLLLLLLL.LLLLL
LLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLLLLLLL.LLLLLLLLLL.LLLL.LLLLLLLLLLLLLLLL.L.LLLLLLLLLLLLL.LLLLL
LLLLLLLLLLLLLLL.LLLLL.LLLLLLLLL.LLLLLLLLLL.LLLLLL.LLLL.LLLLLLLLL.LLLLLLL..LLLLL.LLLLLLLLLLLLL
LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLLLL.LLLLL.L..LLLLL.LLLLL.LLLLLLL.LLLLL
LLLLLL..LLLLLLL.LLLLL.LLLLLL.LLLL.LLLL.LLL.LLLLLLLLLLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL
LL.LL...L....LLL.L.L....LL.L.....L...LLL..LL.......L.......L.......L..L......LLL..L.LL..LL..L
LLLL.LL.LLLLL.L.LLLLLLLLLLLL.LLLL..LLLLLLL.LLLLLL.LLLL.LLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLL.LLLLLL.LL.LLLLL.LLLLLLLLLLLLLLLL.LLLLLLL.L.LLLLLLLLLLLLLL.LLLLLLLL.LLLL
LLLLL.L.LLLLLLL.LLLLL.LLLLLLLLLLL.LLLLLLLL.LLLLL..LLLL.LLLLLLLLL.LLLLLLLL.LLLLLLLLLLLLL.LLLLL
LLLLLLL.LLLLLLLLLLLLLLLLLLLLL.L.LLLLLLLLLL.LLLLLL.LLLL.LLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLL
L.LLLLLLLLLLLLL..LLLLLLLLLLL..LLL.LLLLLLLL.LLLLL...LLL.LLLLLLLLL.LLLLLLLLLLL.LL.LLLLLLLLLLLLL
.L......LL...L.L....L...L...........L.LL...L.LLLLL.....LL....L......L.LL..L..L.....L...L.L.LL
LLLLLLL.LLLLLLLLLLLLLLLLLLLL.LLLL.LLLL.LLL.LLLLLL.LLL..LLLLLLLLL.LLLLLLLLLLLLLL..LLLLLL.LLLLL
LLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLL.LLLL.LLLLLLLLLL.LLLLL.LLLLLLLL.LLLLL.LLLLL.L.LLLLL
LLLLLLLLLLLLLLL.LLLLL.LLL.LL.LLLL.LLLLLLLLLLLLLLLLLLLL.LL.LLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL
LLLLLLL.LLLLLLLLLLLLLLLLLLLL.LLLL.LLLLLLLL.L.LLLLL.LLL.LLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL
LL.L.LLLLL.LLLL.LLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLL
LLLL.LLLLLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLL.LLLLLLLLL.L.LLLLLL.LLLLL.LLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLL.LLLLLL.LLLL.LLLLLLLL.LLLLLLLLLLL.LLLLL.LLLLL.LLLLLL.LL.LL.LLLLLLLLLLLLL
..L....L.L.LL.L.........L...LL.L....LL......LL..LL.L.L.....L..L..L..L..LL.L...L..L....L......
LLLLLLL.LLLLLLL.LLLLL.LLLLLL.LLL..LLLLLLLLLLLLLLLLLLLLL.LLL.LLLLLLLLLL.LL.LLLLL.LLLLLLL.LLLLL
LLLLLLL.L.LLLLLLLLLLLLLLLLLLLLLLL.LLLLLLL..LLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLLLL
LLLLLLL.LLLLLLL.LLLLL.L.LLLL.L.LLLLLLLLLLL..LLLLLLLLLL.LL.LLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLL.LLLLLL.LL.LLLLLLLL..L.LL.LLLLLLLLLLLLL
.L......L....L.L.L...LLLL......LL...LL...L...L......L..L...........L......L.......L....L.L...
LL.LLLLLLLLLLLLLLLLLLLLLLLLL.LLLL.LL.LLLLL.LLLLLLLLLLL.LLL.LLLLL.LLLLLLLL.LLLLL.LL.LLLL.LLLLL
L.LLLLL.LLLLLLL.LLLLL.LLLLLL.LL.LLLLLLLLLL.L.LLLLLLLLL.LLLLLLLLL.LLLLLLLL.LLLLLLL.LLLLLLLLLLL
LLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLL.LLLLL.LLLLLLLL.LLLLLLLLLLLLLLL.LLL.LLLL.LLLLLLLLLLLLL.LLLLL
LLLLLLLLLLLLLLLLL.LLLLLLLLLL.LLLL.LLLLLLLLLLLLLLL.L.LLLLLLLLLLLL.LLLLL.LLLLLLLL.LLLLLLL.LLLLL
.LLLLLL.LLLLLLL.LLLLLLLLLLLL.LLLL.LLLLLLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLLL.LLLLL.L.LLLLL.LLLLL
LLLLLLL.LLLLLLLLLLLLLLLLLL.L.LLLL.LLLLLLLLLLL.LLL.LLLL.LLL.LLLLL.LLL.LLLLLLLLLL.LLLLLLL..LLLL
.L.....L...L....L.LL............LL..L.LL.....LLL..L.............L...........L...L.L.L........
LLLLLLLLLLLLL.L.LLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLL.LLLL.LLLLLLLLL.LLL.LLLL.LLLLLLLLLLLLL.LLLLL
LLLLLLL..LLLLLL.LLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLL.LLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLL
LL.LLLLLLLLLLLL.LLLLL.LLL.LL.LLL..LLLLLLLL.L.LLLL.LLLLLLLLLLLLLL.LLLLLL.L.LLLLLLLLLLLL.L.LLLL
LLL.LLL.LLLLLLLLLLLL..LLLLLL.LLLL.LLLLLLLLLLLL.LLLLLLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLL.LLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLLLLLLLLLLLLLLLLLLL.L.LLLLL.LLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLLLLLLLLL.LLLL.LL.L.LLLLLLLLLL.LLLL.LLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLLLLL
LLLLLLLLLLLLLLLLLLLLL.LLLLLL.LLLLLLLLLLLLL..LLLL..LLLLLLLLLLLLLL.LLLLLLLLLLLLLLLLLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLL.LLLLLLLLLLL.LLLLLLLL.LLLLLL.LLLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLL.LL.LL
.LLLLLL.LL.LLLLLLLLLLLLLL.LLLLLLLLLLLLLLLL.LLLLLL.LLLLLLLLLLLLLL.LLLLLLLLLL.LLL.LLLLLLL.LLLLL
LL.L.L...L...L...LLL.......LLL..L.L...L.......L......L.LL.......L..LLL.L..L.L.LL..L..L.L.LLL.
LLLLLLL.LLLLLL..LLLLL.LLLLLL.LLLL.LLLLLLLL.LLLLLL.LLLL.LLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLL.LLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLL.LLLLLLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLL
LLLLLLL.LLLLLLL.LLLLLLLLLLLL.LLLL.LLLLLLLL.LLLLLL.LLLL.LLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLL.LLLL
LLLLLLLLLLLLLLL.LL.LL.LLLLLL.LLLL.LLLLLLLL.LLLLLLLLLLL.LLLL.LLLL.LLLLLLLL.LLLLLLLLLLLLLLLLLLL
LLLLLLL.LL.LLLL..LLL.LLLLLLLL.L.L.LLLLLLLL.LLLLLL.L.LL.LLLLLL.LL.LLLLLLLL.LLLLL.LLLLLLL.LLLLL
LLLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLL.LLLLLLLL.LLLLLLLLLLL.LLLLLLLLL.LLLLL.LL.LLLLLLLLL.LLL.LLLL.
L.LLLLLLLLLLLLLLLLLLL.LLLL.L.LLLL.L.LLLL.L.LLLLLL.LLLL.LLLLLL.L.LLLLLLLLLLLLLLLLLLLLLLL.LL.LL
.LLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLL.LLLL.LLL.LLLLLLLLLLL.LLLLLL.LLLLLLLLLLLLLLLLL.LLLLL.L.LLLLL
LL....L....L..L.L.....L.L...L...L.....L.....L....LLL..L.L..L..L.LL.L...L.LLL.......L....L.LL.
LLLLLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLLLLLLL.LLL.LLLLLLLLLLLLLL.LLLLL.LLLLLLL.LLLLL
LLLLLLL.LLL.LLLLLLL.LLLL.LLL.LLLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLL.LLLLLLLL.L..LLLLLLLLLL.LLLLL
LLLLLLLLLLLLLLL.LLLLL.LLLLLLLLLLL.LLLLLLLL.LLLLLLLLLLL.LLLLLLLLL.L.LLL.LLLLLLLL.LLLLLLL.LLLLL
LLLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLLL.LLLLLLL.LLLLLL.LLLL.LLLLLL.LLLLLLLLLLL.LLLLL.LLLLLLLLLLLLL
LLLL.LL.LLLLLLLLLLLLL.LLLLLL.LLLL.LLLLLLLL.LLLLLLLLLLL.LLLLLLL.L.LLLLLLLL.LLLLL.LLLLLLL.LLLLL
LLLLLLL.LLLLLL.LLLLLL.LLLLLLLLLL..LLLLLLLL.LLLLLL.LLLL.LLL.LLLLL.LLLLLLLLLLLLLL.LLL.LLL.LLLLL
LLLLLLLLLLLLLLL..LLLLLLLLLLLLLLLLLLLL..LLL.LLLLLL.LL.L.LLL.LLLLLLLLL..LLL.LLLLL.LLLLLLL.LLLLL
..L..L..L.L.......L..LL...L.L..LL...L............L.L...L.....L...LL..LL......L.L...L.....L..L
LLLLL.LLLLLLLLLLLLLLL.LLLLLL.LLLL.LL.LLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL
L.LLLLL.LLLLLLL.LLLLLLL.LLLL.LLLL.LLLLLLLLLLLLLLL.LLLLLLLLLLLLLL.LLLLLLLL.L.LLL.LL.LLL.LLLLLL
LLLLLLL.LLLLLLLLL.LLLLLLLLLLL.L.L.LLLLLLLL.LLLLLL.LLLL.LLLLLLLLLLLLLLLLLL.L.LLL.LLL.LL..LLLLL
LLLLLLL.LLLLLLL.LLLLLLLLLLLL.LLLLLLLLLLLLL.LLLLLL.LLLL.LLLL.LLLL.LLLLLLLL.LLLLL.LLL..LL.LLLLL
LLLLLLL.LLLLLLL.LLLLLLLLLLLL.LLLL.LLLLLLLL.LLLL.LLLLLL.LLLLLLLLLLLLLLLLLLLLLLLL.LLLLLLLLLL.LL
LLLLLL.LLLLLLLL.LLL...LLLLLL.LLLL.LLLLLLLL.LLLLLL.LLLLLLLLLL.L.L.LLLLLLLL.LLLLL.LLLLLLL.L.LL.
LL.LL.L.LLLLLLLLLLLLL.L.LLLLLLLLLLLLLLLLLL.LLLLLL..LLL.LLLLLLLLLLLLLLLLL..LLLLL.LLLLLLL.LLLLL
LLLLLLLLLLLLLLL.LLL.LL.LLLLL.LLLL.LLLLLLLL.LLLLLLLLLLL.LLLLLLLLL.LLLLLLLLL.LL.L.LLLLLLLLLLLLL
LLLLLLL.LLLL.LL.LLLLL.LLLLLL.LLLL.L.LLLLLLLLLLLLLLLLLLLLLLLLLLL..LLLLLLLLL.LLLLLLLLLLLL.LLLLL
L.LLLLL.LLLLLLL.LLLLL.LLLLLLLLLLL.LLLLLLLL.LLLLLL.LLLL.LLLLLLLLLLLLLLLL.L.LLLLLLLLLLLLL..LLLL
LLLLLLL.LLLLLLLL.LLLLLLLLLLL.LLLLLLLLL.LLL.LLLLLLLLLL..LL.LLLLLL.LLLLLLLL.LLLLL.LLLLLLLLLLLLL'''

from functools import lru_cache
import itertools

def point_add(a, b):
    return (a[0] + b[0], a[1] + b[1])

directions = set(itertools.product(range(-1, 2), repeat=2))
directions.remove((0, 0))

@lru_cache(maxsize=None)
def neighbors(position):
    return {point_add(position, direction) for direction in directions}

@lru_cache(maxsize=None)
def visible_seats(start_position):
    positions = set()
    for direction in directions:
        position = point_add(start_position, direction)
        while initial_layout.get(position, 'L') not in '#L':
            position = point_add(position, direction)
        positions.add(position)
    return positions

def iterate(space, relevant_occupants, part2=False):
    if space == 'L' and not relevant_occupants:
        new_space = '#'
    elif space == '#' and relevant_occupants >= 4 + part2:
        new_space = 'L'
    else:
        new_space = space
    return new_space

rows = initial.splitlines()
initial_layout = {}
for y, row in enumerate(rows):
    for x, space in enumerate(row):
        initial_layout[(y, x)] = space
layout = initial_layout
layouts = []
while layout not in layouts:
    layouts.append(layout)
    new_layout = {}
    for position, space in layout.items():
        #relevant_occupants = sum(layout.get(neighbor, '.') == '#' for neighbor in neighbors(position))
        relevant_occupants = sum(layout.get(visible_seat, '.') == '#' for visible_seat in visible_seats(position))
        new_layout[position] = iterate(space, relevant_occupants, part2=True)
    layout = new_layout
print(sum(1 for space in layout.values() if space == '#'))
