16 votes

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:

....#....#
....#.###.
....#.#.#.
#...#..#..
.#..#...#.

5 comments

  1. [2]
    onyxleopard
    (edited )
    Link
    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
    
    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)]
    
    7 votes
    1. Emerald_Knight
      Link Parent
      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!

      3 votes
  2. musa_totter
    (edited )
    Link
    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;
    }
    
    6 votes
  3. Emerald_Knight
    Link
    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.
        }
        
        public function load($grid_description) {
            $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[0]);
            
            $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();
    $grid->load($grid_description);
    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.

    5 votes
  4. Flashynuff
    (edited )
    Link
    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[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.
    
    4 votes