1
\$\begingroup\$

I've create a program that finds mixed duo within a string. It removes characters from a string that do not form the first mixed duo. It does not rearrange the order of the string, it ony remove characters to reveal the mixed duo...... aka "abababab", "chchchchc", "!s!s!s!".

What is a mixed duo? It is the combination of 2 characters repeating in oscillating fashion. for example the string "@@byb:b4bb:4b:4@@ybbb@b@:@@4" mixed duo would be ":4:4:4:4 because upon removal of every other character these two characters confirmed to the condition. @b does not form a mixed duo from the string because removal of all other character form this string forms "@@bbbbbb@@bbb@b@@@". It is not a repeating pattern of the first 2 characters otherwise it would look like this "@b@b@b@b@b@b@b"

Tell me what do you think of this code? Is my solution too complex? is it too slow?, is the code messy? is it maintainable?, am I following industry norms? Your honest opinion and critique of my style, logic, and approach is what I desire.

Below is an example of input and output.

input: @@byb:b4bb:4b:4@@ybbb@b@:@@4

output: :4:4:4:4

#include <map>
    #include <set>
    #include <list>
    #include <cmath>
    #include <ctime>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <limits>
    #include <vector>
    #include <climits>
    #include <cstring>
    #include <cstdlib>
    #include <fstream>
    #include <numeric>
    #include <sstream>
    #include <iostream>
    #include <algorithm>

struct Data{
    std::map<char,char> data1;
    std::string data2;
};

