Counting the number of domino tilings for a rectangular grid

Question

A domino tiling of a grid is a tiling of the grid using domino pieces. Below is a C++ program to count the number of possible tilings of a grid of a given size.

The program constructs the board row by row, representing each row as a string. In each row, d represents the top half of a domino pointing downwards, u represent the bottom half of a domino pointing upwards, r represents the left half of a domino pointing to the right, and l represents the right half of a domino pointing to the left.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class DominoTilingCounter {
    int height, width;
    bool done;
    int tilingCount;

    map<string, vector<string>> dictionary;

    vector<string> firstRow(int width) {
        vector<string> prev;

        prev.push_back("d");
        prev.push_back("r");

        for (int col = 1; col < width; col++) {
            vector<string> next;

            while (!prev.empty()) {
                string candidate = prev.back();
                prev.pop_back();

                switch (candidate.back()) {
                case 'd':
                case 'l':
                    next.push_back(candidate + 'd');
                    if (col != width - 1)
                        next.push_back(candidate + 'r');
                    break;
                case 'r':
                    next.push_back(candidate + 'l');
                    break;
                }
            }

            prev = next;
        }

        return prev;
    }

    vector<string> nextRows(const string& row) {
        if (dictionary.find(row) != dictionary.end())
            return dictionary[row];

        vector<string> prev;

        if (row.front() == 'd')
            prev.push_back("u");
        else {
            prev.push_back("d");
            if(row.length() > 1)
                prev.push_back("r");
        }

        for (int col = 1; col < row.length(); col++) {
            vector<string> next;

            while (!prev.empty()) {
                string candidate = prev.back();
                prev.pop_back();

                switch (row[col]) {
                case 'd':
                    if (candidate[col - 1] != 'r')
                        next.push_back(candidate + 'u');
                    break;
                case 'u':
                case 'r':
                case 'l':
                    if (candidate[col - 1] == 'r')
                        next.push_back(candidate + 'l');
                    else {
                        next.push_back(candidate + 'd');
                        if (col != row.length() - 1)
                            next.push_back(candidate + 'r');
                    }
                }
            }

            prev = next;
        }

        return prev;
    }

    int countTiling(int height, int width, const string& previousRow, int currentRow) {
        if (currentRow == height) {
            for (char cell : previousRow)
                if (cell == 'd')
                    return 0;
            return 1;
        }

        int count = 0;

        vector<string> rows;

        if (currentRow == 0)
            rows = firstRow(width);
        else
            rows = nextRows(previousRow);

        for (string row : rows)
            count += countTiling(height, width, row, currentRow + 1);

        return count;
    }

public:
    DominoTilingCounter(int height, int width) : height(height), width(width) {
        if (height <= 0 || width <= 0 || height * width % 2) {
            tilingCount = 0;
            done = true;
        }
    }

    int count() {
        if (!done) {
            tilingCount = countTiling(height, width, "", 0);
            done = true;
        }

        return tilingCount;
    }
};


int main() {
    DominoTilingCounter tc(4, 7);

    cout << tc.count() << endl;

    return 0;
}

Answer 1

Looks like a decent translation of your algorithm into C++. However, if you're looking for speed, this code is very "heavyweight".

• It uses strings such as "drldurlrld" to represent each row of the grid, when bit-strings would suffice. (If you mark each "d" with the bit 1, and everything else with the bit 0, you'll still have an unambiguous encoding. This trick is similar to the trick used by Eller's maze-generation algorithm.)

• It copies around vector<string> to memoize the "next possible rows" for a given row.

• It doesn't use move semantics.

---

Now, I said that your code memoizes "next possible rows" — this is the purpose of dictionary — but if you look closely, you'll see that the variable dictionary is unused!

I can tell from context that what happened is you forgot to add a single line of the form dictionary[row] = prev; at the end of nextRows. But if the compiler can't read your mind as well as I can, then you'll have to learn to be more on guard — otherwise your code will run slowly and you won't know why!

On the plus side, this one-line difference is nice because it means you can test your code with and without the memoization and see if the memoization is actually worth it. I think it will be worth it, but I'm not 100% sure.

---

    if (currentRow == height) {
        for (char cell : previousRow)
            if (cell == 'd')
                return 0;
        return 1;
    }

This code, which rejects tilings with dominos that stick off the bottom of the grid, is important enough that I would recommend putting a comment on it.

    if (currentRow == height) {
        // Count this tiling, unless it dangles off the edge of the grid.
        return (previousRow.find('d') == std::string::npos) ? 1 : 0;
    }

---

To address the lack of move semantics: There are a couple of places in firstRow where you make copies of strings (or even whole vectors of strings), when you actually don't care about the right-hand side of the assignment anymore and might as well just move the string (or vector) into the left-hand variable. For example:

    string candidate = prev.back();
    prev.pop_back();

    switch (candidate.back()) {
    // ...
    case 'r':
        next.push_back(candidate + 'l');
        break;
    }
}

prev = next;

Here once you've finished the switch statement you don't care about the value of candidate, so you could

next.push_back(std::move(candidate) + 'l');

to save a copy. (Yes, this will in fact do the efficient thing: see overload #11 on the cppreference page.)

And you certainly don't need to make a copy of next when you assign it to prev! Replace that vector copy with a quick vector move:

prev = std::move(next);

Move semantics are more subtle (and probably less important) than I'm making them sound here; I won't go into detail here. But there is no shortage of material for learning more about move semantics if you want/need to.

---

int count() {
    if (!done) {
        tilingCount = countTiling(height, width, "", 0);
        done = true;
    }

    return tilingCount;
}

This is a common anti-pattern I see in a lot of student code for some reason: you want to compute a value, so you make a ValueComputor class, give it a computeTheValue() method, and then add memoization so that the computeTheValue() method won't be so darn slow the second time you call it.

This is an anti-pattern because it takes a notionally const operation (counting the number of tilings) and makes it a non-const member function. That is, it breaks this reasonable-looking code:

DominoTilingCounter tc(4, 4);
const DominoTilingCounter& param = tc;
std::cout << param.count() << std::endl;  // oops! can't call count() on a const object!

But it's also super easy to fix. Just take that code that computes the number of tilings, and move it straight into the constructor of your class!

DominoTilingCounter(int height, int width) : height(height), width(width)
{
    if (height <= 0 || width <= 0 || height * width % 2) {
        tilingCount = 0;
    } else {
        tilingCount = this->countTiling(height, width, "", 0);
    }
}

int count() const { return tilingCount; }

Much cleaner! And a tiny bit faster in the case that you call count() multiple times, because you don't have to check done anymore. (And much slower in the case that you construct a DominoTilingCounter object and never call the count() method — but why on earth would you construct this single-purpose object if you're never going to use it?)

---

Now notice that you don't use this->height or this->width anywhere in the code — instead, you pass around the caller's original height and width as parameters. And with the refactoring above, you don't use done. So what you're left with here is a class DominoTilingCounter that is effectively the same thing as an int. So, get rid of the useless class!

int count_domino_tilings(int height, int width);

This is the function you want to be writing. There's no reason to drag object-orientation into it at all. Your main function had been multiple lines long because of the mutation involved (and honestly it's not clear from reading this code that all the expensive work occurs on line 2 — so that's another downside to the anti-pattern above)...

int main() {
    DominoTilingCounter tc(4, 7);
    std::cout << tc.count() << std::endl;
}

...but with a nice clean function, it becomes simply

int main() {
    std::cout << count_domino_tilings(4, 7) << std::endl;
}

With such a drastic savings in lines of code, you have room left over to write some test cases! :)