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!
