10
\$\begingroup\$

This is version 2 of Efficiently counting rooms from a floorplan. I had accidentally pasted in the wrong version of the code.

Update

Final version (version 3) of the code with updated test harness is here: Multithreaded testing for counting rooms from a floor plan solution


I was inspired by Calculating the number of rooms in a 2D house and decided to see if I could come up with efficient code to solve the same problem.

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 the overall roomcount.

Because I wanted to be able to test it with many different inputs, my version of the code keeps reading and processing each floor plan until it gets to the end of the file.

The code is time efficient because it makes only a single pass through the input, and it's memory efficient because it only allocates a single \$1 \times m\$ vector.

Questions

  1. Correctness - The code works correctly on every input I've tried, but if there is any error in either the code or the algorithm, I'd like to know.
  2. Efficiency - Could the code be made even more efficient?
  3. Reusability - This works for a 2D map, but I'd like to adapt it to 3 or more dimensions. Are there things I could do in this code to make such adaptation simpler?

Any hints on style or any other aspect of the code would be welcome as well.

rooms.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::size_t rooms(std::istream &in) {
    std::size_t height;
    std::size_t width;
    std::size_t roomcount{0};
    static constexpr char empty{'.'};
    in >> height >> width;
    if (!in)
        return roomcount;
    std::vector<std::size_t> tracker(width, 0);
    for (auto i{height}; i; --i) {
        std::string row;
        in >> row;
        if (row.size() != width) {
            in.setstate(std::ios::failbit);
            return roomcount;
        } 
        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]) {
                        if (tracker[j-1] < tracker[j]) {
                            tracker[j] = tracker[j-1];
                            --roomcount;
                        } else if (tracker[j] < tracker[j-1]) {
                            // set all contiguous areas to the left
                            for (auto k{j-1}; k; --k) {
                                if (tracker[k]) {
                                    tracker[k] = tracker[j];
                                } else {
                                    break;
                                }
                            }
                            --roomcount;
                        }
                    }
                } else {
                    // continuation from left?
                    if (j && tracker[j-1]) {
                        tracker[j] = tracker[j-1];
                    } else {
                        tracker[j] = ++roomcount;
                    }
                }
            } else {
                tracker[j] = 0;
            }
        }
    }
    return roomcount;
}


int main() {
    auto r = rooms(std::cin);
    while (std::cin) {
        std::cout << r << '\n';
        r = rooms(std::cin);
    }
}

test.in

5 8
########
#..#...#
####.#.#
#..#...#
########
9 25
#########################
#.#.#.#.#.#.#.#.#.#.#.#.#
#########################
#.#.#.#.#.#.#.#.#.#.#.#.#
#########################
#.#.#.#.#.#.#.#.#.#.#.#.#
#########################
#.#.#.#.#.#.#.#.#.#.#...#
#########################
3 3
...
...
...
3 3
###
...
###
3 3
###
###
###
7 9
#########
#.#.#.#.#
#.#.#.#.#
#.#...#.#
#.#####.#
#.......#
#########
5 8
########
#..#.#.#
##.#.#.#
#..#...#
########
7 8
########
#..#.#.#
##.#.#.#
#..#...#
########
#..#...#
########
7 9
#########
#.#.#.#.#
#.#.#.#.#
#.#.#.#.#
#.#.#.#.#
#.......#
#########
7 9
#########
#.#.##..#
#.#.##.##
#.#.##..#
#.#...#.#
#...#...#
#########
7 9
#########
#.#.....#
#.#.###.#
#.#...#.#
#.#####.#
#.......#
#########
7 9
#########
#.......#
#.#####.#
#.#.#.#.#
#.#.#.#.#
#.......#
#########

Results

Running the program as rooms <test.in produces this expected result:

3
47
1
1
0
2
2
4
1
1
1
1
\$\endgroup\$
  • \$\begingroup\$ What constitutes a room? Maybe I’m just not seeing the bit that defines when a hallway suddenly meets room criteria. Also, I haven’t had a chance to fully analyze your source, but one stand-out for me to answer the “extend to 3D” question is to rename the height to length. \$\endgroup\$ – Ian MacDonald Jul 23 '18 at 13:53
  • \$\begingroup\$ It might be easier to use a modified path-finding algorithm, and then instead of setting a goal, mark all blocks (the periods) that were touched as it "tries" to find the goal until it gives up. When it gives up, store the flagged blocks as a segment, then repeat for all remaining non-flagged blocks individually. The # mark would represent a wall, for example. \$\endgroup\$ – alexyorke Jul 23 '18 at 14:02
