Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS with neighbors function; math.isqrt solution in Clear category for Triangular Islands by Phil15
import math
from typing import Set, Iterable
def is_square(n: int) -> bool: return math.isqrt(n) ** 2 == n
def neighbors(n: int) -> Iterable[int]:
# Right neighbor.
if not is_square(n):
yield n + 1
# Left neighbor.
if not is_square(n - 1):
yield n - 1
# We are at (row, col). Up/down neighbor at (row + shift, col + shift).
row = math.isqrt(n - 1)
col = n - 1 - row ** 2
shift = (1, -1)[col % 2] # Down if col is even, up otherwise.
yield 1 + (row + shift) ** 2 + col + shift
def triangular_islands(triangles: Set[int]) -> Iterable[int]:
while triangles: # DFS
stack, island = [triangles.pop()], set()
while stack:
new = stack.pop()
if new not in island:
island.add(new)
triangles.discard(new)
stack.extend(set(neighbors(new)) & triangles - island)
yield len(island)
July 12, 2020
Comments:
