Finding pairs of non_vowels in C++

Question

I have a programming problem where I should make a program which will calculate the amount of pairs of letters (letters next to each other) which aren't 'a', 'e', 'i', 'o', 'u' (vowels).

Examples:

jas 0
olovo 0
skok 1 (sk)
stvarnost 4 (st, tv, rn, st)

Input consists of small letters which make a word not bigger than 200 characters, and the output should output the number of pairs of letters that aren't vowels (a, e, i, o, u).

Time limit:

1 sec

Memory limit:

64 MB

Examples provided in the problem I have been given:

Input skok
Output 1

However, when I enter the words 'skok' the program doesn't work (it seems to keep working in the background yet not displaying anything on screen). The word 'stvarnost' (reality) works however, displaying '4' - as given in the problem.

Out of 10 test-cases, two test-cases give me the right output, one gives me a wrong output, and seven other test-cases tell me I have exceeded my time-limit.

Now, I'd also like an advice on how I can avoid exceeding my given time-limit, and how to fix it in the program below.

Here's the code I've started:

#include <iostream>
#include <string.h>

using namespace std;

int main() {

    char zbor[200];
    cin.get(zbor, 200);
    int length = strlen(zbor);
    int j_value = 0;
    int check_pairs = 0;
    int pairs = 0;
    int non_vowels = 0;

    for (int i = 0; i < length; i++) {
        if (zbor[i] == 'a' || zbor[i] == 'e' || zbor[i] == 'i' || zbor[i] == 'o' || zbor[i] == 'u') {
            continue;
        } else {
            non_vowels++;
            for (int j = i + 1; j < length; j++) {
                if (zbor[j] == 'a' || zbor[j] == 'e' || zbor[j] == 'i' || zbor[j] == 'o' || zbor[j] == 'u') {
                    break;
                } else {
                    non_vowels++;
                    if (non_vowels % 2 != 0) {
                        check_pairs = non_vowels / 2 + 1;
                    } else {
                        check_pairs = non_vowels / 2;
                    }
                    if (pairs < check_pairs) {
                        pairs++;
                    }
                    j_value = j;
                }
            }
            i = j_value +  1;
        }
    }

    cout << pairs;

    return 0;
}

Edit:

#include <iostream>
#include <string.h>

using namespace std;

int main() {

    char zbor[200];
    cin.get(zbor, 200);
    int length = strlen(zbor);
    int pairs = 0;
    int non_vowels = 0;

    for (int i = 0; i < length; i++) {
        if (zbor[i] == 'a' || zbor[i] == 'e' || zbor[i] == 'i' || zbor[i] == 'o' || zbor[i] == 'u') {
            non_vowels = 0;
            continue;
        } else {
            non_vowels++;
            if (non_vowels >= 2) {
                if (non_vowels % 2 != 0) {
                    pairs = non_vowels / 2 + 1;
                } else if (non_vowels % 2 == 0) {
                    pairs = non_vowels / 2;
                }
            }
        }
    }

    cout << pairs;

    return 0;
}

Edited the code, using pieces of code of the answers below, (bruno's and Ozzy's) here's the final version which works:

#include <iostream>
#include <string.h>

using namespace std;

bool vowel(char c) {
    switch(c) {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
        return true;
    default:
        return false;
    }
}

int main()
{

    char zbor[200];
    cin.get(zbor, 200);
    int N = strlen(zbor);
    int non_vowels = 0;
    int pairs = 0;

    for (int i = 0; i < N; i++) {
        if (!vowel(zbor[i])) {
            non_vowels = 0;
        } else {
            non_vowels++;
            if (!vowel(zbor[i])) {
                non_vowels = 0;
            } else {
                non_vowels++;
                if (non_vowels > 1) {
                    pairs++;
                }
            }
        }
    }

    cout << pairs;

    return 0;
}

