4
$\begingroup$

I was working on the following leetcode problem:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: 11110 11010 11000 00000

Output: 1

Example 2:

Input: 11000 11000 00100 00011

Output: 3

And wrote up the following explicit solution:

from collections import OrderedDict

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if len(grid) == 0:
            return 0

        land = ones(grid)
        parcels = len(land)
        islands = 0

        while parcels > 0:

            unexplored = []
            start = land.popitem()[0]
            parcels = parcels - 1

            print(start)

            up = (start[0] + 1, start[1])
            down = (start[0] - 1, start[1])
            left = (start[0], start[1] - 1)
            right = (start[0], start[1] + 1)

            if up in land:
                unexplored.append(up)
                del land[up]
            if down in land:
                unexplored.append(down)
                del land[down]
            if left in land:
                unexplored.append(left)
                del land[left]
            if right in land:
                unexplored.append(right)
                del land[right]

            while len(unexplored) > 0:

                start = unexplored.pop()
                parcels = parcels - 1

                up = (start[0] + 1, start[1])
                down = (start[0] - 1, start[1])
                left = (start[0], start[1] - 1)
                right = (start[0], start[1] + 1)

                if up in land:
                    unexplored.append(up)
                    del land[up]
                if down in land:
                    unexplored.append(down)
                    del land[down]
                if left in land:
                    unexplored.append(left)
                    del land[left]
                if right in land:
                    unexplored.append(right)
                    del land[right]

            islands += 1

        return islands

def ones(grid):
    ones = OrderedDict()
    height = len(grid)
    width = len(grid[0])

    for i in range(0,height):
        for j in range(0,width):
            if grid[i][j] == "1":
                ones[(i,j)] = 1

    return ones

But, my intuition said that finding the number of islands in a grid of ones and zeroes should be a good machine learning problem, associated with image detection.

So, I wrote the following code to generate test cases:

from random import randint

def make_grid():

    width = 30
    height = 30
    grid = []

    for i in range(0,height):
        row = []
        for j in range(0,width):
            if randint(0,1) == 0:
                row.append("0")
            else:
                row.append("1")
        grid.append(row)

    return grid

And, I then generated 60,000 cases and scored them using my explicit solution. I divided them into 50,000 train cases and 10,000 test cases.

I then tried to feed the train cases into a Keras network that was 64 nodes per layer, 10 layers deep using relu and a softmax activation function at the end. I trained the model for 250 iterations.

I got low accuracy statistics on recognizing the number of islands in the "images" on both the train and test cases.

I then tried to feed them into a Keras network using two convolutional layers, the first one 2x2 and the second one 4x4 with 64 nodes each followed by 2 dense layers with 64 nodes per layer. I trained the model for 3 iterations.

I got low accuracy statistics at predicting the number of islands in an "image" on both the train and test cases.

Is this just a bad problem for neural networks? Am I using the wrong kind of networks? Are my networks too small? Do I need to do a larger number of test cases?

Any input appreciated!

| improve this question | | | | |
$\endgroup$
0
$\begingroup$

For a start I would begin with simpler tests cases because they look rather complex (see an exemple of what you seems to simulate below). May be start with a 10x10 grid and generate 1 to 5 islands of different size.

enter image description here

| improve this answer | | | | |
$\endgroup$

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.