Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
union and find solution in Clear category for Triangular Islands by Sim0000
from typing import Set, Iterable
from math import isqrt, sqrt, ceil
from itertools import combinations
class union_find:
def __init__(self, items):
self.d = {i: {i} for i in items}
def union(self, a, b):
if b in self.d[a]: return
for i in self.d[b]:
self.d[a] |= self.d[i]
self.d[i] = self.d[a]
def find(self, a, b):
return b in self.d[a]
def groups(self):
return set(map(frozenset, self.d.values()))
def triangular_islands(triangles: Set[int]) -> Iterable[int]:
def is_connect(a, b):
a, b = min(a, b), max(a, b)
ay = ceil(sqrt(a))
by = ceil(sqrt(b))
if by == ay and b == a + 1: return True
if by == ay + 1 and a % 2 == ay % 2 and b == a + 2 * ay: return True
return False
uf = union_find(triangles)
for a, b in combinations(triangles, 2):
if is_connect(a, b): uf.union(a, b)
return sorted(map(len, uf.groups()))
if __name__ == '__main__':
print("Example:")
print(sorted(triangular_islands({1})))
# These "asserts" are used for self-checking and not for an auto-testing
assert sorted(triangular_islands({1})) == [1]
assert sorted(triangular_islands({2, 3, 6})) == [3]
assert sorted(triangular_islands({4, 3})) == [2]
assert sorted(triangular_islands({1, 4, 7, 8})) == [1, 3]
assert sorted(triangular_islands({1, 2, 3, 4, 5, 6, 7, 8, 9})) == [9]
assert sorted(triangular_islands({1, 2, 4, 5, 7, 9})) == [1, 1, 1, 1, 1, 1]
print("Coding complete? Click 'Check' to earn cool rewards!")
Aug. 30, 2022