Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Radiation Search by Moff
class QuickFindUF(object):
def __init__(self):
self.key = dict()
def push(self, p):
if p not in self.key:
self.key[p] = len(self.key) + 1
def connected(self, p, q):
return self.key.get(p) is not None and \
self.key.get(q) is not None and \
self.key.get(p) == self.key.get(q)
def union(self, p, q):
self.push(p)
self.push(q)
if self.connected(p, q):
return
pkey = self.key[p]
for node, key in self.key.items():
if key == pkey:
self.key[node] = self.key[q]
@property
def keys(self):
return set(self.key.values())
@property
def unions(self):
return {k: [p for p, v in self.key.items() if v == k] for k in self.keys}
def checkio(field):
delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]
uf = QuickFindUF()
for i, row in enumerate(field):
for j, n in enumerate(row):
for ci, cj in ((i + di, j + dj) for di, dj in delta):
if 0 <= ci < len(field) and 0 <= cj < len(row) \
and field[i][j] == field[ci][cj]:
uf.union((i, j), (ci, cj))
max_union = max(uf.unions.values(), key=lambda x: len(x))
row, col = max_union[0]
return [len(max_union), field[row][col]]
Aug. 12, 2015
