Card 07/ 08
Practice: Counting the Enclosed Courtyards on a Map
Open squares joined to the edge of the map are not enclosed: find how many groups of open squares are walled in on every side.
Some region questions are answered by filling from the edge of the grid first. A plan of a building marks walls with # and open squares with ., and squares that touch above, below, left or right are joined. A courtyard is a group of joined open squares that is walled in on every side; open squares joined to the edge of the map lead outside and are not a courtyard. How many courtyards does the plan hold, and how would you find them without checking each region for an edge square after filling it?
# # # # # # #
# . . # . . #
# . # # # . .
# # . . # # #
# . # . # . #
# # # # # # #Show the answer and a solution
4 courtyards, of 3, 3, 1 and 1 squares. The plan holds 5 groups of open squares, and the group at the top right reaches the edge at (2, 6), so it leads outside. The solution makes every open square on the edge a source of one fill, which labels everything that reaches the edge, then counts the regions left with a fill from each square still unlabelled, as when counting islands. The listing labels the outside region o and each courtyard with a letter.
DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))
def fill(grid: list[str], label: list[list[str]], start: tuple[int, int], name: str) -> None:
rows, cols = len(grid), len(grid[0])
label[start[0]][start[1]] = name
stack = [start]
while stack:
row, col = stack.pop()
for d_row, d_col in DIRECTIONS:
r, c = row + d_row, col + d_col
if 0 <= r < rows and 0 <= c < cols and grid[r][c] == "." and label[r][c] == "":
label[r][c] = name
stack.append((r, c))
def courtyards(grid: list[str]) -> list[list[str]]:
rows, cols = len(grid), len(grid[0])
label = [["#" if cell == "#" else "" for cell in line] for line in grid]
for row in range(rows):
for col in range(cols):
on_edge = row in (0, rows - 1) or col in (0, cols - 1)
if on_edge and label[row][col] == "":
fill(grid, label, (row, col), "o")
found = 0
for row in range(rows):
for col in range(cols):
if label[row][col] == "":
fill(grid, label, (row, col), chr(ord("A") + found))
found += 1
return label
plan = ["#######", "#..#..#", "#.###..", "##..###", "#.#.#.#", "#######"]
label = courtyards(plan)
for line in label:
print(" ".join(line))
names = [name for line in label for name in line if name not in ("#", "o")]
print("courtyards:", len(set(names)), "sizes:", [names.count(name) for name in sorted(set(names))])# # # # # # #
# A A # o o #
# A # # # o o
# # B B # # #
# C # B # D #
# # # # # # #
courtyards: 4 sizes: [3, 3, 1, 1]Filling each region and checking afterwards whether it touched the edge also works, but needs a flag carried through every fill or a second pass over each region. Filling from the edge first removes the outside regions in one sweep, and the count that follows is the islands count unchanged. Every square is filled at most once, so the whole is O(R · C) time and space.
← → move through sections and cards