8
\$\begingroup\$

Program description

The goal of this program is to get a number, which is the number of lines of inputs (lets call that number N) that the program will receive. Then the following N lines will consist of two parts, first a char which is either 'T' or 'M'. The next part will be a string that is a little different for 'T' and 'M'. If the char is 'T' then the string will consist of the following chars: '-', '+' and '0'. If the first char in the input line is 'M' then the following string can consist of the following chars: '-', '+', '0' and '?'.

When the line starts with a 'T', then the string will be stored. I store it in an array and the entries will be numbered from 1 to the number of entries.

When the line starts with an 'M', then the string will be compared to the list of strings that are stored to find out which of them that it matches best with.

The program will then output after each input line starting with 'M' the number associated with the stored string that the tested string matches best with. If there are more that each share the best match then it will output the one with the highest number associated with it.

The program check if the strings match from right to left.

If a string after an 'M' contains the char '?' it can be any char ('-', '+' and '0').

The way I build the program was by making an array for the stored strings, then making a function that can get a "match score" when trying to see which of the stored strings match best with the string being tested. If the match score is equal to the length of the tested string then it is the best possible match.

The program does not care about matching more then the chars in the tested string, so if we tried tried matching "0++--0" to "++0++--0" it would give os a match score of 6 which means it would be the best possible match.

Program execution

#include <iostream>

//For strcpy:
#include <stdio.h>
#include <string.h>
using namespace std;

//Gets match score for checking which match is the best of all. The highest match value is the best.
int getMatchScore(string matchCheck, string matchTarget)
{
    //Declares integers for length of matchCheck and matchTarget, and also for matchScore.
    int lenCheck=matchCheck.length(), lenTarget=matchTarget.length(),matchScore=0;
    //Declares int checkCounter and targetCounter, that has values lenCheck-1 and lenTarget-1 respectively used in while loop condition.
    int checkCounter=lenCheck-1, targetCounter=lenTarget-1;

    //If the length of the matchTarget is less than the length of matchCheck return 0.
    if(lenCheck>lenTarget){
        return 0;
    }

    //Declares char arrays for check and target so they can be compared.
    char matchCheckArr[50], matchTargetArr[50];

    //These two lines copy the strings for check and target into their respective char arrays.
    strcpy(matchCheckArr, matchCheck.c_str());
    strcpy(matchTargetArr, matchTarget.c_str());

    //While there are still elements in matchCheckArr:
    while(checkCounter>=0){

        //If matchCheckArr and matchTargetArr are the same (starting from the right going left) increment matchScore.
        if(matchCheckArr[checkCounter]=='?'){
            matchScore++;
        }

        else if(matchCheckArr[checkCounter]==matchTargetArr[targetCounter]){
            matchScore++;
        }

        //Decrement checkCounter and TargetCounter to move one spot to the left in the matchCheckArr and matchTargetArr arrays.
        checkCounter--;
        targetCounter--;
    }
    return matchScore;
}

int main()
{
    //Declares numInput for getting the number of inputs. Also declares targetCounter to hold the amount of data in targets array. tempLen to hold strInputHolders length.
    int numInput, targetCounter=0, tempLen;

    //Gets numInput from user.
    cin >> numInput;

    //Declares targets, that holds the data for checking against. Declares strInputHolder to hold string input when it needs to be checked against targets array.
    string targets[numInput], strInputHolder;

    //Declares inputHolder, that holds the char inputs temporarily.
    char inputHolder;

    //For loop for testing each line of input.
    for(int i=0; i<numInput; i++){
        //Takes the char that is in line of input and puts it in inputHolder.
        cin >> inputHolder;

        //Checks what char inputHolder is, if 'T' then do if statement if not ('M') do else statement.
        if(inputHolder=='T'){

            //Takes the string that follows the char in an input line and puts it in the targets array at the targetCounter position.
            cin >> targets[targetCounter];

            //Increments targetCounter so that the next input that goes to targets is placed in the right position.
            targetCounter++;
        }

        //Check comment at if statement.
        else{

            //Declares two ints, matchScoreHolder which is set to 0 because we will need to check if the current match score is bigger then matchScoreHolder.
            //Also declares targetPosition, which will hold the value of which target the match string matches best with.
            int matchScoreHolder=0, targetPosition;

            //Gets the string that follows the char in an input line and puts it in strInputHolder.
            cin >> strInputHolder;

            //Sets tempLen to the length of strInputHolder this will be temporary as strInputHolder will change for each input.
            tempLen=strInputHolder.length();

            //For loop that checks each target string against the current match string.
            for(int x=0; x<targetCounter; x++){

                /*Sets currentMatchScore to the number of chars that the current match string and the target string at the targetCounter-1-x position has in
                common (they have a char in common when they share the same char in the same position from right to left).*/
                int currentMatchScore=getMatchScore(strInputHolder, targets[targetCounter-1-x]);

                //Checks if currentMatchScore is greater then matchScoreHolder this is why we set matchScoreHolder to 0 to begin with.
                if(currentMatchScore>matchScoreHolder){

                    //Sets targetPosition to targetCounter-x, because we want the targetPosition to be the most accurate first of all, and then highest.
                    targetPosition=targetCounter-x;

                    //Sets matchScoreHolder to currentMatchScore since matchScoreHolder should hold the value of the highest match score.
                    matchScoreHolder=currentMatchScore;
                }

                //If matchScoreHolder is as high as it can possibly be for the current match string execute if statement.
                if (matchScoreHolder==tempLen){

                    //Sets targetPosition to the correct value.
                    targetPosition=targetCounter-x;

                    //Jumps out of loop, because we have found the highest possible match score and there is no reason to check the others.
                    goto matchOutput;
                }
            }

            //For goto matchOutput in last if statement in the last for loop in main (just above).
            matchOutput:

            //Outputs targetPosition and goes to a new line.
            cout << targetPosition << "\n";
        }
    }
}

