156 lines
3 KiB
Python
156 lines
3 KiB
Python
import copy
|
|
from pprint import pprint
|
|
|
|
|
|
class PuzzleSolver:
|
|
def __init__(self, filename):
|
|
self.load(filename)
|
|
|
|
def load(self, filename):
|
|
with open(filename, "r", encoding="utf-8") as f:
|
|
self.data = [list(x.rstrip()) for x in f.readlines()]
|
|
self.width = len(self.data[0])
|
|
self.height = len(self.data)
|
|
|
|
def occupied_adjacent(self, x, y):
|
|
n = 0
|
|
for j in range(y-1, y+2):
|
|
for i in range(x-1, x+2):
|
|
if (i, j) == (x, y):
|
|
continue
|
|
if not (0 <= i < self.width):
|
|
continue
|
|
if not (0 <= j < self.height):
|
|
continue
|
|
|
|
s = self.get(i, j)
|
|
if s == "#":
|
|
n += 1
|
|
|
|
return n
|
|
|
|
def occupied_in_sight(self, ix, iy):
|
|
directions = [( 1, -1), ( 1, 0), ( 1, 1), ( 0, 1), (-1, 1), (-1, 0), (-1, -1), ( 0, -1)]
|
|
n = 0
|
|
for dx, dy in directions:
|
|
x, y = ix, iy
|
|
x += dx
|
|
y += dy
|
|
while 0 <= y < self.height and 0 <= x < self.width:
|
|
s = self.get(x, y)
|
|
if s == "#":
|
|
n += 1
|
|
break
|
|
if s == "L":
|
|
break
|
|
x += dx
|
|
y += dy
|
|
|
|
return n
|
|
|
|
def get(self, x, y):
|
|
return self.data[y][x]
|
|
|
|
def mutate(self):
|
|
ret = copy.deepcopy(self.data)
|
|
for y in range(self.height):
|
|
for x in range(self.width):
|
|
s = self.get(x, y)
|
|
if s == ".":
|
|
continue
|
|
|
|
n = self.occupied_adjacent(x, y)
|
|
if s == "L":
|
|
if n == 0:
|
|
ret[y][x] = "#"
|
|
elif s == "#":
|
|
if n >= 4:
|
|
ret[y][x] = "L"
|
|
|
|
return ret
|
|
|
|
def mutate_in_sight(self):
|
|
ret = copy.deepcopy(self.data)
|
|
for y in range(self.height):
|
|
for x in range(self.width):
|
|
s = self.get(x, y)
|
|
if s == ".":
|
|
continue
|
|
|
|
n = self.occupied_in_sight(x, y)
|
|
if s == "L":
|
|
if n == 0:
|
|
ret[y][x] = "#"
|
|
elif s == "#":
|
|
if n >= 5:
|
|
ret[y][x] = "L"
|
|
|
|
return ret
|
|
|
|
def print(self):
|
|
for y in range(self.height):
|
|
print("".join(self.data[y]))
|
|
print()
|
|
|
|
def solve_in_sight(self):
|
|
stable = False
|
|
rounds = 0
|
|
self.print()
|
|
while not stable:
|
|
x = self.mutate_in_sight()
|
|
stable = x == self.data
|
|
self.data = x
|
|
rounds += 1
|
|
|
|
self.print()
|
|
|
|
return rounds
|
|
|
|
def solve(self):
|
|
stable = False
|
|
rounds = 0
|
|
self.print()
|
|
while not stable:
|
|
x = self.mutate()
|
|
stable = x == self.data
|
|
self.data = x
|
|
rounds += 1
|
|
|
|
self.print()
|
|
|
|
return rounds
|
|
|
|
def count_occupied(self):
|
|
return sum([x.count("#") for x in self.data])
|
|
|
|
|
|
#ps = PuzzleSolver("test.txt")
|
|
#rounds = ps.solve()
|
|
#cs = PuzzleSolver("test-1.txt")
|
|
#assert ps.data == cs.data
|
|
#
|
|
#ps = PuzzleSolver("data.txt")
|
|
#rounds = ps.solve()
|
|
#n = ps.count_occupied()
|
|
#print(f"There are {n} occupied seats.")
|
|
|
|
ps = PuzzleSolver("test-2.txt")
|
|
assert ps.get(3, 4) == "L"
|
|
assert ps.occupied_in_sight(3, 4) == 8
|
|
|
|
ps = PuzzleSolver("test-3.txt")
|
|
assert ps.get(3, 3) == "L"
|
|
assert ps.occupied_in_sight(3, 3) == 0
|
|
|
|
ps = PuzzleSolver("test-4.txt")
|
|
assert ps.get(1, 1) == "L"
|
|
assert ps.occupied_in_sight(1, 1) == 0
|
|
|
|
ps = PuzzleSolver("test.txt")
|
|
ps.solve_in_sight()
|
|
assert ps.count_occupied() == 26
|
|
|
|
ps = PuzzleSolver("data.txt")
|
|
ps.solve_in_sight()
|
|
n = ps.count_occupied()
|
|
print(f"There are {n} occupied seats.")
|