429,067 Members | 1,818 Online
Need help? Post your question and get tips & solutions from a community of 429,067 IT Pros & Developers. It's quick & easy.

# Project Euler 22 - What am I doing wrong?

 P: 26 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: Expand|Select|Wrap|Line Numbers #include  #include  #include    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! Dec 2 '10 #1
4 Replies

 Expert Mod 5K+ P: 8,916 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? Dec 3 '10 #2