From f652ea0be6cb6ea4340971ed06852f071b8519a4 Mon Sep 17 00:00:00 2001 From: William Carroll Date: Fri, 20 Nov 2020 21:32:22 +0000 Subject: Solve "count islands" problem This morning, I attended the "Interview Club" and was asked this question by the interviewer in front of ~20 FTEs. While I struggled to fully solve it during the abridged (i.e. 20 minute) timeslot, I completed the problem afterwards. Here is my solution. --- scratch/facebook/count-islands.py | 53 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) create mode 100644 scratch/facebook/count-islands.py (limited to 'scratch/facebook/count-islands.py') diff --git a/scratch/facebook/count-islands.py b/scratch/facebook/count-islands.py new file mode 100644 index 000000000000..a007684bca23 --- /dev/null +++ b/scratch/facebook/count-islands.py @@ -0,0 +1,53 @@ +from collections import deque + +def maybe_queue(row, col, game, q, seen): + """ + Add coordinate, (`row`, `col`), to the queue, `q`, as long as it exists in + the map, `game`, and it is not already present in `seen`. + """ + if row >= 0 and row < len(game) and col >= 0 and col < len(game[0]): + if game[row][col] == 'L' and (row, col) not in seen: + q.append((row, col)) + +def visit_island(row, col, game, seen): + """ + Starting at the coordinate, (`row`, `col`), in the map, `game`, visit all + surrounding tiles marked as land by adding them to the `seen` set. + """ + q = deque() + q.append((row, col)) + while q: + row, col = q.popleft() + seen.add((row, col)) + maybe_queue(row - 1, col, game, q, seen) # UP + maybe_queue(row + 1, col, game, q, seen) # DOWN + maybe_queue(row, col - 1, game, q, seen) # LEFT + maybe_queue(row, col + 1, game, q, seen) # RIGHT + +def count_islands(game): + """ + Return the number of contiguous land tiles in the map, `game`. + """ + result = 0 + seen = set() + for row in range(len(game)): + for col in range(len(game[row])): + if game[row][col] == 'L' and (row, col) not in seen: + visit_island(row, col, game, seen) + result += 1 + return result + +################################################################################ +# Tests +################################################################################ + +game = [ + "LWLWWW", + "LLLWWW", + "WWWLLW", +] + +result = count_islands(game) +print(result) +assert result == 2 +print("Success!") -- cgit 1.4.1