Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second solution in Clear category for Visibilities by pokosasa
from typing import List, Iterable, Tuple
def visibilities(grid: List[List[int]]) -> Iterable[Tuple[int]]:
H, W = len(grid), len(grid[0])
EMPTY, BLACK, STONE = 0, -1, -2
OUTSIDE = (-1, -1)
DIRS = ((-1, 0), (0, 1), (1, 0), (0, -1))
DIRS2 = ((-1, 1), (1, 1), (1, -1), (-1, -1))
def current_view(pos, cells):
visible, unknown = 1, 0
lines = {dir: 0 for dir in DIRS}
for di, dj in DIRS:
si, sj = pos
is_neighbor = True
while True:
si, sj = si + di, sj + dj
if (si, sj) not in cells or cells[(si, sj)] == BLACK or lines[(di, dj)] > cells[pos]:
break
lines[(di, dj)] += 1
if cells[(si, sj)] != EMPTY and is_neighbor:
visible += 1
continue
unknown += 1
if is_neighbor:
is_neighbor = False
return (visible, unknown, lines)
def check_fill(pos, cells):
num = cells[pos]
visible, unknown, lines = current_view(pos, cells)
if visible + unknown < num or visible > num:
return False
if unknown == 0:
return True
for dir in DIRS:
sum_3ways = sum(lines[dir2] for dir2 in DIRS if dir2 != dir)
if sum_3ways + 1 < num:
if num - sum_3ways - 1 > lines[dir]:
return False
(si, sj), (di, dj) = pos, dir
for _ in range(num - sum_3ways-1):
(si, sj) = (si+di, sj+dj)
if cells[(si, sj)] == EMPTY:
if place_stone((si, sj), cells):
visible += 1
unknown -= 1
continue
return False
if visible == num:
for dir, length in lines.items():
(si, sj), (di, dj) = pos, dir
for _ in range(length):
si, sj = si + di, sj + dj
if cells[(si, sj)] == BLACK:
break
if cells[(si, sj)] == EMPTY:
if place_black((si, sj), cells):
break
return False
return True
return True
def place_stone(pos, cells):
cells[pos] = STONE
return check_lines(pos, cells)
def place_black(pos, cells):
i, j = pos
cells[pos] = BLACK
if separated(pos, cells):
return False
for n_pos in ((i+di, j+dj) for di, dj in DIRS if (i+di, j+dj) in cells):
if cells[n_pos] == EMPTY:
if place_stone(n_pos, cells):
continue
return False
return check_lines(pos, cells)
def check_lines(pos, cells):
i0, j0 = pos
for di, dj in (dir for dir in DIRS):
si, sj = i0, j0
while True:
si, sj = si + di, sj + dj
dist = abs(si-i0)+abs(sj-j0)
if (si, sj) not in cells or cells[(si, sj)] in (BLACK, EMPTY):
break
if (cells[(si, sj)] - 1) + 1 >= dist:
if check_fill((si, sj), cells):
continue
return False
return True
def separated(pos, cells):
i0, j0 = pos
used = {(i0, j0)}
stack = [((i0, j0), used)]
while stack:
(i, j), used = stack.pop()
if len(used) == 3:
used = used-{(i0, j0)}
if len(used) != 1 and (i, j) == (i0, j0):
return True
if (i, j) == OUTSIDE:
for (i1, j1), cell1 in cells.items():
if cell1 == BLACK and (i1 in (0, H - 1) or j1 in (0, W - 1)) and (i1, j1) not in used:
stack.append(((i1, j1), used | {(i1, j1)}))
continue
for di, dj in DIRS2:
ni, nj = i + di, j + dj
if (ni, nj) not in cells:
if OUTSIDE not in used:
stack.append(((-1, -1), used | {OUTSIDE}))
continue
if cells[(ni, nj)] == BLACK and (ni, nj) not in used:
stack.append(((ni, nj), used | {(ni, nj)}))
return False
def method_1(cells):
updated = False
for i, j in sorted(cells, key=lambda x: - (abs(x[0] - H // 2) + abs(x[1] - W // 2))):
if cells[(i, j)] != EMPTY:
continue
if sum(cells[(i+di, j+dj)] != EMPTY for di, dj in DIRS if (i+di, j+dj) in cells) == 0:
continue
test_cells_1 = cells.copy()
if not place_black((i, j), test_cells_1):
place_stone((i, j), cells)
updated = True
continue
test_cells_2 = cells.copy()
if not place_stone((i, j), test_cells_2):
place_black((i, j), cells)
updated = True
continue
return updated
cells = {(i, j): grid[i][j] for i in range(H) for j in range(W)}
while method_1(cells):
pass
res = [pos for pos, cell in cells.items() if cell == BLACK]
return res
July 21, 2020
Comments:
