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.

• pgs: Can you make more clear definition of an island? Imagine you have diagonal matrix - it's one island or it's equal to the matrix dimension?
• Gareth Rees: @pgs: The post says "islands are orthogonal groups of land". This seems clear to me (and it corresponds to the code).
• Bernardo Araujo: @pgs: As Gareth pointed out two "lands" will be considered from the same island only if they are touching in an orthogonal relation a diagonal would result in different islands unless there is another (or more) land units forming an orthogonal connection between those.

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.

• Bernardo Araujo: Thank you for the input, your parse is much more elegant than mine and also corrected a problem that I hadn't stumbled on yet (when the number of rows or columns is greater than nine). But, since the reader became a method, is there a way to pass it directly to the new swipe method? In other words, can i turn this two lines: h, w, f = read_matrix(inp_file) and swipe(h, w, f) into one?
• kraskevich: @BernardoAraujo You can, but I don't think it's a good idea. These functions do different things.
• Janne Karila: @BernardoAraujo I think argument unpacking is what you are looking for: swipe(*read_matrix(inp_file))

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.

• kraskevich: You code doesn't seem to be correct. It prints 0 for a 1x1 matrix consisting of one element 1, while the correct answer is 1.
• pgs: @kraskevich: yes, I agree. It was one misspelling b0 = count_continuous_block(s1) instead of b0 = count_continuous_block(s0). I changed it. Thank you!
• kraskevich: If the input is an arbitrary 0-1 matrix, your code still doesn't always work. It prints 0 for the matrix [[1, 1, 1], [1, 0, 1], [1,1, 1]], but there's clearly 1 connected component.
• pgs: @kraskevich: I guess I found one stream-like solution with cs help but I would like to implement in c instead of python.