Click here to Skip to main content
15,889,808 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Hi, I have written a program, which works like 24 game puzzle i.e. from the given integer set and a target value, I list all the possible mathematical expressions to evaluate that target value.
Now, I want to modify this code using openMP in order to speedup the program. So, can anyone help me which code segments should be modified and how can it be done?

What I have tried:

C++
#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;


//All the Declaration of my functions
vector<int> getQuestion();


#define EMPTY -1
#define DIV 0
#define MUL 1
#define PLUS 2
#define MINUS 3


//Declare Global Constant
const string problemFile = "problem.txt";
const string answerFile = "answer.txt";
ofstream writeToAnswerFile(answerFile);


/* Following function is needed for library function qsort(). */
int compare(const void *a, const void * b)
{
	return (*(int *)a - *(int *)b);
}

// A utility function two swap two characters a and b
void swap(int* a, int* b)
{
	char t = *a;
	*a = *b;
	*b = t;
}

// This function finds the index of the smallest character
// which is greater than 'first' and is present in str[l..h]
int findCeil(int str[], int first, int l, int h)
{
	// initialize index of ceiling element
	int ceilIndex = l;

	// Now iterate through rest of the elements and find
	// the smallest character greater than 'first'
	for (int i = l + 1; i <= h; i++)
		if (str[i] > first && str[i] < str[ceilIndex])
			ceilIndex = i;

	return ceilIndex;
}


void releaseAnswerFile() {
	writeToAnswerFile.close();
}
//Main Program
int main() {
	writeToAnswerFile<<"-1"<<endl;
	writeToAnswerFile.close();
	atexit(releaseAnswerFile);
	vector<int> question = getQuestion();	//Retrieve Question from file

	int* questionArray = new int[question.size()]();
	char operatorList[] = { '/','*','+','-' };
	int targetAnswer = question.back();	//Get the final answer
	question.pop_back();	//remove the final answer from question list
	const int numberOfOperator = question.size() - 1;
	const int questionSize = question.size();
	bool hasAnswer = false;
	for (int i = 0; i < questionSize;i++) {
		questionArray[i] = question[i];
	}
	if (!question.empty()) {

		// Sort the string in increasing order
		qsort(questionArray, questionSize, sizeof(int), compare);

		//create dynamic allocation array
		int* tempOperationSequence = new int[numberOfOperator]();
		int* tempOperandSequence = new int[questionSize]();

		//algorithm starts for operands' permutation without duplication
		bool isFinished = false;
		while (!isFinished)
		{
			////////////////////////////////////////////////
			//brute force every operator combination algorithm start
			bool shouldContinueFindNewOperatorCombination = true;
			int* operationSequence = new int[numberOfOperator]();	//initialize the operand with all value 0
			operationSequence[0] = -1;
			int operatorPositionToChange = 0;
			bool containMultiplication = false;
			do {
				bool shouldSkipThisCombination = false;
				//generate next set of operand's combination
				if (++operationSequence[operatorPositionToChange] == 4) {
					for (int i = operatorPositionToChange; i < numberOfOperator;i++) {
						if (operationSequence[i] == 4) {
							operationSequence[i] = 0;
							if (i + 1 == numberOfOperator) {
								shouldContinueFindNewOperatorCombination = false;
								shouldSkipThisCombination = true;
								break;
							}
							operationSequence[i + 1]++;
						}
					}
				}
				operatorPositionToChange = 0;
				//Check Point 1
				if (shouldSkipThisCombination) {
					continue;
				}
				//Create a copy of operator array and operand array
				for (int operation = 0; operation < numberOfOperator;operation++) {
					tempOperationSequence[operation] = operationSequence[operation];
				}
				for (int operand = 0; operand < questionSize;operand++) {
					tempOperandSequence[operand] = questionArray[operand];
				}
				//Start the calculate the answer based on current set of operators and operands
				int finalResult;
				int fDigitPos = 0;	//First digit position
				int sDigitPos = 1;	//Second digit position

				//check all division operators first, if there are any invalid pairs, directly discard the whole combination
				for (size_t i = 0; i < numberOfOperator; i++) {
					if (tempOperationSequence[i] == DIV) {
						if (tempOperandSequence[i + 1] <= 0 || tempOperandSequence[i] % tempOperandSequence[i + 1] != 0) {
							operatorPositionToChange = i;
							shouldSkipThisCombination = true;
							break;
						}
					}
				}
				//Check Point 2
				if (shouldSkipThisCombination) {
					continue;
				}
				//entering the real calculation part
				//look for both multiplication and division operator
				for (size_t i = 0; i < numberOfOperator && fDigitPos != numberOfOperator; i++) {

					if (tempOperationSequence[i] == DIV) {
						if (tempOperandSequence[sDigitPos] > 0 && tempOperandSequence[fDigitPos] % tempOperandSequence[sDigitPos] == 0) {

							tempOperandSequence[fDigitPos] /= tempOperandSequence[sDigitPos];
							tempOperandSequence[sDigitPos] = -1;
							tempOperationSequence[i] = -1;
							sDigitPos++;
						}
						else {
							shouldSkipThisCombination = true;
							break;
						}
					}
					else if (tempOperationSequence[i] == MUL) {
						tempOperandSequence[fDigitPos] *= tempOperandSequence[sDigitPos];
						tempOperandSequence[sDigitPos] = -1;
						tempOperationSequence[i] = -1;
						sDigitPos++;
					}
					else {
						fDigitPos = sDigitPos;
						sDigitPos++;
					}
				}
				//Check Point 3
				if (shouldSkipThisCombination) {

					continue;
				}
				fDigitPos = 0;
				sDigitPos = 1;
				for (int i = 0; i < numberOfOperator;i++) {
					if (tempOperandSequence[i] != -1) {
						fDigitPos = i;
						sDigitPos = i + 1;
						break;
					}
				}
				//perform addition and subtraction
				for (size_t i = 0; i < numberOfOperator &&fDigitPos != numberOfOperator; i++) {

					if (tempOperationSequence[i] == EMPTY) {
						continue;
					}
					else if (tempOperandSequence[sDigitPos] == EMPTY) {
						i--;
						sDigitPos++;
						continue;
					}
					//Since plus and minus are the last section, no need to indicate used operands and operators is still ok
					else if (tempOperationSequence[i] == PLUS) {
						tempOperandSequence[fDigitPos] += tempOperandSequence[sDigitPos];
						sDigitPos++;
					}
					else if (tempOperationSequence[i] == MINUS) {
						tempOperandSequence[fDigitPos] -= tempOperandSequence[sDigitPos];
						sDigitPos++;
					}
				}
				//get the final result from array
				finalResult = tempOperandSequence[fDigitPos];
				//check result
				if (finalResult == targetAnswer) {
					//directly write answer into the file
					if(hasAnswer){
					
					writeToAnswerFile<<questionArray[0];
					for (size_t answerPos = 1; answerPos < questionSize; answerPos++) {
						writeToAnswerFile<<operatorList[operationSequence[answerPos - 1]];
						writeToAnswerFile<<questionArray[answerPos];
					}
					}else{
						hasAnswer = true;
						writeToAnswerFile = ofstream(answerFile,ios::trunc);
						
						writeToAnswerFile<<questionArray[0];
						for (size_t answerPos = 1; answerPos < questionSize; answerPos++) {
							writeToAnswerFile<<operatorList[operationSequence[answerPos - 1]];
							writeToAnswerFile<<questionArray[answerPos];
						}
					}
					
					writeToAnswerFile << endl;

				}
			} while (shouldContinueFindNewOperatorCombination);
			delete [] operationSequence;

			////////////////////////////////////////////////
			// Find the rightmost character which is smaller than its next
			// character. Let us call it 'first char'
			int i;
			for (i = questionSize - 2; i >= 0; --i)
				if (questionArray[i] < questionArray[i + 1])
					break;

			// If there is no such chracter, all are sorted in decreasing order,
			// means we just printed the last permutation and we are done.
			if (i == -1)
				isFinished = true;
			else
			{
				// Find the ceil of 'first char' in right of first character.
				// Ceil of a character is the smallest character greater than it
				int ceilIndex = findCeil(questionArray, questionArray[i], i + 1, questionSize - 1);

				// Swap first and second characters
				swap(&questionArray[i], &questionArray[ceilIndex]);

				// Sort the string on right of 'first char'
				qsort(questionArray + i + 1, questionSize - i - 1, sizeof(int), compare);
			}
		}
		delete[] tempOperationSequence;	//release dynamic allocation memory
		delete[] tempOperandSequence; //release dynamic allocation memory
		writeToAnswerFile.close();
	}

	return 0;
}