I don't see any question but it looks like a job for the debugger. — Quimby, Mar 13 '19 at 13:05
It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/) and [Debugging Guide](http://idownvotedbecau.se/nodebugging/) — NathanOliver, Mar 13 '19 at 13:09
you increment `non_vowels` each time you reach a non vowel, to check the parity doesn't allow to check the if non vowels are consecutive or not. Your algorithm is wrong — bruno, Mar 13 '19 at 13:12
@N.T. when you reach the first non vowel after vowels (or at the beginning of the _zbor_) start a new loop to count the consecutive non vowel after it and stop at end of _zbor_ or reaching a vowel. of course that second loop modify the index of the first. — bruno, Mar 13 '19 at 13:17
@bruno I tried simplifying it, I edited my comment, it's not working though because if I type 'jas' it outputs 1 instead of 0 so it's still a wrong algorhithm. — N.T., Mar 13 '19 at 13:38
@N.T. Honestly, you're overcomplicating the program. All you need to do is go through each adjacent pair of characters and if the pair matches the criteria, then add 1 to the count. All of this division by 2 is totally unnecessary. For example: `if (is_consanant(str[i]) && is_consanant(str[i+1])) ++numpairs;`. You just have to write the `is_consanant` function. — PaulMcKenzie, Mar 13 '19 at 13:40

score 2 · Answer 1 · answered Mar 13 '19 at 13:47

You could easily simplify your code by using C++ features, a proposal:

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

const std::array<char, 5> vowels = {'a', 'e', 'i', 'o', 'u'};

bool isVowel(char c)
{
    return std::find(vowels.begin(), vowels.end(), c) != vowels.end();
}

bool checker(char c)
{
    static bool lastFound = false;

    if (lastFound && !isVowel(c))
        return true;
    else
        lastFound = !isVowel(c);

    return false;   
}

int main()
{
    std::vector<char> v{'s', 'k', 'o', 'k', 'a', 'k'};

    int num_items = std::count_if(v.begin(), v.end(), &checker);

    std::cout << num_items << std::endl;
}

No need for the stateful `checker()` (how do you reset it for the next use?) if you simply use `std::adjacent_find()` instead. — Toby Speight, Mar 13 '19 at 14:15

score 2 · Answer 2 · answered Mar 13 '19 at 13:59

Here is a solution using std::adjacent_find:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

bool isConsonant(char c)
{
    static const char *vowels = "aeiou";
    return strchr(vowels, c)?false:true;
}

int main()
{
    std::string s = "stvarnost";
    auto it = s.begin();
    int count = 0;
    while (true)
    {
        // find the adjacent consonants
        auto it2 = std::adjacent_find(it, s.end(), 
                                     [&](char a, char b) 
                                     { return isConsonant(a) && isConsonant(b); });
        if ( it2 != s.end())
        {
            // found adjacent consonents, so increment count and restart at the next character.
            ++count;
            it = std::next(it2);
        }
        else
            break;
    }
    std::cout << count << "\n";
}

Output:

Live Example

score 2 · Answer 3 · answered Mar 13 '19 at 15:12

Here's a C++17 solution that uses string_view and adjacent_find. It's idiomatic C++, making it quite short and easy to understand.

#include <algorithm>
#include <iostream>
#include <string_view>
using namespace std;

bool checkPair(char a, char b)
{
    string_view vowels { "aeiou" };
    bool aNotVowel = vowels.find(a) == string_view::npos;
    bool bNotVowel = vowels.find(b) == string_view::npos;
    return aNotVowel && bNotVowel;
}

int main(int argc, char **argv)
{
    int pairs { 0 };
    string_view input(argv[1]);

    for(auto next = input.begin(); next != input.end();)
    {
        next = adjacent_find(next, input.end(), checkPair);
        if(next != input.end())
        {
            ++pairs;
            ++next;
        }
    }
    cout << pairs << endl;

    return 0;
}

bruno · Answer 4 · 2019-03-13T14:44:00.297

1

A proposal :

#include <iostream>

using namespace std;

bool vowel(char c)
{
    switch (c) {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
    case 'y':
        return true;
    default:
        return false;
    }
}

int main()
{
    string zbor;

    if (! (cin >> zbor))
        return -1;

    int pairs = 0;

    for (size_t i = 0; i < zbor.length(); ++i) {
        if (!vowel(zbor[i])) {
          int n = 0;

          do
            n += 1;
          while ((++i != zbor.length()) && !vowel(zbor[i]));

          pairs += n - 1;
        }
    }

    cout << pairs << endl;

    return 0;
}

Compilation and execution:

/tmp % g++ -pedantic -Wextra p.cc
/tmp % ./a.out
jas
0
/tmp % ./a.out
olovo
0
/tmp % ./a.out
skok
1
/tmp % ./a.out
stvarnost
4

edited Mar 13 '19 at 14:44

answered Mar 13 '19 at 13:40

bruno

32,421
7
25
37

What does the 'size_t' part mean? – N.T. Mar 13 '19 at 13:53
@N.T. `size_t`is the right type rather than _int_ or _unsigned int_ in a lot of cases, for instance `string::length()` returns `a size_t` – bruno Mar 13 '19 at 13:55
@N.T. Here, `size_t` is the same as `std::size_t` - note the nasty `using namespace std;` near the top (and read _[Why is “using namespace std” considered bad practice?](/q/1452721/)_). – Toby Speight Mar 13 '19 at 14:12
We're taught in school to use 'using namespace std;' so I am used to it, I'll change that habit though. – N.T. Mar 13 '19 at 14:28
@N.T. in 15 years of C++ I *never* had a problem because of `using namespace std;` ;-) – bruno Mar 13 '19 at 14:31
@N.T. you have 6 answers, now you have to decide the one you accept, and may be up vote some of the others you also like ? ^^ – bruno Mar 13 '19 at 14:36
@bruno Yeah... The only problem is that I'm still in my 1st year of high school, and many of these codes are still a bit confusing to me. I will try to understand at least one of them and try them. Thanks everyone for the help! – N.T. Mar 13 '19 at 14:40
I recommend placing the vowels into a string, then searching the string. If the letter is in the vowel string, it is a vowel. Possibly more efficient than the `switch/case` statement (at least less statements to type). – Thomas Matthews Mar 13 '19 at 14:46
@ThomasMatthews I was first thinking to use a string but for me the switch case is more efficient – bruno Mar 13 '19 at 14:48