10
\$\begingroup\$

This is called connected component analysis or labeling in the image processing literature. There are many algorithms that try to make this more efficient. You’re only counting regions, not assigning a unique label (i.e. room number) to each region, so you can get away with a somewhat simpler algorithm than I’m used to seeing.

You’ve already got comments on your coding style, I won’t go there again. But you also asked about a 3D extension, and I can give suggestions for that.

A straight-forward extension of your code to 3D would require to store the previous plane (2D data for the previous z coordinate) as well as the previous line. This gets complicated quickly, and will make it impossible to generate an algorithm that works with an arbitrary number of dimensions.

If you are indeed after an algorithm that would work with any number of dimensions, I’d suggest storing the whole floor plan and using a standard labeling algorithm. They’re only a little bit more complicated that what you’re doing, but assign a label to each room element. You’d have a Union-Find data structure to keep track of labels. For each new element you look at all connected elements (the neighbors in the grid) that have already been processed (this is a fixed list of offsets). If any of them has a label, assign the same label to this element. If another one also has a label, set the equivalence between the two labels in your Union-Find data structure.

The very efficient implementations optimize the order in which neighbors are examined, noting that certain neighbors need not be examined at all under certain configurations.

To learn more about these algorithms, look at YACCLAB. It is explicitly 2D, but you can see all the different approaches people have taken here. I wrote a dimensionality-independent version, you can see the code here.

\$\endgroup\$
  • \$\begingroup\$ Yes! Using a proven algorithm instead of trying to hack it together in an ad-hoc way leads to success. \$\endgroup\$ – Deduplicator Jul 22 '18 at 22:52
  • 1
    \$\begingroup\$ Sure, but that presumes one knows the proven algorithm. I didn’t, but now I do. \$\endgroup\$ – Edward Jul 22 '18 at 23:15
  • 1
    \$\begingroup\$ @Edward ...which is why I wrote the above. :) \$\endgroup\$ – Cris Luengo Jul 22 '18 at 23:25
10
\$\begingroup\$

Unfortunately, it does not work correctly. The output is 0 (zero rooms) for the floor plan

4 6
######
#.#..#
#....#
######

After parsing the second row, the room count is two and the tracker vector is

010220 

Then, when parsing the third row

#....#

the room count is decremented twice from two to zero.

Another example: For

7 22
######################
##..##..####..#......#
###....#...##...#....#
#........#.#....#....#
#...#......#..#...####
###.#..#.....#....#.##
######################

