This is version 3 of Efficiently counting rooms from a floorplan. Version 2 is here Efficiently counting rooms from a floorplan (version 2)
It also has a comprehensive test facility that is the focus of this question.
To recap, the problem (from here) is this:
You are given a map of a building, and your task is to count the number of rooms. The size of the map is \$n \times m\$ squares, and each square is either floor or wall. You can walk left, right, up, and down through the floor squares.
Input
The first input line has two integers \$n\$ and \$m\$: the height and width of the map.
Then there are \$n\$ lines of \$m\$ characters that describe the map. Each character is
.(floor) or#(wall).Output
Print one integer: the number of rooms.
Constraints
\$1\le n,m \le 2500\$
Example
Input:
5 8 ######## #..#...# ####.#.# #..#...# ########Output:
3
Strategy
It seemed to me to be possible to solve the problem by processing line at a time, so that's what my code does. Specifically, it keeps a tracking std::vector<std::size_t> named tracker that corresponds to the rooms from the previous row and starts with all zeros.
As it reads each line of input, it processes the line character at a time. If it's non-empty (that is, if it's a wall), set the corresponding tracker entry to 0.
Otherwise, if the previous row (that is, the matching value from the tracker vector) was a room, then this is part of the same room.
If the previous character in the same row was a room, this is the same room.
The code also has provisions for recognizing that what it "thought" was two rooms turns out to be one room, and adjusts both the tracker vector and increments the merges variable.
Testing
Because there were a number of false starts, I wanted to make sure this one was entirely accurate before posting it. So to that end, I wrote a generic routine that uses a simple flood fill. It's based on a class I named House that reads and stores the entire input. It's simple and reliable, but slow. I use it to verify the inline version that is implemented as a function. Finally,, there is a TestHouse class for testing one against the other of these. Finally, the main test routine generates all possible test cases of the dimensions given on the command line and tests the two routines against each other using multiple tasks if std::thread::hardware_concurrency() returns a value greater than one. It's also assumed in the code that the value returned is a power of 2, which is strictly true for all of my machines, but might not be for yours.
Also, I'm aware that the output from the test routine should use a mutex to control access to std::cout but since, in my testing, there isn't any output anyway, I'm not so concerned about it and didn't bother adding it.
Results
I've tested this exhaustively with sizes up to 5x7. All tests pass.
roomtest.cpp
#include "House.h"
#include "Rooms.h"
#include <sstream>
#include <iterator>
#include <future>
#include <vector>
#include <string>
#include <cstddef>
class TestHouse {
public:
TestHouse(std::size_t height, std::size_t width, unsigned bits=0, unsigned chunk=0);
explicit operator bool() const { return !overflow; }
TestHouse& operator++();
friend std::ostream& operator<<(std::ostream& out, const TestHouse& t);
void test() const;
private:
static constexpr char wall{'#'};
static constexpr char empty{'.'};
bool increment(std::size_t n);
std::size_t height{0};
std::size_t width{0};
std::vector<std::string> floor;
bool overflow{false};
unsigned bits{0};
};
TestHouse::TestHouse(std::size_t height, std::size_t width, unsigned bits, unsigned chunk) :
height{height},
width{width},
overflow{false},
bits{bits}
{
floor.reserve(height);
std::string line(width, wall);
for (auto i{height}; i; --i) {
floor.push_back(line);
}
for ( ; chunk; --chunk) {
bool carry{true};
for (auto n{height * width - bits}; carry && n < height*width; ++n) {
carry = increment(n);
}
}
}
// increment a single indicated bit and return carry as appropriate
bool TestHouse::increment(std::size_t n) {
auto row{n / width};
auto col{n % width};
if (floor[row][col] == wall) {
floor[row][col] = empty;
return false;
}
floor[row][col] = wall;
return true;
}
// increment as though the entire array were one big binary value
TestHouse& TestHouse::operator++() {
bool carry{true};
for (std::size_t n{0}; carry && n < height*width - bits; ++n) {
carry = increment(n);
}
overflow = carry;
return *this;
}
std::ostream& operator<<(std::ostream& out, const TestHouse& t) {
out << t.height << ' ' << t.width << '\n';
for (const auto& line : t.floor) {
out << line << '\n';
}
return out;
}
void TestHouse::test() const {
House h{height, width, floor};
auto good = h.rooms();
auto alt{rooms(height, width, floor)};
if (alt != good) {
std::cout << *this << alt << " != " << good << '\n';
}
}
void testing(std::size_t height, std::size_t width, unsigned bits, unsigned chunk) {
for (TestHouse t{height, width, bits, chunk}; t; ++t) {
t.test();
}
}
int main(int argc, char *argv[]) {
if (argc != 3) {
std::cerr << "Usage: roomtest height width\n";
return 1;
}
auto height{std::stoul(argv[1])};
auto width{std::stoul(argv[2])};
auto n{std::thread::hardware_concurrency()};
if (n < 2) {
n = 2;
}
auto bits{0u};
// note that this assumes that n is a non-zero power of 2
for (auto i{n}; i; i >>= 1) {
++bits;
}
std::vector<std::future<void>> chunks;
for (auto i{n} ; i; --i) {
chunks.push_back(std::async(testing, height, width, bits, n-1));
}
for (auto& task : chunks) {
task.get();
}
}
House.h
#ifndef HOUSE_H
#define HOUSE_H
#include <iostream>
#include <vector>
#include <string>
#include <cstddef>
class House {
public:
House() : height{0}, width{0}, floor{} {}
House(std::size_t height, std::size_t width, std::vector<std::string> plan) :
height{height}, width{width}, floor{plan}
{}
friend std::ostream& operator<<(std::ostream& out, const House& h);
std::size_t rooms();
private:
bool flood(std::vector<std::string>& floorplan);
void fill(std::size_t row, std::size_t col, std::vector<std::string>& floorplan);
static constexpr char empty{'.'};
static constexpr char explored{'x'};
std::size_t height;
std::size_t width;
std::vector<std::string> floor;
};
#endif // HOUSE_H
Rooms.h
#ifndef ROOMS_H
#define ROOMS_H
#include <cstddef>
#include <iostream>
#include <vector>
#include <string>
std::size_t rooms(std::size_t height, std::size_t width, const std::vector<std::string>& plan);
#endif // ROOMS_H
House.cpp
#include "House.h"
std::ostream& operator<<(std::ostream& out, const House& h) {
for (const auto& row : h.floor) {
out << row << '\n';
}
return out;
}
// given row and column, fills all empty cells
// reachable from that room, where 'reachable' means
// that a cell is adjacent to an empty cell in one
// of the four compass directions
void House::fill(std::size_t row, std::size_t col, std::vector<std::string>&f loorplan) {
if (row >= height || col >= width || floorplan[row][col] != empty) {
return;
}
floorplan[row][col] = explored;
fill(row+1, col, floorplan);
fill(row-1, col, floorplan);
fill(row, col+1, floorplan);
fill(row, col-1, floorplan);
}
// finds an empty room and floods it
// return false if no empty rooms were found
bool House::flood(std::vector<std::string>& floorplan) {
for (std::size_t i{0}; i < height; ++i) {
for (std::size_t j{0}; j < width; ++j) {
if (floorplan[i][j] == empty) {
fill(i, j, floorplan);
return true;
}
}
}
return false;
}
std::size_t House::rooms() {
std::size_t rooms{0};
for ( ; flood(floor); ++rooms) {
}
return rooms;
}
Rooms.cpp
#include "Rooms.h"
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
std::size_t rooms(std::size_t height, std::size_t width, const std::vector<std::string>& plan) {
std::size_t roomcount{0};
std::size_t merges{0};
static constexpr char empty{'.'};
std::vector<std::size_t> tracker(width, 0);
for (const auto& row : plan) {
for (std::size_t j{0}; j < width; ++j) {
if (row[j] == empty) {
// continuation from line above?
if (tracker[j]) {
// also from left?
if (j && tracker[j-1] && (tracker[j-1] != tracker[j])) {
auto bigger = tracker[j-1];
auto smaller = tracker[j];
// make sure they're in the right order
if (bigger < smaller) {
std::swap(smaller, bigger);
}
// rooms have joined
std::replace(tracker.begin(), tracker.end(), bigger, smaller);
++merges;
}
} else {
// continuation from left?
if (j && tracker[j-1]) {
tracker[j] = tracker[j-1];
} else {
tracker[j] = ++roomcount;
}
}
} else {
tracker[j] = 0;
}
}
}
return roomcount-merges;
}
