3
\$\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!".

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.

#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\$
4
  • \$\begingroup\$ "Is my solution too complex?" Yes. Can you tell us why you took the approach you did? Because a lot about your code is not obvious. \$\endgroup\$
    – Mast
    Nov 5, 2018 at 14:16
  • \$\begingroup\$ I was trying to achieve simplicity as my original solution was much more complex. I decided using recursion might simply the solution rather than using nested for loops. I also decided to speed up computation by not requiring a string to be re-read as often to determine if the first element of the string is apart of the first mixed duo of a string array. Finally I put everything in a more formatted way starting with declarations, initialization, and lastly computation. \$\endgroup\$
    – Laurent
    Nov 5, 2018 at 14:33
  • 1
    \$\begingroup\$ I haven't looked at all your code already (I'll take a true look later) but you include so much header. And your code can be simpler, more on that later. Can you edit your post to show some example with expected results? It will help to understand your logic. \$\endgroup\$
    – Calak
    Nov 5, 2018 at 14:39
  • \$\begingroup\$ Welcome to Code Review! I have rolled back the last edit (with the updated code). Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ Nov 6, 2018 at 0:59

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for the resources & critique. My diligent will create refinements to the up more standards. \$\endgroup\$
    – Laurent
    Nov 5, 2018 at 20:47
1
\$\begingroup\$

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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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