Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Triangular Islands by U.V
from typing import Set, Iterable
from math import sqrt
def triangular_islands(triangles: Set[int]) -> Iterable[int]:
nodes = list(triangles)
dnod = {i:set(nb(i)) for i in nodes }
nbs0 = []
N = []
while nodes:
q = [list(nodes)[0]]
visited = set()
while q:
u = q.pop()
visited.add(u)
nxt = dnod[u]
if u in nodes:
nodes.remove(u)
for v in nxt:
if v in dnod and v in nodes :
q.append(v)
N.append(len(visited))
return N
# index to triangle
def i2tri(n):
i = n - 1
r = int(sqrt(i))
ix = i - r * r
up = (i - r) % 2
return r, ix, up # r - row , ix - index in row from left, up - orientation 1/0- neibth up /down
#triangle to index
def tri2i(r, ix, up=None):
i = r * r + ix
return i + 1
# neibs jf i
def nb(i):
nbs = []
r, ix, up = (i2tri(i))
#left NB
if ix > 0:
#print('L', end=' ')
nbs.append(i-1)
#right NB
r1,ix1,up1 = i2tri(i+1)
if r1 == r:
#print('R', end=' ')
nbs.append(i+1)
if up: # up NB
if r > 0 :
#print('U', end=' ')
nbs.append(tri2i(r-1, ix-1))
else: #down NB
#print('D', end=' ')
nbs.append(tri2i(r+1, ix+1))
return nbs
Aug. 30, 2022