Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Disjoint Set solution in Clear category for Calculate Islands by PositronicLlama
"""
Determine the size of each island in an archipelago.
"""
import itertools
class DisjointSet:
"""
The disjoint set data structure.
"""
def __init__(self):
self._nodes = {}
def add(self, item):
"""Add an item to this set."""
if item not in self._nodes:
self._nodes[item] = DisjointSetNode()
def find(self, item):
"""
Return the canonical set node for the given item.
Raise KeyError if item is not in this set.
"""
return self._nodes[item].find()
def merge(self, a, b):
"""
Merge together a and b, and return the merged node.
"""
node_a = self.find(a)
node_b = self.find(b)
node_a.merge(node_b)
return node_a.find()
class DisjointSetNode:
"""
One node in a disjoint set data structure.
"""
def __init__(self):
self.parent = self
self.rank = 0
def find(self):
"""Find the canonical (root) element that represents this set."""
if self.parent is not self:
self.parent = self.parent.find()
return self.parent
def merge(self, other):
"""
Merge together self and other.
"""
# This is more commonly called the 'Union' operation, but since it
# has side effects, I prefer to name it with a verb.
root = self.find()
other_root = other.find()
if root is other_root:
# Both items are already in the same set
return
if root.rank < other_root.rank:
root.parent = other_root
elif root.rank > other_root.rank:
other_root.parent = root
else:
other_root.parent = root
root.rank += 1
# Orthogonal and diagonally adjacent tiles.
ADJACENT = [(1, 0), (0, 1), (1, 1), (1, -1)]
def checkio(data):
"""Return a list of the size of each island in ascending order."""
tiles = []
ds = DisjointSet()
height, width = len(data), len(data[0])
for x, y in itertools.product(range(width), range(height)):
if data[y][x]:
ds.add((x, y))
tile = ds.find((x, y))
tile.size = 1
tiles.append(tile)
for x, y in itertools.product(range(width), range(height)):
if not data[y][x]:
continue
ta = ds.find((x, y))
for dx, dy in ADJACENT:
nx, ny = x + dx, y + dy
if 0 <= nx < width and 0 <= ny < height:
if not data[ny][nx]:
continue
tb = ds.find((nx, ny))
if ta is not tb:
size = ta.size + tb.size
ta.merge(tb)
ta.find().size = size
islands = [tile.size for tile in tiles if tile.find() is tile]
return list(sorted(islands))
if __name__ == '__main__':
assert checkio([[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0]]) == [1, 3], "1st example"
assert checkio([[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 0, 0]]) == [5], "2nd example"
assert checkio([[0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0]]) == [2, 3, 3, 4], "3rd example"
June 23, 2013
Comments: