Demonstration of Find Vowel Square

Question

Have the function VowelSquare(strArr) take the strArr parameter being passed which will be a 2D matrix of some arbitrary size filled with letters from the alphabet, and determine if a 2x2 square composed entirely of vowels exists in the matrix. For example: strArr is {{"a","b","c","d"},{"e","i","k","r"}, {"o","u","f","j"}} then this matrix looks like the following:

$$\begin{array}{cccc} a & b & c & d \\ \color{red}e & \color{red}i & k & r \\ \color{red}o & \color{red}u & f & j \\ \end{array}$$

Within this matrix there is a 2x2 square of vowels starting in the second row and first column, namely, ei, ou. If a 2x2 square of vowels is found your program should return the top-left position (row-column) of the square, so for this example your program should return 1-0. If no 2x2 square of vowels exists, then return the string not found. If there are multiple squares of vowels, return the one that is at the most top-left position in the whole matrix. The input matrix will at least be of size 2x2.

Are there any improvements I can make in terms of readability?

bool must_be_2x2(std::vector<std::vector<std::string>>& letters)
{
    constexpr int MIN_SIZE = 2;
    if (letters.at(0).size() > MIN_SIZE && letters.at(1).size() > MIN_SIZE)
    {
        return true;
    }

    return false;
}

std::string matrix_vector_to_string(std::vector<std::vector<std::string>>& matrix)
{
    std::string str;

    for (int row = 0; row < matrix.size(); ++row)
    {
        for (int col = 0; col < matrix.at(row).size(); ++col)
        {
            str += matrix.at(row).at(col);
        }
    }

    return str;
}

bool alphabet_only(std::vector<std::vector<std::string>>& letters)
{
    std::string str = matrix_vector_to_string(letters);

    for (std::size_t pos = 0; pos < str.length(); ++pos)
    {
        if (!std::isalpha(str.at(pos)))
        {
            return false;
        }
    }

    return true;
}

bool equal_length(std::vector<std::vector<std::string>>& letters)
{
    const size_t SIZE = letters.at(0).size();

    for (std::size_t row = 1; row < letters.size(); ++row)
    {
        if (letters.at(row).size() != SIZE)
        {
            return false;
        }
    }

    return true;
}

bool is_vowel(std::string element) noexcept
{
    static const auto vowels = std::array<std::string,5> { "a","e","i","o","u" };

    return std::find(vowels.begin(), vowels.end(), element) != vowels.end();
}

std::string find_vowel_square(std::vector<std::vector<std::string>>& letters)
{
    for (std::size_t row = 0; row < letters.size()-1; ++row)
    {
        for (std::size_t col = 0; col < letters.at(row).size()-1; ++col)
        {
            if (is_vowel(letters.at(row).at(col)) && is_vowel(letters.at(row).at(col + 1)) && is_vowel(letters.at(row + 1).at(col)) && is_vowel(letters.at(row).at(col + 1)))
            {
                return std::to_string(row) + "-" + std::to_string(col);
            }
        }
    }

    return "not found";
}

Answer 1

The #1 improvement you can make for code readability is adding comments. Plain code, even the most expressive plain code, rarely makes any sense on its own. In addition to comments, a use case showing the code in action is very helpful. Tests, too.

As for the code itself:

bool must_be_2x2(std::vector<std::vector<std::string>>& letters)

Vectors of vectors are rarely a good idea, and never a good idea for matrices. If you want a 2×2 matrix, you have to allocate three vectors: the vector for the matrix itself, then one vector per row. If you fail to properly allocate every row vector, you'll probably end up triggering UB.

Plus, accessing elements is slow. When you want to access an element of a vector of vectors, first the base vector has to be accessed and loaded... then the row vector has to be accessed or loaded. That's twice as many dives into main memory, which is painfully slow. And cache misses are more likely because a vector of vectors takes up more memory.

You can see the headaches yourself right in the code of must_be_2x2()... which, by the way, I think you have messed up the logic. A 2×2 matrix done as a vector of vectors would look like { { a, b }, { c, d } }. There are at least three ways to have a matrix less than 2×2:

