islands_in_matrix.py

#Sample input:
# A=[[0,1,0,0,1],[0,1,0,1,1],[1,0,0,1,1],[0,1,1,0,0],[1,1,0,0,0]]
# Find the number of "islands" in the matrix

#I will find the "chains" = strings of ones, then I will label them all with a different label. 
# I will next iterate over the labeled chains, and if two of them should be in one island, I will re-asign the smaller of the two labels to the both of them.
#I will count the number of different labels in the end to get the number of islands

#To get the number of islands run reassign_labels_and_find_number_of_islands(A)

def chains(row):
    ' Finds all the chains for a row and returns the sets of indices that are in the chains'
    c=[]
    chain_of_ones=set()
    if row[0]==1:
        chain_of_ones.add(0)
    l=len(row)
    for i in range(1,l):
        if row[i-1]==1 and row[i]==1:
            chain_of_ones.add(i)
        if row[i-1]==1 and row[i]==0:
            c.append(chain_of_ones)
            chain_of_ones=set()
        if row[i-1]==0 and row[i]==1:
            chain_of_ones.add(i)
        if  row[i]==1 and i==l-1:
            c.append(chain_of_ones)
    return(c)

def assign_different_labels(B):
    'For an array finds all chains, and creates a dictionary by assigning different key to each chain. We also add a label=key, and record the row from where each chain came from'
    n=len(B[0])
    l=1
    labeled_chains = {}
    for i in range(n):
        chains_of_row=chains(B[i])
        num_chains=len(chains_of_row)
        if num_chains!=0:
            for j in range(num_chains):
                labeled_chains[l]=[l,i,chains_of_row[j]]
                l = l + 1
    return (labeled_chains, l-1)

def reassign_labels_and_find_number_of_islands(B):
    'We re-label all chains sharing a side by assigning to them the same label (smallest of the two)'
    C=assign_different_labels(B)[0]
    l=assign_different_labels(B)[1]
    for i in range(1,l+1):
        for j in range(i,l+1):
            if C[i][1] + 1 == (C[j][1]):
                if C[i][2] & (C[j][2]) and C[i][0] != C[j][0]:
                    print "Running " + str(C[i]) + "and" + str(C[j])
                    L = min(C[i][0], C[j][0])
                    print "L = "+str(L)
                    C[i][0] = L
                    C[j][0] = L
    label_set=[]
    for i in range(1, l + 1):
        label_set.append(C[i][0])
    S=len(set(label_set))
    print "The number of islands is "+str(S)
    return (C, S)