Ozzy · Accepted Answer · 2019-04-02T08:21:36.743

1

Indeed, there are several things..

accessing zbor[i] could be very time consuming, because it always looks up the position i again for every comparison (unless the compiler optimizes some things)
the second for-loop is not needed, you can just count if the last entry was a vowel and that is all the info you need when going further through the string.
make use of c++ features like lambdas to make your code easier readable

.

auto isVowel = [](char& c) {return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';};

for (int i = 0; i < length; i++)
{
  if (isVowel(zbor[i]))
  {
    non_vowels = 0;
  }
  else
  {
    non_vowels++;

    if (non_vowels > 1)
      pairs++;
  }
}

cout << pairs;

edited Apr 02 '19 at 08:21

answered Mar 13 '19 at 13:58

Ozzy

64
4

Why do we check whether the same `zbor [i]` is a vowel twice after `non_vowels++`. – N.T. Mar 14 '19 at 09:41
Whups, good point. Edited the code, since non-vowels are never vowels :S – Ozzy Apr 02 '19 at 08:23

score 1 · Answer 6 · edited Jun 20 '20 at 09:12

Optimize time: When parsing strings (char *), pass through using "while" instead of getting the length and using "for". You get only 1 pass insteads of 2 (1 pass is already taken by strlen).
Optimize code: If you have code that repeats itself, either put it in a function or a macro.
Using the two points before, here is a sample code (you can handle the input management):

Sample

#include <iostream>
#include <cstddef>

using namespace std;

#define IS_VOWEL(a) ((a == 'a') || (a == 'i') || (a == 'u') || (a == 'e') || (a == 'o') || (a == 'y'))

int find_pairs(char * input, char ** stop_pos)
{
    char * input_cursor = input;

    while ((*input_cursor != 0) && IS_VOWEL(*input_cursor))
    {
        input_cursor++;
    }
    size_t used_count = 0;
    while ((*input_cursor != 0) && !IS_VOWEL(*input_cursor))
    {
        used_count++;
        input_cursor++;
    }
    *stop_pos = input_cursor;
    if (used_count < 2)
    {
        return 0;
    }
    else
    {
        return used_count - 1;
    }
}

int main()
{
    char input[] = "stvarnost";
    char * input_cursor = input;
    int found = 0;
    while (*input_cursor != 0)
    {
        found += find_pairs(input_cursor, &input_cursor);
    }
    cout << found << endl;
    return 0;
}

Have fun :)

Macros are evil. For example, what is the result of `IS_VOWEL(3.14159264)`? A function has better type checking. — Thomas Matthews, Mar 13 '19 at 14:49
You should prefer `std::string` as it is safer than character arrays. You can use `operator[]` to access characters in the string. — Thomas Matthews, Mar 13 '19 at 14:51
@ThomasMatthews I knwo macros aren't good, but it is just an example that has to be enhanced. For the string vs char arrays, if you check correctly the input you can work with it, also the whole logic behind the algorithm is pointer manipulations. — Meher Khiari, Mar 13 '19 at 16:23

score 1 · Answer 7 · answered Mar 13 '19 at 14:06

I think, for the requirement, you can make the program look more simpler like below, which I tested and working for the samples you've given. Instead of getting input, I tested by hardcoding input, which you can change:

#include <iostream>
#include <string.h>

using namespace std;

bool IsVowel(char ch)
{
    switch (ch)
    {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
    case 'A':
    case 'E':
    case 'I':
    case 'O':
    case 'U':
        return true;
        //break;
    default:
        return false;
    }

    return false;
}

int CountNonVowelPair(char* chIn)
{
        char zbor[200];
        //cin.get(zbor, 200);
        strcpy(zbor, chIn);
        int length = strlen(zbor);
        int j_value = 0;
        int check_pairs = 0;
        int pairs = 0;
        int non_vowels = 0;

        if (length <= 1)
            return 0;

        for (int i = 1; i < length; i++)
        {
            if (IsVowel(zbor[i - 1]) || IsVowel(zbor[i]))
                continue;
            else
                pairs++;
        }

        return pairs;
}

int main() 
{
    int nRet;
    nRet = CountNonVowelPair("jas");
    cout << nRet <<endl;
    nRet = CountNonVowelPair("olovo");
    cout << nRet <<endl;
    nRet = CountNonVowelPair("skok");
    cout << nRet <<endl;
    nRet = CountNonVowelPair("stvarnost");
    cout << nRet <<endl;

    return 0;
}

You can reduce the size of the `switch/case` statement by using `std::toupper` or `std::tolower`. Also, consider using `std::string` rather than character arrays, as arrays can overflow (or worse, they may not have a terminating nul character). — Thomas Matthews, Mar 13 '19 at 14:48

Finding pairs of non_vowels in C++

7 Answers7

Sample