Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Bacteria Colonies by Rounin
def getNeighbours(grid, y, x):
neighbours = []
for neighboury in range(max(y-1, 0), min(y+2, len(grid))):
for neighbourx in range(max(x-1, 0), min(x+2, len(grid[neighboury]))):
if((y==neighboury) == (x==neighbourx)):
continue # Filter start itself and diagonals
neighbours.append([neighboury,neighbourx])
return neighbours
def segment(grid, y=0, x=0, blobs={}, visited=set()):
if grid[y][x] == 0 or str([y,x]) in visited:
return blobs
this = str([y,x])
visited.add(this)
if not this in blobs:
blobs[this] = this
for neighbour in getNeighbours(grid, y, x):
if not str(neighbour) in blobs and grid[neighbour[0]][neighbour[1]] == 1:
blobs[str(neighbour)] = blobs[this]
segment(grid, neighbour[0], neighbour[1], blobs, visited)
return blobs
def invert(dictionary):
out = {}
for key, value in dictionary.items():
if not value in out:
out[value] = []
out[value].append(eval(key))
return out
def getcoords(colony):
colony = sorted(colony)
top = colony[0][0]
bottom = colony[len(colony)-1][0]
colony = sorted(colony, key=lambda c: c[1])
left = colony[0][1]
right = colony[len(colony)-1][1]
centerpoint = [(top+bottom)/2.0, (left+right)/2.0]
size=(abs(bottom-top))//2
if int(centerpoint[0]) != centerpoint[0] or int(centerpoint[1]) != centerpoint[1] or abs(bottom-top) != abs(right-left):
return [0, 0, 0, 0, [0, 0], 0]
return [min(top, bottom), max(top, bottom), min(left, right), max(left, right), [int(centerpoint[0]), int(centerpoint[1])], size]
def grow(grid, y, x, size):
grid[y][x] = 1
if(size <= 0):
return
for neighbour in getNeighbours(grid, y, x):
grow(grid, neighbour[0], neighbour[1], size-1)
def healthy(grid):
colonies = {}
visited = set()
for row in range(len(grid)):
for col in range(len(grid[row])):
segment(grid, row, col, colonies, visited)
colonies = invert(colonies)
maxHealthy = -1
healthyCoords = [0,0]
for colony in colonies.values():
coords = getcoords(colony)
centerpoint = coords[4]
size = coords[5]
copygrid = eval(str(len(grid)*[len(grid[0])*[0]]))
grow(copygrid, centerpoint[0], centerpoint[1], size)
copycolony = []
for row in range(len(copygrid)):
for col in range(len(copygrid[row])):
if copygrid[row][col] == 1:
copycolony.append([row, col])
if(str(sorted(colony)) == str(sorted(copycolony))) and size > maxHealthy:
maxHealthy = size
healthyCoords = centerpoint
return healthyCoords
if __name__ == '__main__':
# These "asserts" using only for self-checking and not necessary for auto-testing
def check(result, answers):
return list(result) in answers
check(healthy(((0, 1, 0),
(1, 1, 1),
(0, 1, 0),)), [[1, 1]])
check(healthy(((0, 0, 1, 0, 0),
(0, 1, 1, 1, 0),
(0, 0, 1, 0, 0),
(0, 0, 0, 0, 0),
(0, 0, 1, 0, 0),)), [[1, 2]])
check(healthy(((0, 0, 1, 0, 0),
(0, 1, 1, 1, 0),
(0, 0, 1, 0, 0),
(0, 0, 1, 0, 0),
(0, 0, 1, 0, 0),)), [[0, 0]])
check(healthy(((0, 0, 0, 0, 0, 0, 1, 0),
(0, 0, 1, 0, 0, 1, 1, 1),
(0, 1, 1, 1, 0, 0, 1, 0),
(1, 1, 1, 1, 1, 0, 0, 0),
(0, 1, 1, 1, 0, 0, 1, 0),
(0, 0, 1, 0, 0, 1, 1, 1),
(0, 0, 0, 0, 0, 0, 1, 0),)), [[3, 2]])
check(healthy(((0, 0, 0, 0, 0, 0, 2, 0),
(0, 0, 0, 2, 2, 2, 2, 2),
(0, 0, 1, 0, 0, 0, 2, 0),
(0, 1, 1, 1, 0, 0, 2, 0),
(1, 1, 1, 1, 1, 0, 2, 0),
(0, 1, 1, 1, 0, 0, 2, 0),
(0, 0, 1, 0, 0, 0, 2, 0),
(0, 0, 0, 1, 0, 0, 2, 0),
(0, 0, 1, 1, 1, 0, 2, 0),
(0, 1, 1, 1, 1, 1, 0, 0),
(0, 0, 1, 1, 1, 0, 0, 0),
(0, 0, 0, 1, 0, 0, 0, 0),)), [[4, 2], [9, 3]])
Oct. 14, 2017