Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
48-liner: Generate connections & start path-finding solution in Clear category for Triangular Islands by Stensen
from typing import Set, Iterable
# Generate the appropriate number of stacks
def num_of_stacks(maxi):
n_stacks, sum_of_stacks = 2, 1
while maxi > sum_of_stacks:
n_stacks += 2
sum_of_stacks += list(range(3, 20, 2))[n_stacks//2-2]
return n_stacks
# Generate the befitting triangular connections
def connections(n_stacks):
conn = {1: (3,)}
j = 1 # j is the land_number counter
for length in range(3, n_stacks, 2):
for i in range(length):
j += 1 # Increse the land_number
# Neighbors for the start land_number of each island stack (0-index)
if not i:
conn.update({j: (j+1, j+length+1)}); continue
# Neighbors for the last land_number of each island stack (-1-index)
if i == length - 1:
conn.update({j: (j-1, j+length+1)}); continue
# Neighbors for the UP-Triangle land_number of each island stack (even index)
if not i % 2:
conn.update({j: (j-1, j+1, j+length+1)}); continue
# Neighbors for the DOWN-Triangle land_number of each island stack (odd index)
if i % 2:
conn.update({j: (j-length+1, j-1, j+1)}); continue
return conn
def triangular_islands(triangles: Set[int]) -> Iterable[int]:
conn = connections(num_of_stacks(max(triangles)))
visited = set()
answer = []
for island in triangles:
if island in visited: continue
neighbr = [island]
count = 0
while neighbr:
fore = neighbr.pop(0)
for i in conn[fore]:
if i in triangles and i not in visited:
neighbr.append(i)
visited.add(i)
count += 1
answer.append(count if count else 1)
return answer
Dec. 8, 2020
