Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
sane coordinate system solution in Clear category for Triangular Islands by Leonix
def triangular_islands(land):
""" Loop over non-empty triangles of the field, top to bottom, left to right.
Maintain list of continuous areas processed so far. Merge areas together
when current triangle is adjacent to more than one.
"""
areas = []
for x, y, neighbours in coordinates(land):
areas, old_areas = [{(x, y)}], areas
for area in old_areas:
if area & neighbours:
areas[0] |= area
else:
areas.append(area)
return [len(area) for area in areas]
def coordinates(land):
""" Convert triangle coordinates to (x,y) and figure out its neighbours.
Only neighbours above and to the left are considered.
First row is (1,1). Second row is (1,2),(2,2),(3,2).
Third row is x=1..5, y=3. Etc.
"""
max_x = x = y = i = 1
for n in sorted(land):
# figure out (x, y) coordinate of triangle number n
while i < n:
i += 1
if x < max_x:
x += 1
else:
max_x += 2
y += 1
x = 1
# figure out neighbours above and to the left, if present
neighbours = set()
if y > 1 and x % 2 == 0:
neighbours.add((x-1, y-1)) # triangle above
if x > 1:
neighbours.add((x-1, y)) # to the left
yield x, y, neighbours
July 14, 2020
Comments: