7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – pgs Apr 29 '17 at 10:38
  • 2
    \$\begingroup\$ @pgs: The post says "islands are orthogonal groups of land". This seems clear to me (and it corresponds to the code). \$\endgroup\$ – Gareth Rees Apr 29 '17 at 11:18
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Bernardo Araujo Apr 29 '17 at 16:18
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Bernardo Araujo Apr 29 '17 at 20:54
  • \$\begingroup\$ @BernardoAraujo You can, but I don't think it's a good idea. These functions do different things. \$\endgroup\$ – kraskevich Apr 30 '17 at 7:49
  • \$\begingroup\$ @BernardoAraujo I think argument unpacking is what you are looking for: swipe(*read_matrix(inp_file)) \$\endgroup\$ – Janne Karila Apr 30 '17 at 19:30
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – kraskevich Apr 29 '17 at 14:23
  • \$\begingroup\$ @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! \$\endgroup\$ – pgs Apr 29 '17 at 14:29
  • \$\begingroup\$ 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. \$\endgroup\$ – kraskevich Apr 29 '17 at 14:43
  • \$\begingroup\$ @kraskevich: I guess I found one stream-like solution with cs help but I would like to implement in c instead of python. \$\endgroup\$ – pgs May 2 '17 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.