Answer to cassidoo interview question for 4.2.2018: Given a matrix of 0s and 1s, where 0s are bodies of water and 1s are bodies of land, return the number of land masses. Land is connected horizontally and/or vertically.

ClusterDetection.py

# Performs a breadth first search from a point,
# continuing until all connected values are set to 0.
# Ignores diagonals
def bfs(m, x, y):
    m[x][y] = 0
    maxX = len(m) - 1
    maxY = len(m[x]) - 1
    for delta in range(-1,2):
        if (checkBfsPoint(m, x + delta, y)):
            bfs(m, x + delta, y)

        if (checkBfsPoint(m, x, y + delta)):
            bfs(m, x, y + delta)

# Checks that the x,y pairing is valid
# for 2d array m, and the value
# is 1
def checkBfsPoint(m, x, y):
    maxX = len(m) - 1

    inBounds = x >= 0 and x <= maxX

    if not inBounds:
        return False

    maxY = len(m[x]) - 1
    inBounds = y >= 0 and y <= maxY
    if not inBounds:
        return False

    return isCluster(m[x][y])

# Defines the condition for a value being
# considered part of a cluster
def isCluster(value):
    return value == 1

# Counds clusters in a 2d matrix 
# Any value that is 1 is considered part of a cluster,
# other values are not.
#
# Note: This assumes that duplicate visiting inside a matrix
# is cheaper than allocating values to keep track of visited values.
# This will double search nodes that are part of a cluster
def countClusters(m):
    count = 0
    for x in range(len(m)):
        for y in range(len(m[x])):
            if isCluster(m[x][y]):
                count = count + 1
                bfs(m, x, y)

    return count


matrix = [
    [0, 1, 1, 1],
    [0, 0, 0, 1],
    [1, 0, 1, 0],
    [0, 0, 1, 1]
    ]

print("Searching through matrix:\n%s" % matrix)
print("Found %i bodies of land" % countClusters(matrix))
        

Hi!

It seems that you cannot ignore values from the left and up as assumed in your gist: This fails for the following matrices:

matrix = [    # countClusters(matrix) evaluates to 4
    [0, 1, 1, 1],
    [0, 0, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1]    # leftmost 1 on this line will be counted as separate cluster
]

matrix = [    # countClusters(matrix) evaluates to 3
    [0, 1, 1, 1],
    [0, 0, 0, 0],
    [0, 1, 0, 1],    # last 1 on this line will be counted as separate cluster
    [0, 1, 1, 1]
]

I tested the two matrices here: https://repl.it/repls/PresentRaggedActivemovie

Thanks for testing! I updated to include the correct search; no shortcuts this time :)