93 lines
2.1 KiB
Python
93 lines
2.1 KiB
Python
from collections import Counter
|
|
pos = {}
|
|
y = 0
|
|
for line in open("input"):
|
|
for x, c in enumerate(line):
|
|
if c == '#':
|
|
pos[x,y] = 1
|
|
y += 1
|
|
|
|
|
|
def choices(pos, dir):
|
|
x,y = pos
|
|
dy = (dir == 'S') - (dir == 'N')
|
|
dx = (dir == 'E') - (dir == 'W')
|
|
if dx:
|
|
for dy in -1,0,+1:
|
|
yield x+dx,y+dy
|
|
else:
|
|
assert dy
|
|
for dx in -1,0,+1:
|
|
yield x+dx, y+dy
|
|
|
|
def go(pos, dir):
|
|
x,y = pos
|
|
dy = (dir == 'S') - (dir == 'N')
|
|
dx = (dir == 'E') - (dir == 'W')
|
|
return x+dx,y+dy
|
|
|
|
def neighbors(pos):
|
|
x,y = pos
|
|
for dx in -1,0,+1:
|
|
for dy in -1,0,+1:
|
|
if dx or dy:
|
|
yield x+dx,y+dy
|
|
|
|
def migrate(start, rounds):
|
|
moves = ['N', 'S', 'W', 'E']
|
|
for i in range(rounds):
|
|
#show(start)
|
|
#print("-")
|
|
propose = {}
|
|
destCount = Counter()
|
|
|
|
for p in start:
|
|
propose[p] = p
|
|
if any(n in start for n in neighbors(p)):
|
|
for m in moves:
|
|
if not any(c in start for c in choices(p, m)):
|
|
c = go(p,m)
|
|
propose[p] = c
|
|
destCount[c] += 1
|
|
break
|
|
|
|
next = {}
|
|
moved = 0
|
|
for p, d in propose.items():
|
|
if destCount[d] <= 1:
|
|
next[d] = 1
|
|
moved += p != d
|
|
else:
|
|
next[p] = 1
|
|
|
|
if not moved:
|
|
break
|
|
|
|
moves.append(moves.pop(0))
|
|
start = next
|
|
return start, i+1
|
|
|
|
def show(pos):
|
|
xmin = min(x for x,y in pos)
|
|
ymin = min(y for x,y in pos)
|
|
xmax = max(x for x,y in pos)
|
|
ymax = max(y for x,y in pos)
|
|
for y in range(ymin, ymax+1):
|
|
print("".join(".#"[(x,y) in pos] for x in range(xmin,xmax+1)))
|
|
|
|
def count_empty(pos):
|
|
n = 0
|
|
xmin = min(x for x,y in pos)
|
|
ymin = min(y for x,y in pos)
|
|
xmax = max(x for x,y in pos)
|
|
ymax = max(y for x,y in pos)
|
|
return (ymax-ymin+1)*(xmax-xmin+1) - len(pos)
|
|
|
|
|
|
#print(pos)
|
|
end, _ = migrate(pos, 10)
|
|
print(count_empty(end))
|
|
|
|
_, n = migrate(pos, 100000)
|
|
print(n)
|