Project Euler: Problem 22 (2 versions)

Question

I wrote 2 versions of problem 22 on Project Euler:

Using a 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?

Any pointers (see what I did there) or tips on improving my code would be great.

V1: Simply computes and outputs the summed value:

#include <iostream>
using std::endl;
using std::cout;
#include <fstream>
using std::ifstream;
#include <string>
using std::string;
#include <vector>
using std::vector;
#include <algorithm>
using std::vector;
int main(void){
 vector<string> names;
 ifstream input("p022_names.txt");
 string tempName;
 while (getline(input, tempName, ',')){
 tempName.erase(tempName.begin());
 tempName.pop_back();
 names.push_back(tempName);
 }
 sort(names.begin(), names.end());
 names.shrink_to_fit(); //works with my compiler
 long ultimateTotal = 0;
 int i = 0;
 for (auto name : names){
 int sum = 0;
 for (int j = 0; j != name.size(); ++j){
 sum += (name[j] - 64);
 }
 ultimateTotal+=(++i*sum);
 }
 cout << ultimateTotal << endl;
 return 0;
}

V2: Outputs name, name alphabetical value, and name score to a file:

#include <iostream>
using std::endl;
using std::cin;
using std::cout;
#include <fstream>
using std::ifstream;
using std::ofstream;
#include <string>
using std::string;
#include <vector>
using std::vector;
#include <algorithm>
void formatInput(vector<string>&, ifstream&);
void alphaNumSum(vector<string>, vector<int>&);
void totalScore(vector<int>, vector<int>&);
void outputFinal(vector<string>, vector<int>, vector<int>, ofstream&);
int main(void){
 vector<string> names;
 ifstream input("p022_names.txt");
 formatInput(names, input);
 sort(names.begin(), names.end());
 names.shrink_to_fit();
 vector<int> alphSum;
 alphaNumSum(names, alphSum);
 vector<int> tScore;
 totalScore(alphSum, tScore);
 ofstream output("nameScores.txt");
 outputFinal(names, alphSum, tScore, output);
 return 0;
}
void formatInput(vector<string>& names, ifstream& input){
 string tempName;
 while (getline(input, tempName, ',')){
 tempName.erase(tempName.begin());
 tempName.pop_back();
 names.push_back(tempName);
 }
}
void alphaNumSum(vector<string> names, vector<int>& alphSum){
 for (auto name : names){
 int sum = 0;
 for (int j = 0; j != name.size(); ++j){
 sum += (name[j] - 64);
 }
 alphSum.push_back(sum);
 }
}
void totalScore(vector<int> alphSum, vector<int>& tScore){
 int score;
 int i = 1;
 for (vector<int>::iterator l_begin = alphSum.begin(); l_begin != alphSum.end(); ++l_begin, ++i){
 score = i * *l_begin;
 tScore.push_back(score);
 }
}
void outputFinal(vector<string> names, vector<int> alphSum, vector<int> tScore, ofstream& output){
 vector<string>::iterator begin = names.begin();
 vector<string>::iterator end = names.end() - 1;
 vector<int>::iterator l_begin = alphSum.begin();
 vector<int>::iterator l_end = alphSum.end();
 vector<int>::iterator score_begin = tScore.begin();
 vector<int>::iterator score_end = tScore.end();
 long long ultimateTotal = 0;
 for (/* n/a */; begin != end, l_begin != l_end, score_begin != score_end; ++begin, ++l_begin, ++score_begin){
 output << "NAME: " << *begin << "\tALPHNUMERIC SUM: " << *l_begin << "\tTOTAL SCORE: " << *score_begin << endl;
 ultimateTotal += *score_begin;
 }
 cout << "TOTAL NAME SCORES: " << ultimateTotal << endl;
}

• syb0rg: Are the names in the text file unique?
• Ishaan: Yes, 5000 unique names between quotes and separated by commas
• Snowhawk: See this previous answer.

Answer 1

A few notes:

• I'm not a huge fan of this:

  #include <iostream>
  using std::endl;
  using std::cin;
  using std::cout;
  #include <fstream>
  using std::ifstream;
  using std::ofstream;
  #include <string>
  using std::string;
  #include <vector>
  using std::vector;
  #include <algorithm>
  #include <vector>
  using std::vector;
  

  Though it's better than using namespace std;

• If you put your main() function after all of your other functions, then you don't have to specify all of those function prototypes. This helps cut back on the length of your code.

• You don't need to specify the parameter list as void if it doesn't take in parameters. That is a C thing, not C++.

• You never checked if your file opened successfully. I wouldn't assume that it's going to open every time, because that assumption would break your program.

  if (!input) // do something
  

• Your main() function does way too much in your first version. It's better in your second version, but could still be refined down a bit by extracting the file opening process.

• You have a magical number 64 in your code. It would be good to put that in a constant variable and give it a name so that it's purpose is well known and automatically documented.

  constexpr static int ascii_to_integer = 64;
  

• I would look into using std::accumulate in place of your current method of summing up the values for the names.

• You might be able to use a std::map instead of a std::vector, since you have only unique names. They would be sorted upon insertion (which has a logarithmic complexity compared to the vectors linear complexity as you are using it). You would use the names as the keys, and the calculate and store the score as the mapped value. For instance, "COLIN" would be the key, and "53" would be the mapped value. To obtain the actual score for the name though, we would have to multiply that by the index value, which could be found using std::map::find (which is also logarithmic in complexity). I'm not sure if this will amount to a faster program, though it's possible it might.

• Ishaan: Thanks for the tips. I didn't know you didn't have to specify the parameter list as void if no parameters are taken. I did migrate to C++ from C, haha. Also you're correct that my main does too much work in the first version. I initially wrote the second version but tried to make it as small as I can and decided to fit it inside the main and make it do just what it's supposed to do, nothing more.
• Emily L.: Map has logarithmic insertion, inserting 'n' entries is thus 'nlog(n)' compared to only 'n' for vector with constant time insertion at the back. Sorting the vector is a 'nlog(n)' operation. So building the vector and then sorting it is the same time complexity as using the map. The vector has a much better locality of reference than the map (which is a tree structure) hence it will perform much better due to cache performance. Also it is simpler and clearer. Use the vector, please.
• syb0rg: @EmilyL. Good to know, thanks! It was just an idea, I didn't know if it would actually offer a speed improvement or not.