Problem with solving a distance to nearest vowel program

user_14191439 0
Viewed 320

I am trying to write a function that takes in a string and for each character, and returns the distance to the nearest vowel in the string. If the character is a vowel itself, return 0, but when I don't know what's wrong with my code as the first two elements in my s vector(that contains all the values of the answer) are working. The rest are simply returning as 0. What am I doing wrong?

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

std::vector<int> distance(std::string word){
    std::vector<char> r = {'a', 'e', 'i', 'o', 'u'};
    std::vector<int> s(word.length());
    for(int i = 0; i < word.length(); i++){
        if(std::find(r.begin(), r.end(), word[i]) == r.end()){
            for(int c = i + 1, d = i - 1; c < word.length() || d > 0; c++, d--){
                if(std::find(r.begin(), r.end(), word[c]) != r.end()){
                    s[i] = c - i;
                    break;
                }
                else if(d >= 0 && std::find(r.begin(), r.end(), word[d]) != r.end()){
                    s[i] = i - d;
                    break;
                }
            }
        }else s[i] = 0;
    }
    return s;
}

int main() {
  std::vector<int> h = distance("abbb");
    for(auto c : h){
        std::cout<<c<<"\n";
    }
}
c++
1 Answers

The power of algorithms and stateful Lambdas in modern C++ . . .

Please look at first at the code which calculates the result in O(2n):

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

// Function to calculate the distance to the nearest vowel
auto distanceToNextVowel(const std::string& s) {

    // Lambda to calculate if a character is a vowel
    auto isVowel = [](char c) { return (0x208222 >> (c & 0x1f)) & 1; };

    // Here we will store the resulting distance
    std::vector<size_t> dist(s.size());

    // Calculate distance from left and from right and use minimum
    std::transform(s.begin(), s.end(), dist.begin(), [&, i = s.size()](const char c) mutable { if (isVowel(c)) i = 0; else ++i;  return i; });
    std::transform(s.rbegin(), s.rend(), dist.rbegin(), dist.rbegin(), [&, i = s.size()](const char c, const size_t s) mutable { if (isVowel(c)) i = 0; else ++i;  return std::min(i, s); });

    // Return result to caller
    return dist;
}

// Test Driver
int main() {
    // This is our test string
    const std::string test{"Hello World"};

    // Caclcuate Result
    const auto dist = distanceToNextVowel(test);

    // Show result on console
    std::copy(test.begin(), test.end(), std::ostream_iterator<char>(std::cout, "\t")); std::cout << '\n';
    std::copy(dist.begin(), dist.end(), std::ostream_iterator<size_t>(std::cout, "\t")); std::cout << '\n';
    return 0;
}

Uuuh!? What's that?

This shows how wonderful problems can be solved in C++. But, it needs a lot of explanations. First, How to check, if a character is a vowel.

If we use the ASCII code to encode letters, then we will see the following:

Ascci Code for Letters

We see that the ASCII code for uppercase and lowercase letters just differ in the lower 5 bits. So, if we mask the ASCII code with 0x1F, so char c{'a'}; unsigned int x{c & 0x1F}, we will get values between 1 and 26. So, we can calculte a 5 bit value for each letter. If we now mark all vowels with a 1, we can build a binary number, consisting of 32bits (an unsigned int) and set a bit at each position, where the vowel is true. We then get something like

Bit position
3322 2222 2222 1111 1111 1100 0000 0000  
1098 7654 3210 9876 5432 1098 7654 3210  
Position with vowels:
0000 0000 0010 0000 1000 0010 0010 0010

This numer can be converted to 0x208222. And if we now want to find out, if a letter (regardless whether upper- or lowercase) is a vowel, then we mask out the not necessary bits from the chararcter ( C & 1F ) and shift the binary number to the right as much positions, as the resulting letter code has. If then the bit is set at the LSB position, then we have a vowel. This know how is decades old.

Aha. Not so easy, but will work for ASCII coded letters.

By the way, it would also work for other selections of characters.

the resulting Lambda is simple:

auto isVowel = [](char c) { return (0x208222 >> (c & 0x1f)) & 1; };

Cool . . .

Next, how to calculate the distance to/from the next vowel.

Let us start to think. If we go through the string from left to right, then we set the resulting index position to 0, if we found a vowel. Then, we simply count of for each consonant, until we hit the next vowel. This will work for counting from left to right. If the string does not start with a vowel, then we use some big indicator number, for example 999, because there is no distance in this direction. Example:

H   e   l   l   o       W   o   r   l   d
999 0   1   2   0   1   2   0   1   2   3

Next, if we use exactly the same algorithm from the right to the left, then we would get:

H   e   l   l   o       W   o   r   l   d
1   0   2   1   0   2   1   0   999 999 999

And the minimum distance, either from left or right is the minimum of the correspdonding values, either from left or from right. So

String:         H   e   l   l   o       W   o   r   l   d
Left:           999 0   1   2   0   1   2   0   1   2   3
Right:          1   0   2   1   0   2   1   0   999 999 999
Min of above:   1   0   1   1   0   1   1   0   1   2   3

And the last line is the result.

Now, we will use a statefull Lambda to calculate the first line:

std::transform(s.begin(), s.end(), dist.begin(), [&, i = s.size()](const char c) mutable { if (isVowel(c)) i = 0; else ++i;  return i; });

So, we will iterate ovver the string. From left to right. If we find a vowel, we set the distance to 0. If we found a consonant, we will increment the distance. The distance value is a state of the Lambda, which we initialize with a big value, here, the size of the string.

Then, next, we do the same from the right to the left. We will use the second form of the std::transform, where we can work with 2 source containers and create a new target. So, we will use the string, and the already (from left to right) calculated distance-vector and store the result again in distance-vector, because, we do not need a new one. The code is very similar:

    std::transform(s.rbegin(), s.rend(), dist.rbegin(), dist.rbegin(), [&, i = s.size()](const char c, const size_t s) mutable { if (isVowel(c)) i = 0; else ++i;  return std::min(i, s); });

The difference is that we iterate from right to left and store the minimum value of our just calculated distance and the already previously calculated distance.

That's it.

In main, we add some driver code and generate some output on the console.

I hope I could explain the algorithm in an understandable way.

In case of questions, please ask.

user_96660180
Related