# Programming Challenge: Counting isolated regions.

Another week, another challenge!

This time, assume you're given a grid where each `.` represents an empty space and each `#` represents a "wall". We'll call any contiguous space of `.`s a "region". You can also think of a grid with no walls the "base" region. The walls may subdivide the base region into any number of isolated sub-regions of any shape or size.

Write a program that will, given a grid description, compute the total number of isolated regions.

For example, the following grid has 5 isolated regions:

``````....#....#
....#.###.
....#.#.#.
#...#..#..
.#..#...#.
``````

1. 
onyxleopard
(edited )
Someone at work asks this as an interview question. When he shared this with me it tickled my brain so I had to solve it for myself. I implemented two strategies in Python 3: a recursive solution...

Someone at work asks this as an interview question. When he shared this with me it tickled my brain so I had to solve it for myself. I implemented two strategies in Python 3: a recursive solution and a que-based solution. I also added an option to allow regions to be counted as connected along diagonals. I tweaked my program slightly to fit the question as posed.

``````#!/usr/bin/env python3

"""Search 2D bitmaps for regions of adjacent cells whose values are 'empty'
(as opposed to values that are 'walls').

Input is read as a string from stdin.

"""

from collections import deque

import numpy as np

"""Generate all regions adjacent to the given region (including itself)"""
if not (0, 0) <= cell < bitmap.shape:
return []
i, j = cell
rows, cols = bitmap.shape
north = (i - 1, j) if 0 < i else None
east = (i, j + 1) if j < cols - 1 else None
south = (i + 1, j) if i < rows - 1 else None
west = (i, j-1) if 0 < j else None
region = [
cell,
north,
east,
south,
west
]
if diagonals:
northeast = (i - 1, j + 1) if 0 < i and j < cols - 1 else None
southeast = (i + 1, j + 1) if i < rows - 1 and j < cols - 1 else None
southwest = (i + 1, j - 1) if i < rows - 1 and 0 < j else None
northwest = (i - 1, j - 1) if 0 < i and 0 < j else None
region = [
cell,
north, northeast, east, southeast,
south, southwest, west, northwest
]
return [c for c in region if c is not None]

def explore(bitmap, cell, region=[], explored=set(), diagonals=False):
"""Recursively explore a region of adjacent bits whose values are 1"""
return region

def regions_recursive(bitmap, diagonals=False):
"""Generate all regions of adjacent cells whose value is 1 recursively"""
explored = set()
for i, row in enumerate(bitmap):
for j, col in enumerate(row):
cell = i, j
if bitmap[cell]:
region = explore(
bitmap, cell,
region=[],
explored=explored,
diagonals=diagonals
)
if region:
yield sorted(region)

def regions_que(bitmap, diagonals=False):
"""Generate all regions of adjacent cells whose value is 1 via a deque"""
explored = set()
for i, row in enumerate(bitmap):
for j, col in enumerate(row):
cell = i, j
region = deque()
if bitmap[cell] and cell not in explored:
region.append(cell)
while not all(((c in explored) for c in region)):
cell = region.popleft()
if region:
yield sorted(set(region))

def regions(bitmap, strategy, **kwargs):
"""Generate all regions using the given strategy"""
return strategy(bitmap, **kwargs)

def show(bitmap, strategy, wall='#', empty='.', **kwargs):
"""Pretty-print a bitmap and all regions of adjacent 1s in the bitmap"""
print(f'bitmap (empty="{empty}"; wall="{wall}"):')
print(
*(''.join([empty if c else wall for c in row]) for row in bitmap),
sep='\n'
)
print('empty regions:')
for region in regions(bitmap, strategy, **kwargs):
print(region)

def load(s, col_sep=None, row_sep='\n', wall='#', empty='.'):
"""Load a bitmap as a numpy array from a string

[0, 1, 0, 1],
[0, 1, 1, 1],
[0, 1, 0, 1]
])

"""
bitmap = []
for row in s.rstrip().split(row_sep):
row = [c for c in row] if col_sep is None else row.split(col_sep)
row = [int(c == empty) for c in row]
bitmap.append(row)
return np.array(bitmap, dtype=int)

if __name__ == '__main__':
import argparse
import sys
STRATEGIES = {
'recursive': regions_recursive,
'que': regions_que
}
parser = argparse.ArgumentParser(
description=__doc__,
formatter_class=argparse.ArgumentDefaultsHelpFormatter
)
'-c', '--column-delimiter',
default=None,
help='column delimiter string'
)
'-r', '--row-delimiter',
default='\n',
help='row delimiter string'
)
'-s', '--strategy',
default='que',
choices=STRATEGIES,
help='specify a strategy to use'
)
'-w', '--wall',
default='#',
help="character to consider as a 'wall'",
)
'-e', '--empty',
default='.',
help="character to consider as 'empty'",
)
'-d', '--count-diagonals',
action='store_true',
help=(
'consider diagonal cells to be adjacent; e.g., '
'[0,0] and [1,1] would be considered adjacent'
)
)
args = parser.parse_args()
col_sep=args.column_delimiter,
row_sep=args.row_delimiter,
wall=args.wall,
empty=args.empty
)
show(
bitmap,
STRATEGIES[args.strategy],
diagonals=args.count_diagonals,
wall=args.wall,
empty=args.empty
)
``````

