6
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ I would suggest to test also with multiple (randomly generated) houses of larger dimensions (20x20, 100x100, ...) \$\endgroup\$ – Martin R Jul 23 '18 at 21:05
  • \$\begingroup\$ Yes, I have exactly that -- one that does random iterations starting from an arbitrary average density, but omitted that from the code shown here. It's already rather long! \$\endgroup\$ – Edward Jul 23 '18 at 21:13
  • \$\begingroup\$ I'd also be interested to hear if you adapt it for your Swift version \$\endgroup\$ – Edward Jul 23 '18 at 21:15
1
\$\begingroup\$

The swapping

if (bigger < smaller) {
    std::swap(smaller, bigger);
}

if two rooms are merged seems to be unnecessary. The absolute tracker values are not important, only that they are identical for connected fields. Also

  • Your test suite still succeeds with that code removed.
  • Tests with random 100x100 maps resulted in the same room count with and without the swapping.

(I also ran the same random maps through my Swift version and got identical results.)

There is a small error in the setup of the testing threads:

for (auto i{n} ; i; --i) {
    chunks.push_back(std::async(testing, height, width, bits, n-1));
}

The same argument n-1 is passed to all threads, which means that they all test the same floor plan. It should be i-1 instead. And bits must be bits-1 in order to preset the last “bits” of a floor plan:

for (auto i{n} ; i; --i) {
    chunks.push_back(std::async(testing, height, width, bits-1, i-1));
}

Your method to iterate over all possible floor plans (with some pre-set bits at the end)

for (TestHouse t{height, width, bits, chunk}; t; ++t) {
    t.test();
}

is a bit too obscure in my opinion. To understand that loop one has to look-up the operator bool() and understand that it returns false if the last increment had an overflow.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the review (and spotting yet another bug! <sigh>). On the last comment, I can see your point. The way I designed it was to write that loop first and then implement the interface to support it, so it's intuitive to me, but perhaps less so to other readers of the code. I probably shouldn't have chopped all of the comments before posting, but figured it was already very long. \$\endgroup\$ – Edward Jul 25 '18 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.