/***
getQuestion()
- Open Problem file and retrieve all the numbers from the file
return:
- vector<int> - List of Numbers

*/
vector<int> getQuestion() {
	vector<int> numbers;
	string line;
	ifstream opener;
	opener.open(problemFile);
	if (opener.is_open()) {
		while (getline(opener, line))
		{
			numbers.push_back(stoi(line));
		}
	}

	opener.close();
	return numbers;

}</int></int></int></int></int></vector></algorithm></fstream></string></iostream>
Posted
Updated 16-Jul-16 23:02pm
v2
Comments
Mehdi Gholam 17-Jul-16 2:22am    
Looks like homework.
Member 11465955 17-Jul-16 2:24am    
yes, sequential is assignment,,I done it aldy. but now I want learn it to parallel for test.
Kornfeld Eliyahu Peter 17-Jul-16 3:49am    
Put the code aside!!!
Think of the problem in abstraction and try redesign the algorithm to a parallel one... Can it be done at all?

1 solution

Making code parallel isnt always the solution, because it also makes overhead for that. Your primary task should be finding the slow parts of code and redesign them.

As I see you often writing in the writeToAnswerFile file. That looks like a bottleneck. I would try to store that information in a string and write if needed once if all is done.

C++
//Create a copy of operator array and operand array
for (int operation = 0; operation < numberOfOperator;operation++) {
  tempOperationSequence[operation] = operationSequence[operation];
}


I would replace
C++
memcpy(tempOperationSequence, operationSequence, operation);

on different places in your code.

The only thing for parallel is the sorting. Google for further information.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900