And running from command-line driver:

``````\$ cat input.txt
....#....#
....#.###.
....#.#.#.
#...#..#..
.#..#...#.
\$ ./regions.py < input.txt
bitmap (empty="."; wall="#"):
....#....#
....#.###.
....#.#.#.
#...#..#..
.#..#...#.
empty regions:
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 2), (4, 3)]
[(0, 5), (0, 6), (0, 7), (0, 8), (1, 5), (2, 5), (3, 5), (3, 6), (4, 5), (4, 6), (4, 7)]
[(1, 9), (2, 9), (3, 8), (3, 9), (4, 9)]
[(2, 7)]
[(4, 0)]
\$ ./regions.py -d < input.txt
bitmap (empty="."; wall="#"):
....#....#
....#.###.
....#.#.#.
#...#..#..
.#..#...#.
empty regions:
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 0), (4, 2), (4, 3)]
[(0, 5), (0, 6), (0, 7), (0, 8), (1, 5), (1, 9), (2, 5), (2, 7), (2, 9), (3, 5), (3, 6), (3, 8), (3, 9), (4, 5), (4, 6), (4, 7), (4, 9)]
``````
1. Emerald_Knight
Accounting for whether or not diagonals should be considered "square" or "smooth", huh? Nice touch!

Accounting for whether or not diagonals should be considered "square" or "smooth", huh? Nice touch!

2. musa_totter
(edited )
C++ solution. Grid is hardcoded, but if you wanted you could add the ability to take in input without too much trouble. The code assumes the rows can be variable-length, so there's a bit of...

C++ solution. Grid is hardcoded, but if you wanted you could add the ability to take in input without too much trouble. The code assumes the rows can be variable-length, so there's a bit of inefficiency in checking lengths for each row.

``````#include <cstdio>
#include <queue>
#include <utility>
#include <tuple>
#include <vector>
#include <string>

constexpr char wall = '#';
constexpr char space = '.';

const std::vector<std::string> map = {
"....#....#",
"....#.###.",
"....#.#.#.",
"#...#..#..",
".#..#...#."
};

int main() {
std::vector<std::vector<int>> regions;
for(auto& row: map) {
regions.push_back(std::vector<int>(row.size(), 0));
}

int regionCount = 0;

for(int i = 0; i < map.size(); i++) {
for(int j = 0; j < map[i].size(); j++) {
if(map[i][j] == space && regions[i][j] == 0) {
regionCount++;

std::queue<std::pair<int,int>> q;
q.push(std::make_pair(i, j));

while(q.size() > 0) {
int a, b;
std::tie(a, b) = q.front();
if(a >= 0 && a < map.size() && b >= 0 && b < map[a].size() && map[a][b] == space && regions[a][b] == 0) {
regions[a][b] = regionCount;
q.push(std::make_pair(a + 1, b    ));
q.push(std::make_pair(a - 1, b    ));
q.push(std::make_pair(a    , b + 1));
q.push(std::make_pair(a    , b - 1));
}

q.pop();
}
}
}
}

printf("%d regions\n", regionCount);

return 0;
}
``````
3. Emerald_Knight
I've been procrastinating, but here's my solution in PHP: <?php class Node { private \$visited = false; private \$value = null; public function __construct(\$value) { \$this->value = \$value; } public...

I've been procrastinating, but here's my solution in PHP:

``````<?php

class Node {
private \$visited = false;
private \$value = null;

public function __construct(\$value) {
\$this->value = \$value;
}

public function getValue() {
return \$this->value;
}

public function markVisited() {
\$this->visited = true;
}

public function wasVisited() {
return \$this->visited;
}
}

class Grid {
const CHAR_WALL = '#';
const CHAR_FLOOR = '.';

private \$grid = null;
private \$num_rows = -1;
private \$num_cols = -1;

public function __construct() {
// Do nothing.
}

\$grid_rows = array();
\$rows = explode(',', \$grid_description);

foreach(\$rows as \$row) {
\$columns = str_split(\$row);
\$grid_row = array();
foreach(\$columns as \$column) {
array_push(\$grid_row, new Node(\$column));
}

array_push(\$grid_rows, \$grid_row);
}

\$this->num_rows = count(\$grid_rows);
\$this->num_cols = count(\$grid_rows);

\$this->grid = \$grid_rows;
}

public function getTotalRegions() {
\$regions = 0;
foreach(\$this->grid as \$row_index=>\$row) {
foreach(\$row as \$col_index=>\$node) {
\$regions += \$node->getValue() === self::CHAR_FLOOR && !\$node->wasVisited() ? 1 : 0;
\$this->expandRegion(\$row_index, \$col_index);
}
}

return \$regions;
}

private function expandRegion(\$row, \$col) {
if(\$row < 0 || \$row >= \$this->num_rows) {
return;
}

if(\$col < 0 || \$col >= \$this->num_cols) {
return;
}

\$node = \$this->grid[\$row][\$col];
if(\$node->getValue() === self::CHAR_WALL) {
return;
}

if(\$node->wasVisited()) {
return;
}

\$node->markVisited();

\$this->expandRegion(\$row + 1, \$col);
\$this->expandRegion(\$row - 1, \$col);
\$this->expandRegion(\$row, \$col + 1);
\$this->expandRegion(\$row, \$col - 1);
}
}

