Programming Challenge: Counting isolated regions.

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

def adjacents(bitmap, cell, diagonals=False):
    """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"""
    for adjacent in adjacents(bitmap, cell, diagonals):
        if adjacent not in explored:
            explored.add(adjacent)
            if bitmap[adjacent]:
                region.append(adjacent)
                explore(bitmap, adjacent, region, explored, diagonals)
    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()
                    explored.add(cell)
                    for adjacent in adjacents(bitmap, cell, diagonals):
                        if bitmap[adjacent] and adjacent not in set(region):
                            region.append(adjacent)
            explored.add(cell)
            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

    load('.#.#\n.###\n.#.#') -> numpy.array([
        [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
    )
    parser.add_argument(
        '-c', '--column-delimiter',
        default=None,
        help='column delimiter string'
    )
    parser.add_argument(
        '-r', '--row-delimiter',
        default='\n',
        help='row delimiter string'
    )
    parser.add_argument(
        '-s', '--strategy',
        default='que',
        choices=STRATEGIES,
        help='specify a strategy to use'
    )
    parser.add_argument(
        '-w', '--wall',
        default='#',
        help="character to consider as a 'wall'",
    )
    parser.add_argument(
        '-e', '--empty',
        default='.',
        help="character to consider as 'empty'",
    )
    parser.add_argument(
        '-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()
    bitmap = load(
        sys.stdin.read(),
        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)]

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;
}

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[0].length - 1
		return grid_array[cell.y][cell.x + 1]
	elsif cell.y < grid_array.length - 1
		return grid_array[cell.y + 1][0]
	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[0].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
grid = IO.readlines('grid.txt')
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[0][0]
size = grid_array.length * grid[0].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.