Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Calculate Islands by Kurush
from collections import deque
def checkio(land_map):
islands = []
i_dim = len(land_map) - 1
j_dim = len(land_map[0]) - 1
visited = [[False for j in range(j_dim + 1)] for i in range(i_dim + 1)]
for i in range(i_dim + 1):
for j in range(j_dim + 1):
if (land_map[i][j] == 1) and visited[i][j] == False:
islands.append(find_size(i, j, i_dim, j_dim, visited, land_map))
return sorted(islands)
def find_size(i, j, i_dim, j_dim, visited, land_map):
size = 0
search_queue = deque()
search_queue.append([i, j]);
while True:
if not search_queue: break
height_index, width_index = search_queue.popleft()
if land_map[height_index][width_index] == 1:
if visited[height_index][width_index] == False:
size += 1
visited[height_index][width_index] = True
move_shifts = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
possible_moves = [(height_index + shift[0], width_index + shift[1]) for shift in move_shifts]
for new_height_index, new_width_index in possible_moves:
if (is_correct_cell(new_height_index, new_width_index, i_dim, j_dim) and
(land_map[new_height_index][new_width_index] == 1) and
(visited[new_height_index][new_width_index] == False)):
search_queue.append([new_height_index, new_width_index]);
return size
def is_correct_cell(i, j, i_dim, j_dim):
if i < 0 or i > i_dim: return False
if j < 0 or j > j_dim: return False
return True
#These "asserts" using only for self-checking and not necessary for auto-testing
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 22, 2014