So the code works, but it is way to slow. It needs to be able to take 50000 lines of input and be finished with outputting in 2 seconds. I don't really know how to improve on this.

Sample input/output:

 (input) 8
 (input) T 0--+0++-
 (input) M ?+0++-
(output) 1
 (input) M ?0++-
(output) 1
 (input) T ---0++0
 (input) M ?+0
(output) 2
 (input) T 0+
 (input) M +0?+-
(output) 1
 (input) T +-

The "(input)" and "(output)" are for showing which of the above are input and output, they are not apart of the actual input and output.

\$\endgroup\$
  • \$\begingroup\$ This is just a code dump with no explanation (even though your code has a lot of comments). What is the task that this code performs? Please tell us, and make that the title of the post. See How to Ask. \$\endgroup\$ – 200_success Feb 27 '17 at 18:16
  • \$\begingroup\$ I have now added a program description, I don't know what the title could be though. \$\endgroup\$ – ImSlake Feb 27 '17 at 18:45
  • \$\begingroup\$ Is 49 the maximum length of the strings? Is this a programming-challenge whose description is somewhere online? \$\endgroup\$ – 200_success Feb 27 '17 at 19:12
  • \$\begingroup\$ The limit is 50 chars, and yes it is a challenge, but only available in Danish and I would need to upload the file because it is only accessible if you have a specific password. But if you want it I could upload it somewhere and link it. \$\endgroup\$ – ImSlake Feb 27 '17 at 19:15
3
\$\begingroup\$

One thing I noticed with your existing code. This:

char matchCheckArr[50], matchTargetArr[50];

//These two lines copy the strings for check and target into their respective char arrays.
strcpy(matchCheckArr, matchCheck.c_str());
strcpy(matchTargetArr, matchTarget.c_str());

is redundant and a waste of resources, since you're only checking each char and matchCheck and matchTarget can each be accessed by indexing.

On a side note, goto is one of the worst programming structures ever created. There is nothing you can do with goto that can't be achieved with more reasonable structures. In your case a simple break statement will break out of the loop and execute the first line after the loop.

\$\endgroup\$
  • \$\begingroup\$ Okay so from now on, don't use goto, and strcpy is a waste of resources, if you can just access the chars in the string by indexing. Thanks a bunch! :) \$\endgroup\$ – ImSlake Feb 28 '17 at 7:37
  • \$\begingroup\$ Implementing those two made it run a lot faster, but not quite enough though. But it helped a lot! \$\endgroup\$ – ImSlake Feb 28 '17 at 7:59
0
\$\begingroup\$

I am answering very carefully here since I don't want to say anything stupid.

When trying to get brute forcing to better performance I would suggest on making the program thread-based. Assume you have a range of 100 numbers. The one you are searching for was, let's say, 70.

Then a normal algorithm would need 70 steps to find the correct number. When creating 2 threads, one could start at 0 and the other at 100. Now the second thread would only need 30 steps to terminate. By using 4 threads, starting at 0 (up), 49 (down), 50 (up), 100 (down), it would only take 20 steps for thread number 3.

I am not sure if this will help you, but I think the point made is clear. Hopefully you can port my poorly-made example to your program.

\$\endgroup\$
  • 1
    \$\begingroup\$ That seems like a good place to start, thanks for the answer. :) \$\endgroup\$ – ImSlake Feb 27 '17 at 17:27
  • \$\begingroup\$ I have thought about this. Would it not just take the same amount of time on average if you can only do one task at a time? I don't know how you would make it do more then one task at a time, and actually thread it. \$\endgroup\$ – ImSlake Feb 28 '17 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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