Count Islands

count_islands.py

#!/usr/bin/env python3

# Given a 2D grid map of 1s (land) and 0s (water), count the number of islands.
# An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
# You may assume the grid itself is surrounded by water.
# https://www.geeksforgeeks.org/find-number-of-islands/
# https://www.geeksforgeeks.org/find-the-number-of-distinct-islands-in-a-2d-matrix/
# https://stackoverflow.com/questions/58767533/find-explicitly-islands-in-matrix
# http://www.huristic.co/blog/2016/10/14/finding-islands-in-an-adjacency-matrix

def count_islands(grids):
    coordinates = get_island_coordinates(grids)
    islands = group_island_coordinates(coordinates)
    print(len(islands))
    print(islands)
    return len(islands)

def get_island_coordinates(grids):
    coordinates = []
    for index, grid in enumerate(grids):
        coordinates += [(i, index) for (i, x) in enumerate(grid) if x == 1]
    return coordinates

def group_island_coordinates(coordinates):
    islands = []
    if coordinates:
        islands.append([coordinates[0]])
    for index, coordinate in enumerate(coordinates[1:]):
        is_part_of_island_index = -1
        for island_index, island in enumerate(islands):
            if is_coordinate_part_of_island(island, coordinate):
                is_part_of_island_index = island_index
        if is_part_of_island_index > -1:
            islands[is_part_of_island_index].append(coordinate)
        else:
            islands.append([coordinate])
    return islands

def is_coordinate_part_of_island(island, coordinate):
    for index, island_coordinate in enumerate(island):
        if island_coordinate[1] == coordinate[1] and island_coordinate[0] == coordinate[0] - 1: # matching y
            return True
        if island_coordinate[0] == coordinate[0] and island_coordinate[1] == coordinate[1] - 1: # matching x
            return True
    return False

grid1 = [
    [0, 0, 0, 1, 1, 0, 0, 1, 0, 0],
    [1, 1, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 1, 0, 0, 1, 0, 0, 1, 1, 1],
    [0, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
]

# [
#     [(3, 0), (4, 0), (4, 1), (4, 2)],
#     [(7, 0)],
#     [(0, 1), (1, 1), (0, 2), (1, 2)],
#     [(9, 1)],
#     [(7, 2), (8, 2), (9, 2), (9, 3), (9, 4)],
#     [(3, 3), (4, 3)],
#     [(0, 5), (1, 5), (2, 5), (3, 5)]
# ]

grid2 = [
    [0, 0, 0, 1, 1],
    [0, 1, 1, 1, 1],
    [1, 0, 1, 0, 0],
    [0, 0, 0, 1, 0]
]

grid3 = [
    [0, 1],
    [1, 0]
]

assert count_islands(grid1) == 5
# assert count_islands(grid2) == 3
# assert count_islands(grid3) == 2