7
\$\begingroup\$

Inspired by recent questions about counting the rooms in a floor plan (1, 2, 3), here is my attempt to solve the problem with a Swift program.

The problem (from “Counting Rooms” on CSES) is:

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

I took this as an opportunity to learn about “disjoint-set data structures” (also called “union-find data structures”). Here is my implementation, it follows closely the pseudo-code from the Wikipedia page. The only difference is that the parent of the “representative” (or “root”) does not point to itself, but is nil.

UnionFind.swift

class UnionFind {

    var parent: UnionFind?
    var rank: Int

    init() {
        self.parent = nil
        self.rank = 0
    }

    // Find with path compression
    func find() -> UnionFind {
        if let parent = self.parent {
            let p = parent.find()
            self.parent = p
            return p
        }
        return self
    }

    // Combine the trees if the roots are distinct.
    // Returns `true` if the trees were combined, and
    // `false` if the trees already had the same root.
    @discardableResult func union(with other: UnionFind) -> Bool {
        var xRoot = self.find()
        var yRoot = other.find()

        if xRoot === yRoot {
            return false
        }

        if xRoot.rank < yRoot.rank {
            swap(&xRoot, &yRoot)
        }

        // Merge yRoot into xRoot
        yRoot.parent = xRoot
        if xRoot.rank == yRoot.rank {
            xRoot.rank += 1
        }
        return true
    }
}

The main code is highly inspired by Efficiently counting rooms from a floorplan (version 2):

  • The data is read from standard input, and can be more than one floor plan.
  • For each column we keep track of the room to which the field at the current row and this column belongs to. Here we use the UnionFind structure.
  • If a field is a continuation from both left and top then the two tracker values are combined with union().

main.swift

import Foundation

func readDimensions() -> (height: Int, width: Int)? {
    guard let line = readLine() else { return nil }
    let ints = line.split(separator: " ")
    guard ints.count == 2,
        let height = Int(ints[0]),
        let width = Int(ints[1]) else {
            return nil
    }
    return (height, width)
}

func readMapAndCountRooms(height: Int, width: Int) -> Int? {
    var tracker = Array<UnionFind?>(repeating: nil, count: width)
    var roomCount = 0

    for _ in 0..<height {
        guard let line = readLine(), line.count == width else { return nil }
        for (offset, field) in line.enumerated() {
            if field == "." {
                if let top = tracker[offset] {
                    // Continuation from the top ...
                    if offset > 0, let left = tracker[offset - 1] {
                        // ... and from the left:
                        if top.union(with: left) {
                            roomCount -= 1
                        }
                    }
                } else if offset > 0, let left = tracker[offset - 1] {
                    // Continuation from the left:
                    tracker[offset] = left
                } else {
                    // New room:
                    tracker[offset] = UnionFind()
                    roomCount += 1
                }
            } else {
                // A wall:
                tracker[offset] = nil
            }
        }
    }
    return roomCount
}

while let (height, width) = readDimensions(),
    let count = readMapAndCountRooms(height: height, width: width) {
        print(count)
}

For the input data

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

this produces the (correct) output

1
1
1
3
47
1
1
0
2
2
4
1
1
1
1

Any feedback on the code is welcome, in particular:

  • This is my first experiment with union-find data structures. Is it correctly implemented? Can it be simplified?
  • Is the main program logic correct or can you spot any errors?
\$\endgroup\$
  • \$\begingroup\$ A question about the code: Does tracker[offset] = UnionFind() allocate a new bit of memory to store the object? I presume so, and I presume that var parent: UnionFind? is a reference of sorts, otherwise the algorithm wouldn't work. If this is the case, it would be more efficient (presumably) to keep an array of UnionFind elements, and refer to them by their index instead. \$\endgroup\$ – Cris Luengo Jul 23 '18 at 15:47
  • 1
    \$\begingroup\$ @CrisLuengo: Yes, UnionFind() returns a “reference” to a newly allocated object. Swift has “automatic reference counting,” which essentially means that the compiler generates to code to increase and decrease reference counts as appropriate. So you can pass references around, copy them etc. The object is deallocated when no reference exists anymore. – Implementing the tree as (automatically memory managed ) “nodes” with pointers to the parent was convenient and is my first approach to this topic. I'll try your suggestion when I find the time. \$\endgroup\$ – Martin R Jul 23 '18 at 16:22