bool finalVerification(std::string input){
    ////////////////
    //DECLARATIONS//
    ////////////////
    int size_Of_String;

    char a; 
    char b;

    //When flip = true a fails, when flip = false b fails;
    bool flip;


    ///////////////////////
    //  INITIALIZATION   //
    ///////////////////////
    size_Of_String = input.size();

    a = input[0]; 
    b = input[1];

    //When flip = true a fails, when flip = false b fails;
    flip = false;

    //////////////////////////////
    //RULE CHECKING BEFORE LOGIC//
    //////////////////////////////
    //Last minute condition check
    if(input.size() < 4){return false;}
    if(input.size() == 4){
        if((input[0] == input[2])&&(input[1] == input[3])){ return true;}
        else {return false;}
    }

    //////////////////
    //IMPLEMENTATION//
    //////////////////
    //Go through the string array from both ends. 
    for(int i=0; i<size_Of_String; i++)
    {       
        if((input[i] != a) && (flip == false))
        {       
            return false;
        }
        else if((input[i] != b ) && (flip == true))
        {
            return false;
        }

        if(flip == true)
        {
            flip = false;
        }
        else if (flip == false) {
            flip = true;
        }
    }

    return true;
}
Data findUniqueChar(std::string input)
{
    ////////////////
    //DECLARATIONS//
    ////////////////
    int size_Of_String;
    int run_Through;

    std::string temp; 

    std::map<char, char> records; 

    Data output;

    ///////////////////////
    //  INITIALIZATION   //
    ///////////////////////
    size_Of_String = input.size();
    run_Through = size_Of_String;

    temp = "";


    //////////////////
    //IMPLEMENTATION//
    //////////////////

    //Find all the unique characters and record them in this map. 
    for (int i=0; i<run_Through; i++){
        if(input[i] != input[0])
        {
            //Assume this can form a twisted pair with the first element. 
            if(records.find(input[i]) == records.end()){
                records[input[i]] = '0';
                temp += input[i];
            }
        }
    }
    output.data1 = records;
    output.data2 = temp;
    return output;
}
std::string quickCheckFix(std::string input)
{
    ///////////////
    //DECLARATION//
    ///////////////
    int size_Of_String;
    std::string output;
    char tmp;

    ///////////////////////
    //  INITIALIZATION   //
    ///////////////////////
    size_Of_String = input.size();
    output = input;

    //////////////////
    //IMPLEMENTATION//
    //////////////////
    //Go through the string array from both ends. 
    for(int i=0; i<size_Of_String/2; i++)
    {       
        //If duplicates are encountered remove all instances of that character from the string and break out of the loop
        if(output[i] == output[i+1])
        {       
            tmp = output[i];
            output.erase(std::remove(output.begin(), output.end(), tmp), output.end()); 
            break;
        }
        else if(output[size_Of_String - 1 - i] == output[size_Of_String - 2 - i])
        {
            tmp =  output[size_Of_String - 1 - i];
            output.erase(std::remove(output.begin(), output.end(), tmp), output.end()); 
            break;
        }
    }

    //Call yourself again if output has been changed. set output to equal the value of the call. Use the altered output as the argument,
    if(output !=  input){
        output = quickCheckFix(output);
    }

    return output;
}
std::string condition(std::string input)
{   ////////////////
    //DECLARATIONS//
    ////////////////
    int size_Of_String;

    std::string output;
    std::string pair_Values;
    std::string saved_Failures;

    //False = alpha fail, true = omega fails
    Data records;
    ///////////////////////
    //  INITIALIZATION   //
    ///////////////////////
    size_Of_String = input.size();

    output = input;
    pair_Values += input[0];  
    pair_Values += input[1];
    saved_Failures = "";

    // bool keys were replaced with chars key for more options. 0 = false, 1 = true, X = failure! 
    records = findUniqueChar(input);

    //////////////////
    //IMPLEMENTATION//
    //////////////////
    for(int i=0; i<size_Of_String; i++)
    {   
        //----------------------------------//
        //--------Ender conditions----------//
        //----------------------------------//


        //If there are no more unique characaters that could succeed it is finally safe to remove the 1st element from the string. 
        if(saved_Failures.size() == records.data2.size()){
            //Free yourself from the loop first
            break;
        }



        //---------------------------------------//
        //--------Logic and computation----------//
        //---------------------------------------//

        //If the first elements was encountered again
        if(input[i] == input[0])
        {   
            //Record all true key as failures
            for(int a=0; a<records.data1.size(); a++)
            {

                    if(records.data1.find(records.data2[a])->second == '1'){
                        saved_Failures += records.data2[a]; 
                        records.data1[records.data2[a]] = 'X';
                    }

            }
            //Change all the false keys to true
            for(int a=0; a<records.data1.size(); a++)
            {

                    if(records.data1.find(records.data2[a])->second == '0'){
                        records.data1[records.data2[a]] = '1';  
                        pair_Values[1] = input[i];
                    }

            }
        }       
        else if(records.data1.find(input[i])->second == '1'){       //If the key was found again while being true flip the value to false.
                records.data1[input[i]] = '0'; 
                pair_Values[1] = input[i];
        }
        else if(records.data1.find(input[i])->second == '0'){    //If the key was found again while being false record it as failure.
                saved_Failures += input[i]; 
                records.data1[input[i]] = 'X'; // Will never get in the loop again
        }
    }

    //If if failed go ahead and remove the first element instances and call your friend again.
    if(saved_Failures.size() == records.data2.size()){
        output.erase(std::remove(output.begin(), output.end(), input[0]), output.end()); 
    }
    //If you think it succeeded remove all other characters. 
    else{
        //Remove the 1st element character from this string 
        saved_Failures.erase(std::remove(saved_Failures.begin(), saved_Failures.end(), input[0]), saved_Failures.end()); 
        //Start from the top and work your way to the bottom.
        for(int i=0; i<saved_Failures.size(); i++){
            output.erase(std::remove(output.begin(), output.end(), saved_Failures[i]), output.end()); 
        }       
    }


    return output;   
}
std::string findPair(std::string input)
{   
    ///////////////
    //DECLARATION//
    ///////////////
    std::string output;
    std::string pair_Values;

    ////////////////////////////////////////////////
    //RULE CHECKING BEFORE LOGIC & INITIALIZATION //
    ////////////////////////////////////////////////
    //Check if the string size is invalid
    if(input.size() < 4){return "";}

    //If the string is valid see if you can cut it down to size before processing. Apply rule 1 again in case you got lucky
    input = quickCheckFix(input);
    if(input.size() < 4){return "";}

    //Super lucky condition just to save more time. 
    if(input.size() == 4){
        if((input[0] == input[2])&&(input[1] == input[3])){ return input;}
        else {return "";}
    }

    ///////////////////////
    //  INITIALIZATION   //
    ///////////////////////
    //Only munipulate the output string, and begin the set up for the logic loop
    output = input;
    pair_Values += output[0];
    pair_Values += output[1];

    //////////////
    //  LOGIC   //
    //////////////

    output = condition(output);

    //If the function return false, it is on
    switch(finalVerification(output)){
    case true: break;
    case false: output = findPair(output);
    }


    return output;
}
void autoStringRead()
{
    ///////////////
    //DECLARATION//
    ///////////////
    std::ifstream inputs( "pairs-in.txt" );
    std::string line;
    std::string done; 
    std::ofstream results;


    ///////////////////////
    //  INITIALIZATION   //
    ///////////////////////
    //Generate the file
    results.open ("results.txt");

    //Make sure this exists
    if( inputs == NULL ) { return; }



    while (getline(inputs, line)) { 
        done = findPair(line);
        results << done <<std::endl;
        std::cout<< line << std::endl;
        std::cout<< done << std::endl;
    }

    inputs.close();
    results.close();
}

