Amazon islands interview problem, 1 solution and demo of stack overflow

amazon_islands_search.py

'''
Given a 2d grid map of '1's (land) and '0's (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 all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Output: 1

Example 2:

11000
11000
00100
00011

Output: 3

Observations:

- Diagonals are not considered connected islands for this version of the question
- If grid is all zeros, than islands equals 0
- If grid is all ones, than islands equals 1

- The structure of a 2d grid of 1s and 0s is similar to that of a graph data structure, where nodes of an island are connected to 1 or more other nodes of the same island
- For graphs, we can use Breath-First-Search algorithm to locate all the nodes in an island
- We need an way to keep track of already visited nodes
- Initially looks like 0(n) looks like best case scenerio since at least every node in the 2d matrix has to be visited once
'''
import random


# input_matrix = [[0,0,1,1,0],
#                 [1,0,0,0,1],
#                 [1,1,1,1,1],
#                 [0,0,0,0,0]] # 1

def generate_matrix(size=5):
    # make sure there's a higher porpotion of ones to test call stack limitations
    return [[random.choice([1,0,1,0,1]) for x in range(size)] for y in range(size)]


def pretty_print(matrix):
    print('\n'.join(['\t'.join([str(cell) for cell in row]) for row in matrix]))


# Attempt #1
def locate_islands(input_matrix):
    row, col, islands = 0, 0, 0
    # pretty_print(input_matrix)
    
    for ir, row in enumerate(input_matrix):
        for ic, node in enumerate(row):
            if (node is 1):
                islands = islands + 1
                # print("starting node for BFS: {},{} is {}".format(ir, ic, node))
                bfs(ir, ic)
                
    print("output: ", islands)
            
    

def bfs(ir, ic):
    # search to right, bottom, top, left of node
    if (input_matrix[ir][ic] is not 1):
        return 0

    input_matrix[ir][ic] = 2 # mark already visited with 2
    
    # print("Searching...", ic, ir)
    if (ir+1 < len(input_matrix)) and (input_matrix[ir+1][ic] is 1):
        bfs(ir+1, ic)

    if (ic+1 < len(input_matrix[ir])) and (input_matrix[ir][ic+1] is 1):
        bfs(ir, ic+1)
        
    if (ic-1 > 0) and (input_matrix[ir][ic-1] is 1):
        bfs(ir, ic-1)
        
    if (ir-1 > 0) and (input_matrix[ir-1][ic] is 1):
        bfs(ir-1, ic)
    
    return 0
    
input_matrix = generate_matrix(size=5)
locate_islands(input_matrix)

# increase the size of grid
input_matrix = generate_matrix(size=2000)
# RecursionError: maximum recursion depth exceeded while calling a Python object
print(len(input_matrix)) # stackoverflow error!
locate_islands(input_matrix)