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:
....#....#
....#.###.
....#.#.#.
#...#..#..
.#..#...#.
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.
And running from command-line driver:
Accounting for whether or not diagonals should be considered "square" or "smooth", huh? Nice touch!
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.
I've been procrastinating, but here's my solution in PHP:
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.
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.
output: