Project Euler 22 - What am I doing wrong?

[liams]

So, a few days ago I decided to try Project Euler question #22. The question is:

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?


Now, I saved the file, and using the internets I found out that names.txt has 5163 names. Also, names.txt is formatted in the following manner: "John","George","Abe" etc. All in one line.
According to that, I built the following program:

#include <iostream>
#include <fstream>
#include <string>
 
using namespace std;
 
void swap (int& x, int& y)
{
    int holder = x;
 
    x = y;
    y = holder;
}
 
int main()
{
    string namelist;
    string temp;
    int sum;
    int counter = 0;
    unsigned long long total = 0;
    char alpha[26] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
    int values[5163];
 
    ifstream names ("names.txt");
 
    if (names.is_open())
        getline (names, namelist);
 
    names.close();
 
    for (long i = 0; i < namelist.length(); i += 3) //i += 3 to skip the commas and quotes
    {
        temp.clear();
        sum = 0;
 
        while (namelist[i+1] != '"')    //Loop character by character
        {
            temp += namelist[i+1];   //Build the string from individual characters
 
            for (int k = 0; k < 26; k++)  //Loop through alphabet, compare, save the sum
            {
                if (namelist[i+1] == alpha[k])
                        sum += k + 1;
            }
 
            i++;
        }
 
        values[counter] = sum;   //Save the sum in the values array
        counter++;
    }
 
    for (int i = 0; i < 5163; i++)
    {    
        for (int j = i; j < 5163; j++)
        {
            if (values[j] < values[i])   //Sort numerically, not alphabetically, as we are looking for numerical values
                swap(values[j], values[i]);
        }
    }
 
    for (int i = 0; i < 5163; i++)
        total += values[i] * (i + 1);  //Calculate the total
 
    cout << total << endl;
 
    return 0;
}

The code runs very fast, no compile errors. Only one problem - I'm getting the wrong result. What I'm getting:
996321502

I'm running Ubuntu. Compile: g++ -Wall 22.cpp

After a day of headaches, I decided to give up on it. Just now I thought why not ask here, because I really don't want my mistake to repeat itself.

So what's wrong? And how could I avoid this mistake in the future?

Thanks!

[Banfa]

How do you know 996321502 is the wrong answer? Do you know the right answer?

Clearly you do not think int holds enough bits to hold the total, are you sure that on your platform long long has more bits than int?

Also from line 64 will the result of values[i] * (i + 1) fit in an int if values[i] and i are both large?

Sorting by numeric value of the name will not put the name into alphabetic order. For example Zoe (26 + 15 + 5 = 46) is alphabetically after Colin (53) but numerically before it.

Finally you are using C++ so why are you using arrays instead of vectors?

[liams]

Yeah, I have the right answer, and it's not what I got. The right answer is about 11 digits if I remember correctly, and long long can hold much more. In line 64, it must fit because the answer, as I said, is about 10/11 digits.

And about the sorting.. I think you're right. I really didn't think about such a case. Thanks for that, I'll rewrite my code.

I'm using arrays because I know how large each one is going to be, and handling arrays directly is faster than using vectors. I only use vectors when I'm uncertain about certain things like capacity, number of elements, and dynamic handling.

Thanks for your answer... I'll see if I can get the right answer now. Will edit when I finish.

[Banfa]

It is a common myth that arrays are faster than vectors. Under optimisation they are more or less the same speed wise and obviously vectors have benefits from a memory management viewpoint.

That said if I know the required size I tend to use arrays but in this example I would do the following

• Make the array alpha constant, it is never altered in the code and making it constant adds a little protection as well as highlighting this for future maintenance.
• Make values a vector and then write a more general solution that didn't require knowing the number of names in the file in advance. In real life you rarely know this sort of quantity so writing the program like that makes it good practice.

[liams]

Thanks for the tips. But I'm really interested in how vectors can be more or less the same speed. I mean, arrays are approached directly and vectors are handled differently from what I understand. They're like manageable code, which should be making them slower since they are constantly checked for validity, and their size always changes. Doesn't all this make them slower?