One-dimensional Japanese puzzle

Question

I have been practicing competitive coding for a while now and am using codeforces.com. I recently encountered a problem called "One Dimensional Japanese Crossword" on that site. The problem is as follows:

The judge provides an integer (up to 100) and then a string with that many characters being either 'B' or 'W'. We need to output how many groups of 'B' there are and how many 'B's there are in each group. For example:

Input:

6
BBWBWB

Output:

3
2 1 1

---

After lots of tries and lots of fails, I was finally able to get the code accepted by the judge. However, for some reason I feel that my code is really inefficient and there might be an easier and better way to solve this problem.

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;

    int bGroups = 0;
    int wGroups = 0;

    char initChar = s[0];

    for (int i = 1; i < s.length(); i++)
    {
        if (initChar == 'B')
        {
            if (s[i] != initChar)
            {
                bGroups++;
                initChar = 'W';
            }
        }
        else if (initChar == 'W')
        {
            if (s[i] != initChar)
            {
                wGroups++;
                initChar = 'B';
            }
        }

    }

    if (s[n - 1] == 'B')
    {
        bGroups++;
    }
    else if (s[n - 1] == 'W')
    {
        wGroups++;
    }

    char init = s[0];
    vector<int>grpSize(bGroups);
    int counter = 0;
    int i = 0;
    while (counter < bGroups)
    {
        if (init == 'B')
        {
            while (init == 'B')
            {
                grpSize[counter]++;
                i++;
                init = s[i];
            }
            counter++;
            while (init == 'W')
            {
                i++;
                init = s[i];
            }
        }
        else
        {
            while (init == 'W')
            {
                i++;
                init = s[i];
            }
            while (init == 'B')
            {
                grpSize[counter]++;
                i++;
                init = s[i];
            }
            counter++;
        }
    }

    cout << bGroups << endl;
    for (int i = 0; i < bGroups; i++)
    {
        cout << grpSize[i] << " ";
    }
}

So basically, in the first pass over the string, I count how many groups of 'B' and 'W' there are. Then I create an int vector to store the size of each 'B' group. Then on the second pass I fill in the values into the vector and then output the results.

Answer 1

Code with iterators and standard algorithms, and you'll see your coding style improve dramatically:

• finding the beginning of a group of Bs can be done with std::find: auto b = std::find(first, last, 'B');

• finding the end of a group of Bs can also be done with std::find: auto e = std::find(b, last, 'W');

• computing the distance between the two is the job of std::distance: auto nb_bs = std::distance(b, e).

So combining all that we get:

#include <vector>
#include <algorithm>

template <typename Iterator>
auto groups_of_bs(Iterator first, Iterator last) {
    std::vector<int> result;
    while (true) {
        first = std::find(first, last, 'B');
        if (first == last) break;
        auto w = std::find(std::next(first), last, 'W');
        result.push_back(std::distance(first, w));
        if (w == last) break;
        first = std::next(w);
    }
    return result;
}

Now the only thing left is to display the size of the vector, and then its elements:

#include <string>
#include <iostream>

int main() {
    std::string test{"BBWBWB"};
    auto res = groups_of_bs(test.begin(), test.end());
    std::cout << res.size() << '\n';
    for (auto i : res) std::cout << i << ' ';
}

Answer 2

Here are a number of things that may help you improve your program.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers). In this particular case, it's not too terrible because it's a single short program and not a header. Some people seem to think it should never be used under any circumstance, but my view is that it can be used as long as it is done responsibly and with full knowledge of the consequences.

Make sure you have all required #includes

The code uses std::string but doesn't #include <string>. It's important to make sure you have all required includes to assure that the code compiles and runs portably.

Simplify your algorithm

The puzzle can be solved with a single pass through the data. Here's how this might be done:

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

std::vector<unsigned> count(const std::string &s, size_t n) {
    std::vector<unsigned> groups;
    bool withinBs{false};
    if (s.size() >= n) {
        for (size_t i{0}; i < n; ++i) {
            switch(s[i]) {
                case 'B':
                    if (withinBs) {
                        ++groups.back();
                    } else {
                        groups.push_back(1);
                    }
                    withinBs = true;
                    break;
                default:
                    withinBs = false;
            }
        }
    }
    return groups;
}

int main() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    auto groups{count(s, n)};
    std::cout << groups.size() << '\n';
    std::copy(groups.begin(), groups.end(), std::ostream_iterator<int>(std::cout, " "));
}

Answer 3

I will try to tell you what is wrong with your algorithm and why.

You do loop twice over the input string which is most certainly wrong

Your first loop does provide bGroups and wGroups as a result. We immediatly notice, that wGroups is not used at all and can be removed completely. bGroups is used only as limit in the second loop where you loop over all characters again and have to find all groups anyway. So why bother with finding them firsthand? If the second loop iterates over all characters (like the first one does) it can do the group search on its own and we can delete the first loop completely.

However your second loop contains nested while loops that do not stop at the last character. It needs to know the number of groups in advance. But it does not respect the length of the string anyway as it accesses s[s.size()] if the last character is a 'B'. This is guaranteed to be '\0' in C++14 (and thus different than 'B') but may work on older compilers just by accident. The bottom line is that your algorithm would be broken for a different container or of you were searching '\0' characters.

As a learning you should avoid parsing where states are represented by a position in a sequential code. Hold state in variables and have a single flat loop that can safely break.

You also can see your nested loop counting is wrong as there is code duplication. There is an if statement to have the very same code in a different order depending on the start character.

Try to format your code pretty

#include<iostream> should read #include <iostream>

Use std::string.size()

This is the standard how to determine the length of a container and iterate over it. It is a pretty bad idea to hold the length in a seperate variable that must match the actual length. Instead of

for (int i = 0; i < bGroups; i++)
{
    cout << grpSize[i] << " ";
}

The traditional container loop looks like

for (int i = 0; i < grpSize.size(); i++)
{
    cout << grpSize[i] << " ";
}

The modern range based loop - stick to that - looks like

for (const auto & n : grpSize) {
    cout << n << " ";
}

Do not construct a vector like an array

Instead of doing so and filling with the operator[]() you should use std::vector.push_back() to grow in size when you need.

Separate I/O from algorithm

Make a testable function without I/O that you call from main. The code should be structured somewhat like

std::vector<int> puzzle(std::string s)
{
    std::vector<int> grpSize;
    // ...
    return grpSize;
}

std::string input() {
    // ...
    return s;
}

void output(std::vector<int> v) {
    // ...
}

int main() {
    std::string s(input());
    output(puzzle(s));
}

using namespace std;

This line is found in many tutorials and even in IDE templates. You should use this very carefully in a limited scope only. Never use this in header files or before include lines as it may introduce name conflicts. When you fully understand this you may decide to use it in *.cpp files e. g. in an output function.

---

finally your algorithm should look somewhat like

std::vector<int> puzzle(std::string s)
{
    std::vector<int> grpSize;

    // as we are interested in 'B' groups only
    // we start in state 'W' to catch the first 'B'
    char state{'W'};

    for (const auto & c : s) {
        if (c == 'B') {
            if (state != 'B') {
                grpSize.push_back(0);
            }
            ++grpSize.back();
        }
        state = c;
    }
    return grpSize;
}