Counting Islands In Matrix Of Boolean

Question

Code objective: Read a txt file, parse it into a matrix and count (and also print) the number of unique "islands" in the map formed by the matrix.

0 = Sea; 1 = Land; Islands are orthogonal groups of land.

testfile.txt :

5 9
00000
00010
10000
01101
10000
00100
01001
10010
01101

Python code:

# Reads the file and creates the matrix map.
with open('testfile.txt') as f:
    w = int(f.read(1))
    f.read(1)
    h = int(f.read(1))
    f.read(1)
    map = [[2 for x in range(w)] for y in range(h)]
    for y in range(h):
        for x in range(w):
            map[y][x] = int(f.read(1))
        f.read(1)

# Swipes the matrix map after NEW land chunks.
def swipe():
    counter = 0
    for x in range(h):
        for y in range(w):
            if map[x][y] == 1:
                counter += 1
                landInSight(map, x, y, 99)
    print(counter)

# Recursive function to hide any land attached to a chunk already swiped.
def landInSight(m, h, w, c):
    if m[h][w] == 1:
        m[h][w] = c
        if w < len(m[0]) - 1: landInSight(m, h, w + 1, c)
        if h < len(m) - 1: landInSight(m, h + 1, w, c)
        if w > 0: landInSight(m, h, w - 1, c)
        if h > 0: landInSight(m, h - 1, w, c)

# Calls the swipe function.
swipe()

It is a very simple code, but I took way too long coding it. This is my first "program" using Python and although it works, it seems too rough. I am looking for any constructive inputs from Python people.

Answer 1

You can make reading the input more concise and robust:

 def read_matrix(inp_file):
        """
        Reads the matrix from the input file and returns the number of rows, the number 
        of columns and the matrix itself as a list of lists of ints 
        """
        # reads the first line, splits it and parses the parts as integers
        w, h = map(int, inp_file.readline().strip().split())
        # converts the rest of the lines in the input to lists of integers
        field = [list(map(int, line.strip())) for line in inp_file]
        return h, w, field

This way it will work properly, even if one of the dimensions is larger than 9.

It's also common for a name of a function to be a verb. For instance, landInSight sounds a little bit wierd. I'd call it traverse_matrix or flood_fill_matrix or something like that.

The fact that your landInSight function is recursive can cause issues for larger inputs (namely, a stack overflow error). You can make it non-recursive by using a stack (implemented with a standard list) and a loop.

Answer 2

First of all, your solution for this task looks pretty elegant, from my point of view. I would just provide minor comments to optimize this code.

---

Your input data is a boolean matrix, so instead of keeping every value as a byte you can use just one bit. For that purpose you can use bitarray module.

---

Another point, that you are loading whole matrix to the memory. It can be too expensive in certain circumstances. I can suggest one stream-based solution which will calculate a number of islands in dynamic manner. This method was discussed here.