4
\$\begingroup\$

Not a full review, I don’t know Swift at all. I just wanted to comment on the union-find implementation.

I’ve seen this a lot, keeping track of the rank, it never found it useful. When you are comparing the rank to determine which of the two labels should be the parent, you have just find()ed the two elements, meaning that you are looking at two roots by definition, and whatever elements you have visited along the way all now point directly at these two roots.

However, the rank is not updated when flattening the tree, so it is not an indication of tree depth. Keeping track of the rank seems (in my experience) to be more costly than the measly improvement in tree depth you might achieve.

A second issue (which I learned from your helpful comment) is that you're building a tree allocating each node separately. Considering that these nodes only store a pointer, dynamic allocation is relatively expensive. In my experience, storing tree nodes in an array can be very beneficial, especially if they are small. In this case, instead of a pointer to the parent node, you can simply store its index. The benefit extends beyond avoiding all those separate allocations: an array has better cache locality, and reference counting adds a bit of overhead as well.

So, combining these two changes, the data structure becomes a simple array of integers. The root points to itself, as an easy way of indicating it is a root. You could just as well store a negative index in the roots, but then it is necessary to always test the index before accessing the parent.

As you commented, the drawback with such an implementation is that it is not possible to recover nodes no longer referenced. The array keeps growing as the algorithm progresses. Many algorithms have such a compromise between memory use and speed. Reclaiming unused memory takes time. But do note that it is possible to compute the maximum number of elements the Union-Find data structure can possibly contain, given the size of the map under consideration: for \$n\$ map elements, there can be at most \$n/2\$ single-element rooms, and therefore that is the maximum number of elements that can be pushed into the data structure. It is therefore not prohibitive to allocate the array for the maximum size right from the start, and save a bit on additional tests and reallocations.

I wrote a blog post about the Union-Find algorithm recently, describing a C++ implementation.

Lastly: do time and compare before making any decisions! My experience might be different than yours. :)

\$\endgroup\$
  • \$\begingroup\$ Indeed: I made some benchmarks with random 2500x2500 maps, and could not observe a significant difference between using rank or not. \$\endgroup\$ – Martin R Jul 23 '18 at 17:48
  • \$\begingroup\$ I just tried a new implementation based on your crisluengo.net/index.php/archives/913#more-913 blog post, and that turned out to be much faster (factor 5 to 8 for a 2500x2500 map). The only thing I wonder about is the memory consumption: In my implementation, nodes which are not referenced anymore (i.e. rooms which are not reachable anymore) are deallocated automatically. Your vector-based approach is faster, but the std::vector<int> A; only grows and never shrinks. \$\endgroup\$ – Martin R Jul 23 '18 at 18:28
  • \$\begingroup\$ @MartinR: Yes, that is true, the array keeps growing and never shrinks, many of the elements in it are no longer used. There is a compromise there between speed and memory usage. Re-claiming memory during the running of the algorithm takes time. Note that you can determine the maximum number of elements this vector can potentially have: in your case of edge-neighbors (each element has 4 neighbors), you can have up to N/2 unique labels, with N the number of elements in the input matrix. That is not a whole lot of memory, and you can allocate such an array from the start to prevent reallocation. \$\endgroup\$ – Cris Luengo Jul 23 '18 at 18:38
  • \$\begingroup\$ Your above advice to “keep an array of UnionFind elements, and refer to them by their index instead” – in connection with your blog post – turned out to be essential for me to understand the algorithm better and implement it faster. Could you add that information to your answer? \$\endgroup\$ – Martin R Jul 23 '18 at 18:45
  • \$\begingroup\$ @MartinR: Happy to oblige. \$\endgroup\$ – Cris Luengo Jul 23 '18 at 19:12

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.