Project Euler task 42

The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

-------------------------------------------------------------------------

#include

#include

const int MAXNAME = 100;

using namespace std;

__global__ void findTriangleWords(char * _dpNamesArray, char * _dpResult, int _iWordNum, int _iNameLength) {

int nThread = blockIdx.x * blockDim.x + threadIdx.x;

if (nThread >= _iWordNum)

return;

int iSum = 0;

// cycle through the letters

for (int i = 0; i < _iNameLength; i++) {

char c = _dpNamesArray[_iNameLength * nThread + i];

if (c == '\0')

continue;

iSum += (int) c - (int) 'A' + 1;

}

__syncthreads();

int iN = ((int) sqrt(float(1 + 4 * 2 * iSum)) - 1) / 2;

int tN = iN * (iN + 1) / 2;

if (tN == iSum)

_dpResult[nThread] = 1;

else

_dpResult[nThread] = 0;

}

int main() {

ifstream ifs("words.txt", ifstream::in);

char pName[MAXNAME];

size_t iMaxLen = 0;

int iWordNum = 0;

while (!ifs.getline(pName, MAXNAME, '"').eof()) {

if (pName[0] == ',')

continue;

size_t iLen = strlen(pName);

if (iLen > iMaxLen)

iMaxLen = iLen;

iWordNum++;

}

char * pNamesArray = new char[iMaxLen * iWordNum];

memset(pNamesArray, 0, sizeof(char));

ifs.clear();

ifs.seekg(0, ios_base::beg);

iWordNum = 0;

while (!ifs.getline(pName, MAXNAME, '"').eof()) {

if (pName[0] == ',')

continue;

if (!strlen(pName))

continue;

strncpy(&(pNamesArray[iWordNum * iMaxLen]), pName, iMaxLen);

iWordNum++;

}

ifs.close();

// now pNamesArray contains all the necessary names, calling kernel

char * dpNamesArray;

cudaMalloc(&dpNamesArray, iWordNum * iMaxLen * sizeof(char));

// sending array with words into GPU

cudaMemcpy(dpNamesArray, pNamesArray, iWordNum * iMaxLen * sizeof(char), cudaMemcpyHostToDevice);

char * dpResult;

cudaMalloc(&dpResult, iWordNum * sizeof(char));

int threadsPerBlock = 128;

int blocksNum = (iWordNum / threadsPerBlock) + 1;

findTriangleWords <<< blocksNum, threadsPerBlock >>> (dpNamesArray, dpResult, iWordNum, (int) iMaxLen);

// getting back the results from GPU

char * pResult = new char[iWordNum];

cudaMemcpy(pResult, dpResult, iWordNum * sizeof(char), cudaMemcpyDeviceToHost);

cudaFree(dpResult);

cudaFree(dpNamesArray);

// processing results pResult

int sum = 0;

for (int i = 0; i < iWordNum; i++)

sum += (int) pResult[i];

cout << sum << endl;

delete [] pResult;

delete [] pNamesArray;

return 0;

}