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;

}

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.