int main()
{
    autoStringRead();
    system("pause");
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Wasn't this just posted for review here: codereview.stackexchange.com/questions/206983/…? \$\endgroup\$ – πάντα ῥεῖ Nov 5 '18 at 14:50
  • \$\begingroup\$ Yes is was but I posted as a guest with limited access. I couldn't even reply. \$\endgroup\$ – Laurent Nov 5 '18 at 14:53
  • \$\begingroup\$ Certainly. I posted a description of what it means to be a mixed duo and how it is obtained. \$\endgroup\$ – Laurent Nov 5 '18 at 15:08
  • \$\begingroup\$ See below, I edited my answer (at the end) to put an example, tell me if it works as expected, I hope I understood your goal. \$\endgroup\$ – Calak Nov 6 '18 at 3:15
1
\$\begingroup\$

Algorithm

Your code does strike me as unnecessarily difficult to follow for the task it accomplishes.

Given that the final result needs to consist of alternating characters, I think I'd start by eliminating any characters that include any run of two or more:

std::string &remove_runs(std::string &input) { 
    std::string::iterator pos;

    while ((pos = std::adjacent_find(input.begin(), input.end())) != input.end())
    {
        char a = *pos;
        auto end = std::remove(input.begin(), input.end(), a);
        input.erase(end, input.end());
    }
    return input;
}

Then I'd generate a histogram, and eliminate all characters that didn't have at least one other character with the same overall count.

Then I'd generate the possible pairs from that set of possibilities.

std::vector<std::string> gen_pairs(std::string &input) { 
    constexpr auto max = std::numeric_limits<unsigned char>::max();

    std::array<std::size_t, max> counts{};

    for (char c : input)
        ++counts[c];

    std::map<std::size_t, std::string> result;

    for (int i=0; i<max; i++)
        if (counts[i] != 0)
            result[counts[i]].push_back(i);

    std::vector<std::string> ret;

    for (auto &s : result) { 
        if (s.second.length() > 1)
            ret.push_back(s.second);
        else {
            auto pos = std::remove(input.begin(), input.end(), s.second[0]);
            input.erase(pos, input.end());
        }
    }
    return ret;
}

Arguably, that's still not ideal. In particular, gen_pairs not only generates the possible pairs, but also modifies its input to remove characters that couldn't possibly form pairs. That's probably a violation of the single responsibility principle, but I'm not quite ambitious enough at the moment to fix that.

So, for your input, removing characters with runs gives us: "y:4:4:4y:4".

Then generate_pairs reduces the string to :4:4:4:4, and tells us that the only possible pair is 4:.

I believe at that point, we could re-run the code to remove runs, so if we previously had a substring something like byb:4, after the y was removed as not a candidate (because it had no pair) we'd remove the two bs because they now form a run.

Specification

It looks like it's entirely possible that a single input string could actually contain more than one "Mixed Duo". I'm not sure what you want to do in such a case.

For example, consider a case like: ":4:4:4:4'8'8'8'8". Both ":4" and "'8" seem to fit your specification. Perhaps the entire string has to be composed of the two chosen characters (in which case that string doesn't contain a Mixed Duo), but perhaps not (and it contains two Mixed Duos).

Code Style

Looking at some of the details of the code itself, there are a few things I'd change about how it's written as well. For example:

    if(flip == true)
    {
        flip = false;
    }
    else if (flip == false) {
        flip = true;
    }

...can be rewritten more simply as: flip = !flip;

Likewise:

if(input.size() < 4){return false;}
if(input.size() == 4){
    if((input[0] == input[2])&&(input[1] == input[3])){ return true;}
    else {return false;}
}

...can be rewritten rather more simply as:

return (input.size() == 4 )&& (input[0] == input[2])&&(input[1] == input[3]);
\$\endgroup\$
0
\$\begingroup\$

(repost of my previous reply)

A few nitpicks off the bat since you asked about messiness. First, use a tool (any tool) to automatically format your code. Your braces and indentation are all over the place. Second, I would remove all of the "section" comments from your code. It's obvious that, for example, the first few lines of your function are "declarations" You don't need a comment to tell you that.

Non-idomatic code

  • You have a habit of declaring all of your variables at the top of the function. This isn't necessary in C++ (or even modern versions of C). Most people agree that it's easier to read code where variables are simply declared where they are first used.

  • You are passing strings by value everywhere. It would be more idiomatic in C++ to either take function arguments as const references (const std::string&) and continuing to return strings or just take a mutable reference (std::string&) and mutate the string in-place, returning void.

  • This code stuck out to me:

switch(finalVerification(output)){ case true: break; case false: output = findPair(output); }

It's very unusual to switch over a boolean, especially when you don't do anything with the true case. You can re-write this as

if(!finalVerification(output) {
    output = findPair(output);
}

Naming

Function names like condition and quickCheckFix aren't very helpful to the reader. What the quickCheckFix function actually does is remove characters that occur next to themselves, so call it something like removeSelfAdjacent.

Verbosity

Generally, you're writing way more code than you need to. Your quickCheckFix is 42 lines, whereas the following function that does exactly the same thing is only 10.

//Removes all characters that occur next to themselves in the string.
void removeSelfAdjacent(std::string& input) {
    for(std::size_t i = 0; i < input.size() - 1; i++) {
        //If duplicates are encountered remove all instances of that character
        //from the string.
        if(input[i] == input[i + 1]) {
            output.erase(std::remove(output.begin(), output.end(), output[i]), output.end()); 
            --i; // Need to recheck the current character since we just removed it.
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Actually, in C++17 it's idiomatic to pass a std::string_view instead of a std::string const&. \$\endgroup\$ – Deduplicator Nov 5 '18 at 22:18
  • \$\begingroup\$ Ah, what a wonderful world you must live in where C++17 is actually used. I convinced my office that it was safe to move to this newfangled technology called C++11 barely a year ago. \$\endgroup\$ – Jason Watkins Nov 5 '18 at 22:21
  • 1
    \$\begingroup\$ Yes, if would be nice if one always could use the current standard, and there are myriad reasons, even undeniably valid ones, that might not happen. It might be worth mentioning that you restrict yourself to <insert standard version> with your recommendations, and why. Mentioning what the current (and maybe even next) revision would change might also be helpful. \$\endgroup\$ – Deduplicator Nov 5 '18 at 22:36
0
\$\begingroup\$

( repost of my previous reply)

Logic & Algorithm

Without valid and invalid input files and expected outputs, it's hard to know if your program do the job. So, I'll don't analyses the logic nor the general algorithm, but instead, point out issues that are problematic and highlight bad practices


Recurring misuses and errors

I haven't checked every headers, but i'm not sure you need all of those. And if you really need them for only one functionality you certainly have a design problem. I'll try to be as exhaustive that I can, but I see a lot of mistakes

  • You don't provide pairs-in.txt nor the expected results.txt, so it might be hard to poeple to figure out what your program do.
  • Make interfaces explicit. What is the purpose of finalVerification(...), quickCheckFix(...) or condition(...) ? Try to find self-explanatory names, program to an interface, not an implementation.
  • Don't declare variables at the top of your functions, try to keep their scope as small as possible. See here, here and here to get further information about this. Initialize your variables in the declaration.
  • All of your std::string parameters are given by value whereas you don't modify them, using a const& std::string of a const std::string_view is way better (among other things, in term of performance) and make your interface more explicit. More info here.
  • On the same subject, but extending it to all variables, when they don't have to be modified in their scope, make it const.
  • You write too much comment, code have to be self-explanatory. If so, do not use comments, otherwise try to keep them short. Really avoid these big blocks of comments like DECLARATION, INITIALIZATION, etc. And about long explanatory commentaries, think about this comment style.
  • Don't hard-code value that can be modified if your code can be reused.
  • When you open a file with a std::ifstream check success with std::ifstream::is_open instead of comparing with NULL, and do it directly. In addition, with c ++, you do not have to use NULL.
  • [You don't have to close an std::ifstream](https://stackoverflow.com/questions/748014/do-i-need-to-manually-close-an-ifstream) at the end of your function, it's what RAII is for. In case where you have a lot of code after manipulating your file and don't need it anymore, so manually close or, even better, enclose the file-manipulation part into curly braces to make a block scope.
  • Instead of while (getline(inputs, line)) if your input file contains only one word per line, use while (inputs >> line).
  • Don't use std::endl but '\n' and, if you want to manually flush the stream, explicitly call std::flush.
  • Don't use system(...) it's not portable, nor secure and incredibly slow.
  • Avoid to mix signed and unsigned operation (arithmetic or comparison). For info, std::string::size() return a std::string::size_type which basically is a std::size_t namely an unsigned integer.
  • You always wrongly compare flip to true or false, don't add redundant ==/!=
  • Don't use an inconsistent naming style. What is size_Of_String, a mix between snake and camelCase.
  • You never check std::string input length before accessing to 2 first indexes. Try to ensure your bounds safety.

Refactoring

Here some specifics advices and remarks about things I didn't talk about in the section above.

finalVerification

//When flip = true a fails, when flip = false b fails;
bool flip;

.....

//When flip = true a fails, when flip = false b fails;
flip = false;

should be rewrites in:

bool flip = false;

if(input.size() < 4){return false;}
if(input.size() == 4){
    if((input[0] == input[2])&&(input[1] == input[3])){ return true;}
    else {return false;}
}

can be rewrites in:

if (input.size() <= 4u) {
    return (input.size() == 4u && input[0] == input[2] && input[1] == input[3]);
}

    if((input[i] != a) && (flip == false))
    {       
        return false;
    }
    else if((input[i] != b ) && (flip == true))
    {
        return false;
    }

    if(flip == true)
    {
        flip = false;
    }
    else if (flip == false) {
        flip = true;
    }

can be rewrites in:

    if(flip)
    {
        if(input[i] != b)
        {
            return false;
        }
    }
    else if(input[i] != a)
    {
        return false;
    }

    flip = !flip;

But the whole function can be changed to:

// add headers <string_view> & <algorithm>
bool finalVerification(const std::string_view in) {
    std::size_t index = 0;
    return in.size() > 3 && std::all_of(cbegin(in) + 2u, cend(in),
                                        [&](auto c) { return c == in[index++]; });
}

findUniqueChar

You declare size_Of_String and run_Through as a copy of it (as integer instead of std::size_t, but anyway) but never modify run_Through of access to size_Of_String. Simply work with size_Of_String and remove run_Through.


findPair

You take input by value, never modify it, copy it to output. In your case, you can work directly on input.

You declare `std::string pair_Values;, assign two first chars from output, but never use it.

Otherwise:

if(input.size() < 4){return "";}

//Super lucky condition just to save more time. 
if(input.size() == 4){
    if((input[0] == input[2])&&(input[1] == input[3])){ return input;}
    else {return "";}
}

Can be rewrites t (notice the redundancy with the case above, with "" instead of false) :

if (input.size() <= 4u) {
    return (input.size() == 4u && input[0] == input[2] && input[1] == input[3]) ? input : "";
}

//If the function return false, it is on
switch(finalVerification(output)){
case true: break;
case false: output = findPair(output);
}

can be rewrites in:

if (!finalVerification(output)) {
  output = findPair(output);
}

condition

As for findPair you declare std::string pair_Values assign many times values, but never use it.


Final word

I have probably forgotten things and I haven't analyzed the logic of the program too much. I think you should turn to the few links I posted to improve your skills. Also, you should learn how to use the standard library, the different types and algorithms. Try to compile with all warnings and pedantic enabled, help the compiler to helping you.


Working code

I tried this to see if I understood what your program was doing. Tell me :) ( Test it online )

    #include <algorithm>
    #include <iostream>
    #include <string>
    #include <string_view>
    #include <utility>
    #include <vector>


    auto get_repeated_chars(const std::string_view input) {
        auto result = std::vector<char>{};
        auto start = input.data();
        auto end = start + input.size();
        while (start != end) {
            if (std::count(start + 1, end, *start) == 1) result.push_back(*start);
            ++start;
        }
        return result;
    }

    auto get_pairs(const std::string_view input) {    
        auto chars = get_repeated_chars(input);
        auto size = chars.size();
        auto result = std::vector<std::pair<char, char>>{};
        if (size < 2) return result;
        result.reserve(size * (size - 1) / 2);

        for (auto start = chars.data(), end = start + size; start != end; ++start) {
            for (auto middle = start + 1; middle != end; ++middle) {
                auto pair = std::minmax({*start, *middle});
                if (pair.first != pair.second && std::find(result.begin(), result.end(), pair) == result.end()) {
                    result.push_back(pair);
                }
            }
        }
        return result;
    }
    auto is_zigzag_string (const std::string_view input) {
        std::size_t index = 0;
        return input.size() > 3 && std::all_of(cbegin(input) + 2u, cend(input),
                                              [&](char c) { return c == input[index++] && c != input[index]; });
    }
    auto get_mixed_duo_string(const std::string_view input) {
        auto pairs = get_pairs(input);
        auto results = std::vector<std::string>{};
        for (const auto& pair: pairs) {
            auto filtered = std::string{};
            std::copy_if(input.cbegin(), input.cend(), std::back_inserter(filtered),
                        [pair](char c) {return c == pair.first || c == pair.second;});
            if (is_zigzag_string(filtered)) results.push_back(filtered);
        }
        return results;
    }
    void process(const std::string_view input) {
        auto list = get_mixed_duo_string(input);
        std::cout << "Duo strings for " << input <<": [\t";
        for (auto const& str : list) std::cout << str << "\t";
        std::cout << "]\n";
    }
    int main() {
        process("abcdefabcdfs");
        process("@@byb:b4bb:4b:4@@ybbb@b@:@@4");
        process("@@bbbbbb@@bbb@b@@@");
        process(":4:4:4:4'8'8'8'8");
        return 0;   
    }
\$\endgroup\$
  • \$\begingroup\$ This code accurately replicate my program's functionality and finds more than the first potential mixed duo. \$\endgroup\$ – Laurent Nov 6 '18 at 14:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.