your program computes 18446744073709551615 rooms (and 3 rooms with the modification from https://codereview.stackexchange.com/a/200070/35991). The correct result is 2 rooms.

\$\endgroup\$
  • \$\begingroup\$ Would forcing the output to 1 in case of apparant 0 fix it? I mean, what does it mean to have 0 rooms anyway? Even if there's only one room and it's not fully enclosed, are there really 0 rooms? Of-course, in this challenge I assume the test cases will always be enclosed. But if the algorithm only fails in 1 specific case and it should always be from 0 to 1, a bandaid may just be all you need. \$\endgroup\$ – Mast Jul 23 '18 at 7:22
  • \$\begingroup\$ @Mast: It is not just one specific case, I just found (and added) another failure case. I have therefore removed by suggested “fix,” it does not help. Actually I am starting to doubt if this approach can be salvaged at all. \$\endgroup\$ – Martin R Jul 23 '18 at 7:36
7
\$\begingroup\$

I found another problem with the code that isn't quite addressed by @Martin R's approach. Here's an example that shows the problem:

7 9
#########
#.#.#.#.#
#.#.#...#
#.#...#.#
#.#.#.#.#
#.......#
#########

The correct answer is 1 room, but with both the original and the suggested change, I get 18446744073709551615 (equivalent to -1 on my 64-bit machine). The corrected version of the first if clause is this:

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);
        --roomcount;
    }
} else {

Update

Because the code above still failed for some inputs, I changed the algorithm slightly to separately track rooms and merges. Using that, a new variable std::size_t merges{0}; is added to the top of the routine and instead of --roomcount; above, the line is now ++merges;. The final change is to change the line from return roomcount; to return roomcount-merges;

I am now writing an automated tester to verify this.

Update 2

The automated tester, reworked (and apparently bug free) version of this code and an independently derived flood-fill version are now all written, tested and posted here: Multithreaded testing for counting rooms from a floor plan solution

\$\endgroup\$
  • 1
    \$\begingroup\$ You are right, my proposed change does not work correctly, I have therefore removed it from my answer. Unfortunately, this does not work either, see the additional failure case in my answer. \$\endgroup\$ – Martin R Jul 23 '18 at 7:38
  • \$\begingroup\$ Alas, you’re right. \$\endgroup\$ – Edward Jul 23 '18 at 11:00
  • \$\begingroup\$ I've updated this answer to (maybe?) fix the code yet again. Maybe this time it will really work! :) \$\endgroup\$ – Edward Jul 23 '18 at 12:35
6
\$\begingroup\$

Any hints on style or any other aspect of the code would be welcome as well.

Since you explicitly ask for style advice:

  std::istream &in

& belongs with the type in C++ as I'm sure you know so maybe this was just a sort of typo.

   if (!in)
       return roomcount;

I know it's tempting to omit braces for short statements but you're playing with fire everytime you do it. Try to always include them even in short non-production code.
(Many people leave them out as they are a nuisance to type. If that's case you could make a macro in your favorite text editor to add braces via a shortcut so you have no more excuses for dropping them)

   std::size_t

It's good to see that you properly prefix every occurrence of size_t unfortunately you did not include <cstddef>. It does get pulled in by every other header you include but you should not rely on that and always include things you use.

\$\endgroup\$
  • 2
    \$\begingroup\$ @MartinR Generally & and * belong with the type in C++ so it would be std::istream& in. I can't find an explicit guideline for it but if you take a look at this you can see it in action. \$\endgroup\$ – yuri Jul 22 '18 at 19:32
  • 1
    \$\begingroup\$ @MartinR here is another attempt at explaining it. \$\endgroup\$ – yuri Jul 22 '18 at 19:38
  • 3
    \$\begingroup\$ “you're playing with fire everytime you do it” — unfounded claim: there is no evidence that omitting the braces leads to more errors. Notable anecdotes are just that: anecdotes, not evidence. Omitting the braces makes the code terser and removes syntactic clutter so it’s at least plausible that the opposite of your claim is the case. \$\endgroup\$ – Konrad Rudolph Jul 23 '18 at 9:27
  • 1
    \$\begingroup\$ @KonradRudolph I'd rather not fall victim to goto fail style bugs but I'm sure smart scientists such as yourself are not prone to making such silly mistakes anyways so go right ahead. \$\endgroup\$ – yuri Jul 23 '18 at 14:36
  • 1
    \$\begingroup\$ @yuri “Goto fail” is that anecdote. There’s simply no evidence that braces would avoid this class of errors. In the particular case of “goto fail”, the error was most likely caused by a wrongly resolved merge conflict, and using braces would simply not have prevented this bug. The whole point is that this is regardless of whether one is prone to making silly mistakes. In other words, besides being an anecdote, “goto fail” doesn’t even show a situation in which braces would definitely have helped. \$\endgroup\$ – Konrad Rudolph Jul 23 '18 at 15:04
2
\$\begingroup\$

In terms of style, this should be a class with named functions that do specific jobs. This will make the code much easier to read, maintain, and adapt.

Code like this:

            } else {
                // continuation from left?
                if (j && tracker[j-1]) {
                    tracker[j] = tracker[j-1];
                } else {
                    tracker[j] = ++roomcount;
                }
            }

... would be far clearer like this:

void continue_count_from_left() {
    if (j && tracker[j-1]) {
       tracker[j] = tracker[j-1];
    } else {
       tracker[j] = ++roomcount;
    }
}
            ...
            } else {
                continue_count_from_left(); // or a better name
            }
            ...

You can also remove comments this way (which is a sign your code is clearer).

I just split that one section into a function. Putting everything in a class would be far better.

\$\endgroup\$

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.