Sinling islands#
from IPython.display import HTML
Problem statement#
Let us call X the water areas and O the land areas. Then we can make a map of islands, like this:
X O X X X X
X O X O O X
X X X X O X
X O O X X X
X X X X O O
You’ll need to write a program that can single out islands (replace O with X) that don’t touch the edge of the map. So the example below will be replaced as follows:
X O X X X X
X O X X X X
X X X X X X
X X X X X X
X X X X O O
BFS#
BFS (Breadth-first search) algorithm that allows to extract connectivity components from graphs. Islands in our task can be understood as components. Therefore, BFS modified for our goals will be suitable for us.
In the following cell implemented function that finds connectivity components, replace “O” with “X” if needed and mark looked cells.
def bfs(board, looked_cells, beg_pos):
'''
Breadth-first search for our mission.
Realises breadth-first search that
all elements of the connectivity component for the
component for the given cell. And if
element of that component needs to be
with X, it replaces them.
Parameters
----------
board : list of lists
task board. Substitutions occur
directly in the passed argument;
looked_cells : list of lists of bools
True means that cell was looked.
Substitutions occur directly in
the passed argument;
beg_pos : tuple
cell position from which to start
the algorithm traversal.
'''
height = len(board)
width = len(board[0])
# We need to store the path in case it
# doesn't touch the edge of the map. We
# will keep the whole list, but each
# time we use an element from it, we
# will add one to stack_min. So stack[stack_min:]
# will represent the stack structure.
stack_min = 0
stack = [beg_pos]
# This is a flag that defines whether
# we need to replace the O with an X or not
replace = True
while len(stack) > stack_min:
# extract next element from stack
curr_pos = stack[stack_min]; stack_min += 1;
i, j = curr_pos[0], curr_pos[1]
looked_cells[i][j] = True
# if we found out that cell under consideration
# is on the edge of the board we need to set
# flag to replace O in connectivity component
# with X
if i==0 or i==height-1 or j==0 or j==width-1:
replace = False
# we need to check
# left, right, top, bottom
# points
if (
(i-1>0) and
(not looked_cells[i-1][j]) and
(board[i-1][j]=="O")
):stack.append((i-1, j))
if (
(i+1<height) and
(not looked_cells[i+1][j]) and
(board[i+1][j]=="O")
):stack.append((i+1, j))
if (
(j-1>0) and
(not looked_cells[i][j-1]) and
(board[i][j-1]=="O")
):stack.append((i, j-1))
if (
(j+1<width) and
(not looked_cells[i][j+1]) and
(board[i][j+1]=="O")
):stack.append((i, j+1))
# now if the flag indicates that it is
# necessary to change the values in the
# considered component of connectivity
if replace:
for i, j in stack:
board[i][j] = "X"
The next cell shows how the algorithm behaves for islands that should be flooded:
test_map = [
["X", "O", "X", "X", "X", "X"],
["X", "O", "O", "X", "X", "X"],
["X", "X", "X", "O", "O", "X"],
["X", "X", "X", "X", "O", "X"],
["X", "O", "O", "X", "X", "X"],
["X", "X", "X", "X", "O", "O"]
]
looked_cells = [[False]*len(test_map[0]) for i in range(len(test_map))]
bfs(test_map, looked_cells, (2,3))
display(HTML("<p style='font-size:16px'>Board</p>"))
display(test_map)
display(HTML("<p style='font-size:16px'>Looked</p>"))
display([
[("T" if v else "F") for v in l]
for l in looked_cells
])
Board
[['X', 'O', 'X', 'X', 'X', 'X'],
['X', 'O', 'O', 'X', 'X', 'X'],
['X', 'X', 'X', 'X', 'X', 'X'],
['X', 'X', 'X', 'X', 'X', 'X'],
['X', 'O', 'O', 'X', 'X', 'X'],
['X', 'X', 'X', 'X', 'O', 'O']]
Looked
[['F', 'F', 'F', 'F', 'F', 'F'],
['F', 'F', 'F', 'F', 'F', 'F'],
['F', 'F', 'F', 'T', 'T', 'F'],
['F', 'F', 'F', 'F', 'T', 'F'],
['F', 'F', 'F', 'F', 'F', 'F'],
['F', 'F', 'F', 'F', 'F', 'F']]
But for an island that touches the border of the board we must look through all its cells but not replace them.
test_map = [
["X", "O", "X", "X", "X", "X"],
["X", "O", "O", "X", "X", "X"],
["X", "X", "X", "O", "O", "X"],
["X", "X", "X", "X", "O", "X"],
["X", "O", "O", "X", "X", "X"],
["X", "X", "X", "X", "O", "O"]
]
looked_cells = [[False]*len(test_map[0]) for i in range(len(test_map))]
bfs(test_map, looked_cells, (0,1))
display(HTML("<p style='font-size:16px'>Board</p>"))
display(test_map)
display(HTML("<p style='font-size:16px'>Looked</p>"))
display([
[("T" if v else "F") for v in l]
for l in looked_cells
])
Board
[['X', 'O', 'X', 'X', 'X', 'X'],
['X', 'O', 'O', 'X', 'X', 'X'],
['X', 'X', 'X', 'O', 'O', 'X'],
['X', 'X', 'X', 'X', 'O', 'X'],
['X', 'O', 'O', 'X', 'X', 'X'],
['X', 'X', 'X', 'X', 'O', 'O']]
Looked
[['F', 'T', 'F', 'F', 'F', 'F'],
['F', 'T', 'T', 'F', 'F', 'F'],
['F', 'F', 'F', 'F', 'F', 'F'],
['F', 'F', 'F', 'F', 'F', 'F'],
['F', 'F', 'F', 'F', 'F', 'F'],
['F', 'F', 'F', 'F', 'F', 'F']]
Solution#
Now that we have the implementation of BFS for this task, we can just walk through the board. Go through the board and apply BFS to islands we haven’t applied it to yet.
def drown(board):
height = len(board)
width = len(board[0])
looked_cells = [[False]*width for i in range(height)]
for i in range(height):
for j in range(width):
if board[i][j]=="O" and (not looked_cells[i][j]):
bfs(board, looked_cells, (i, j))
Let’s try this solution.
test_map = [
["X", "O", "X", "X", "X", "X"],
["X", "O", "O", "X", "X", "X"],
["X", "X", "X", "O", "O", "X"],
["X", "X", "X", "X", "O", "X"],
["X", "O", "O", "X", "X", "X"],
["X", "X", "X", "X", "O", "O"]
]
drown(test_map)
test_map
[['X', 'O', 'X', 'X', 'X', 'X'],
['X', 'O', 'O', 'X', 'X', 'X'],
['X', 'X', 'X', 'X', 'X', 'X'],
['X', 'X', 'X', 'X', 'X', 'X'],
['X', 'X', 'X', 'X', 'X', 'X'],
['X', 'X', 'X', 'X', 'O', 'O']]