1. { { a, b } }: a 1×2 matrix.
2. { { a }, { b } }: a 2×1 matrix.
3. { { a, b }, { c } } or { { a }, { c, d } }: a ragged row matrix with 2 rows, and one row with 2 elements while the other row has 1 element.

must_be_2x2() ultimately "correctly" detects all 3 failure conditions (and I put "correctly" in quotes because it doesn't correctly work, but we'll get to that)... but it only seems to do so by a fluke. If I pass in a 1×2 matrix like case 1, this function will not return false... it will throw an exception. That's because you check the size of row 1 and row 2... but you never check that there are actually 2 rows. If there are 0 rows, calling letters.at(0) or letters.at(1) will throw; if there is only 1 row, calling letters.at(1) will throw.

So for the function to work the way I think you want it to work - and I'm only guessing at that because, as mentioned, no comments to explain the intention - you would first need to test letters.size()... and only then check letters.at(0).size() and letters.at(1).size().

But there are a couple of other bugs in the function.

First, you should take the parameter by const reference, not non-const reference. You're not changing the input.

Second, MIN_SIZE shouldn't be an int. Vector's size() returns the vector's size_type, which will be unsigned, so you will be comparing signed and unsigned types... which is a big no-no.

Third, and most concerning: you are testing the size of each row as letters.at(N).size() > MIN_SIZE. That means that a 2×2 matrix will fail. Because 2 > 2 is not true. I think you really meant to use >=.

The "fixed" function might look like this:

bool must_be_2x2(std::vector<std::vector<std::string>> const& letters)
{
    constexpr std::vector<std::vector<std::string>>::size_type MIN_SIZE = 2;
    // or for less typing:
    // constexpr decltype(letters.size()) MIN_SIZE = 2;

    if (letters.size() >= MIN_SIZE && letters.at(0).size() >= MIN_SIZE && letters.at(1).size() >= MIN_SIZE)
    {
        return true;
    }

    return false;
}

But as I said, this still smells, because if you are dealing with matrices, vectors of vectors is a terrible structure. It's bloated, it's slow, and it's extra work because you have to maintain that each row is the same size.

When you need a multidimensional matrix in C++, the best solution is almost always to use a flat array or vector, and calculate the offsets yourself. You could wrap it in a class for easier use. To give the basic idea:

template <typename T>
class matrix2d
{
public:
    matrix2d(std::size_t rows, std::size_t cols) :
        _elements(rows * cols),
        _rows{rows},
        _cols{cols}
    {}

    auto element(std::size_t row, std::size_t col) -> T&
    {
        return _elements[_calculate_offset(row, col)];
    }

    auto rows() const noexcept { return _rows; }
    auto cols() const noexcept { return _cols; }

private:
    auto _calculate_offset(std::size_t row, std::size_t col) noexcept
    {
        return (row * _cols) + col;
    }

    std::vector<T> _elements;
    std::size_t _rows;
    std::size_t _cols;
};

With a matrix class like this (obviously filled out with all the useful methods you'll need), you should see significant performance gains. And your code can be much simpler. The bottom line is: don't use vectors of vectors - they're almost always the wrong choice.

std::string matrix_vector_to_string(std::vector<std::vector<std::string>>& matrix)

This function "works"... but is highly inefficient.

First, again, you should take the parameter by const reference.

But the real issue is that you are repeatedly concatenating strings. Each time you do this, you could be triggering a new memory allocation, copying the whole string, then a deallocation.

Instead, it might be worthwhile to figure out in advance how much memory in total you're going to need. For that you'll need two loops:

std::string matrix_vector_to_string(std::vector<std::vector<std::string>> const& matrix)
{
    auto size = std::string::size_type{0};
    for (auto&& row : matrix)
        for (auto&& elem : row)
            size += elem.size();

    std::string str;
    str.reserve(size);
    for (auto&& row : matrix)
        for (auto&& elem : row)
            str += elem;

    return str;
}

On to the next function.

bool alphabet_only(std::vector<std::vector<std::string>>& letters)

Now, this function - like the previous function - "works", but it is extremely inefficient. First you construct a string of all the strings in the matrix concatenated, and then check that everything in that is a letter. But... why? Why create the concatenated string? Why not just check the letters in the matrix?

bool alphabet_only(std::vector<std::vector<std::string>> const& letters) noexcept
{
    for (auto&& row : letters)
    {
        for (auto&& elem : row)
        {
            for (auto c : elem)
            {
                if (!std::isalpha(static_cast<unsigned char>(c)))
                    return false;
            }
        }
    }

    return true;
}

On to the next function:

bool equal_length(std::vector<std::vector<std::string>>& letters)

This function's name isn't exactly clear. What it's doing is verifying that every row of the matrix is the same length. The only reason this is necessary at all is because you're using a vector of vectors.

bool is_vowel(std::string element) noexcept

This function has a lot of problems.

First of all, the parameter should probably be passed by const reference, not by value.

Second, it can't really be noexcept. Inside the function you construct an array of 5 strings. The string constructors are not noexcept. (One would hope that the string uses the small-string optimization. But one shouldn't rely on it like this.)

