|
Here are three similar algorithms in Python for operations on “island problems”.
These are problems were the input is a 2D matrix of grid coordinates, where 0
represents sea and 1 represents land.
For example:
[
[1, 0, 1, 0, 1],
[1, 0, 1, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 0, 0],
[1, 1, 0, 0, 1],
]
It’s slightly hard to see, but there are 5 islands in this grid: one in each
corner, and a larger contiguous one in the shape of an L.
The general approach for these algorithms is similar: iterate the grid, and when
we hit a land cell, mark of all of its neighbouring land cells as visited while
keeping track of whichever piece of information we’re interested in.
This approach is $O(n)$ for all of these problems, as we visit each cell once or
twice.
Each of the solutions needs to import some types, and also a deque for
handling the queue of cells to visit.
We’ll also need a list of directions to check neighbouring cells.
from typing import List, Set, Tuple
from collections import deque
DIRS = [
[-1, 0],
[0, 1],
[1, 0],
[0, -1],
]
Island counting
The island counting algorithm is the simplest, as we don’t need to track
anything about each separate island. When we hit a land cell, we mark all of its
neighbours as visited, and increment our total island count by one.
This can be done recursively, but I’m using a queue here instead, which I think
makes it easier to follow and debug.
def count_islands(grid: List[List[int]]) -> int:
s = len(grid)
island_count = 0
visited = set() # type: Set[Tuple[int, int]]
for i, row in enumerate(grid):
for j, cell in enumerate(row):
if cell == 0 or (i, j) in visited:
continue
island_count += 1
vis_nxt = deque()
vis_nxt.append((i, j))
while vis_nxt:
vis = vis_nxt.popleft()
if vis in visited:
continue
visited.add(vis)
if grid[vis[0]][vis[1]] == 0:
continue
for d in DIRS:
nbr = (vis[0] + d[0], vis[1] + d[1])
if nbr[0] < 0 or nbr[1] < 0 or nbr[0] >= s or nbr[1] >= s:
continue
vis_nxt.append((vis[0] + d[0], vis[1] + d[1]))
return island_count
Max island area
The max island area algorithm is perhaps slightly trickier than the total island
count, and slightly less tricky than the max island perimeter algorithm.
The only difference from the total island count algorithm is that we count each
neighbouring land cell as we visit a contiguous island, and then track the max
of that after each whole island visit.
def max_island_area(grid: List[List[int]]) -> int:
s = len(grid)
mia = 0
visited = set() # type: Set[Tuple[int, int]]
for i, row in enumerate(grid):
for j, cell in enumerate(row):
if (i, j) in visited:
continue
if cell == 0:
continue
tia = 0
nxt_q = deque()
nxt_q.append((i, j))
while nxt_q:
nxt = nxt_q.popleft()
if grid[nxt[0]][nxt[1]] == 0 or nxt in visited:
continue
visited.add(nxt)
tia += 1
for d in DIRS:
nbr = (nxt[0] + d[0], nxt[1] + d[1])
if nbr[0] < 0 or nbr[1] < 0 or nbr[0] >= s or nbr[1] >= s:
continue
nxt_q.append(nbr)
mia = max(mia, tia)
return mia
Max island perimeter
The last of these three problems is tracking the max island perimeter. This is
probably a little bit harder than the other two, but not by much.
The main difference is that there’s a little trick to calculating the island
perimeter, which is to add 4 for each island cell, and also subtract 2 for each
neighbour of a cell to the west or the north. This is because we don’t want to
count an internal perimeter, i.e. an edge between two neighbouring land cells.
We subtract 2 for each of these because we previously added 4 full edges for
both of the neighbouring cells.
This diagram might make this a bit clearer:
┌─┐
│A│
┌─┼═┤
│B║C│
└─┴─┘
There are 3 land cells labelled A, B and C. While visiting them, we add 4 to the
perimeter edge count for each. We have now counted 12 edges.
While visiting cell C, we check its neighbour to the north, and see cell A
there. This means there is an internal edge there, marked on the diagram with a
double line. This isn’t an external perimeter edge, but has been counted twice
(once for A and once for C), so we subtract 2.
Next we check C’s neighbour to the west, and find cell B. Again the internal
edge between them has been marked with a double line on the diagram. Because we
already counted 4 edges for both B and C, we need to subtract 2 to exclude the
internal edge between them.
With this approach, we do $4 + 4 + (4 - 2 - 2) = 8$, which is the correct count
of external perimeter edges of the island.
Finally, we just apply that sub-algorithm to each island we encounter in the
whole grid, and keep track of the max perimeter to return.
def max_island_perimeter(grid: List[List[int]]) -> int:
s = len(grid)
mip = 0
visited = set() # type: Set[Tuple[int, int]]
for i, row in enumerate(grid):
for j, cell in enumerate(grid):
if cell == 0 or (i, j) in visited:
continue
tip = 0
nxt_q = deque()
nxt_q.append((i, j))
while nxt_q:
tc = nxt_q.popleft()
if grid[tc[0]][tc[1]] == 0 or tc in visited:
continue
visited.add(tc)
tip += 4
if tc[0] > 0 and grid[tc[0] - 1][tc[1]] == 1:
tip -= 2
if tc[1] > 0 and grid[tc[0]][tc[1] - 1] == 1:
tip -= 2
for d in DIRS:
nbr = (tc[0] + d[0], tc[1] + d[1])
if nbr[0] < 0 or nbr[1] < 0 or nbr[0] >= s or nbr[1] >= s:
continue
nxt_q.append(nbr)
mip = max(mip, tip)
return mip
View post:
Island counting, max island area and max island perimeter in Python
|