\$grid_description = implode(',', array(
'....#....#',
'....#.###.',
'....#.#.#.',
'#...#..#..',
'.#..#...#.'
));

\$grid = new Grid();
echo \$grid->getTotalRegions();

?>
``````

There's no data validation whatsoever. I've not added a way to receive input, instead using a hard-coded test case. I don't even check that each row is the same length, or that anything has even been passed in. There are unnecessary recursive levels that could be avoided. This entire thing is pretty inefficient and could be written a lot better. It's still a solution, though.

For the less experienced here, it's a basic depth-first search (DFS) approach. This is a term for a recursive algorithm where you go as far down one path as you possibly can before trying the paths next to it. The counterpart to DFS is the breadth-first search (BFS) approach, where you try each path level by level. The general idea behind this solution is to "fill" the regions by starting at an open spot, "marking" the spot as "visited", and expanding out toward other nearby "unvisited" spots. When this "expanding" action is complete (i.e. we couldn't find any more "unvisited" spots without running into a wall), we've finished marking an entire enclosed region. Additionally, every time we encounter a new, untouched region, we increase the counter by 1.

4. Flashynuff
(edited )
Alright, I've implemented a solution for this in Ruby. It's been a while since I really did any programming so this was a lot harder than it should have been, and my code is probably really messy...

Alright, I've implemented a solution for this in Ruby. It's been a while since I really did any programming so this was a lot harder than it should have been, and my code is probably really messy and not very ruby-like. I'm also not all that experienced in the quirks of Ruby. But it works! It assumes the grid is in a text file called 'grid.txt' in the same directory.

The idea is to traverse the grid and look for empty regions. If an empty region is found (i.e., an empty space), it then recursively goes through all the spaces connected to the first empty space and marks that they've been looked at. Once all the spaces in a region have been found, it goes back to the next cell over from the initial space and starts the process over. If the cell is a space that has already been looked at or it is a wall, it skips over and checks the next cell.

``````class Cell
attr_accessor :x, :y, :type, :has_region
def initialize(x, y, type)
@x = x
@y = y
@type = type
@has_region = false
end
end

def next_cell (cell, grid_array)
if cell.x < grid_array.length - 1
return grid_array[cell.y][cell.x + 1]
elsif cell.y < grid_array.length - 1
return grid_array[cell.y + 1]
end
return cell
end

def search(cell, grid_array)
# If the cell is a wall, return false
if cell.type == '#'
return false
# If the cell has a region already, we've already looked at it
elsif cell.has_region
return false
end

# otherwise, the cell is a space that does not currently have a region.
# mark the cell with a region and search for the next ones
cell.has_region = true

if (cell.x < grid_array.length - 1 && search(grid_array[cell.y][cell.x+1], grid_array)) || # check right cell
(cell.y > 0 && search(grid_array[cell.y-1][cell.x], grid_array)) || # check below cell
(cell.x > 0 && search(grid_array[cell.y][cell.x-1], grid_array)) || # check left cell
(cell.y < grid_array.length - 1 && search(grid_array[cell.y+1][cell.x], grid_array)) # check above
return true
end

return false
end

# read the grid in from a text file
regions_count = 0

# Build a grid array

grid_array = []

grid.each_with_index do |row, y|
row_array = []
row.chomp.chars.each_with_index do |char, x|
row_array.push(Cell.new(x, y, char))
end
grid_array.push row_array
end

# traverse the grid, checking each cell to see if it's the start of a new region

current_cell = grid_array
size = grid_array.length * grid.length
count = 0

while count < size
if  current_cell.type == '.' and !current_cell.has_region
# this is a cell that is both a space, and is the start of a new region.
regions_count += 1
search(current_cell, grid_array)
current_cell = next_cell(current_cell, grid_array)
count += 1
next
else
# either the cell is a wall, or it already has a region.
# either way we don't care about it so we go to the next cell.
current_cell = next_cell(current_cell, grid_array)
count += 1
next
end
end

puts "There were #{regions_count} unique regions."
``````

output:

``````\$ ruby regions.rb
There were 5 unique regions.
``````