Which leads to the question of why you're dealing with strings at all. As far as I can tell, you're dealing with only ASCII characters. You don't need strings for this. This function could take a char, and do the test using a static array<char, 5>. That would be noexcept, and a lot faster.

std::string find_vowel_square(std::vector<std::vector<std::string>>& letters)

Once again, this "works", but is not particularly efficient. It's a brute force search, which is bad enough, but what's particularly bad is that it's a brute force search over a vector of vector of strings. I don't think you could have chosen a more inefficient data structure if you'd tried.

Changing to a better data structure alone - like a vector<char> (possibly wrapped in a matrix class) instead of vector<vector<string>> - should net you significant benefits. In the worst case scenario, with a large enough data set that it won't all in cache, and a string without SSO, you could be looking at a speed-up of several thousand times.

But changing to a more efficient algorithm would be the biggest gain (especially because doing that would automatically mean changing to a better data structure). You don't need to read the entire matrix in to search for sub-matrices. In fact, you don't really need to store any part of the matrix at all.

All you need to do is create a vector of flags (call it flags) of the size of one matrix row. Then you read the first matrix row, and for each element that is a vowel, set the corresponding flag in the flag vector. Then for each subsequent row i, start by setting another flag (not one in the vector, call it previous_is_vowel_column) to false, then for each character j, if it is a vowel and flag[j] is true and previous_is_vowel_column is true... you're done. The result is to_string(i - 1) + '-' + to_string(j - 1). Otherwise, you set to previous_is_vowel_column to true if the current character is a vowel and flag[j] is true, and set flag[j] to true if the current character is a vowel, and move on. If you get to the end without a success, then you return the fail message.

Answer 2

Use AAA style (Almost Always Auto)

There are several places where you can use auto to help make sure the variable's type is correct, make the code more flexible to type changes, and/or save typing. For example:

const size_t SIZE = letters.at(0).size(); // in equal_length()
std::string str = matrix_vector_to_string(letters); // in alphabet_only()

Use the right type

Your compiler should warn you about signed/unsigned integer comparisons in these for loops:

for (int row = 0; row < matrix.size(); ++row)
{
    for (int col = 0; col < matrix.at(row).size(); ++col)
    {
        str += matrix.at(row).at(col);
    }
}

Although auto won't help you here (since you are initializing to 0, which is an int) you can use decltype (e.g. decltype(matrix.size()) instead of int for row).

In some cases it is possible to use range-based for loops to make the code even shorter and allow the use of auto, as @indi's answer shows:

for (auto&& row : matrix)
    for (auto&& elem : row)
        size += elem.size();

Use type aliases

You are using std::vector<std::vector<std::string>> for your matrices and most of your functions accept an argument of that type. You can use a type alias such as

using Matrix = std::vector<std::vector<std::string>>;

to reduce the required typing, make the code easier to read, and make the code more flexible to changes (e.g. if you change the matrix type to a flat array or vector as @indi suggests).

Avoid verbosity

This can be made less verbose:

if (letters.at(0).size() > MIN_SIZE && letters.at(1).size() > MIN_SIZE)
{
    return true;
}

return false;

A more concise equivalent is simply

return letters.at(0).size() > MIN_SIZE && letters.at(1).size() > MIN_SIZE;