Grind Report 22

Problem 22

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 x 53 = 49714.

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

*WARNING: This contains the solution!*

This was a somewhat longer problem. It was for me at least. Starting off, it is obvious that the names need to be extracted from the .txt file, sorted and then calculate the name scores.

Extraction:
I decided I would use a regex, even though it was kind of overkill for this problem. I considered using Boost regex but I ended up going with the extension of the standard library, which is known as tr1. Which this I was able to define a regex ("[A-Z]+") and then search through the names for all matches, which took the names out of the quotes and commas.

Sorting:
I wanted to have a fast algorithm since 5000+ elements is kind of a lot. Having something like O(n^2) would be horrible and so I decided to go with the popular Quicksort algorithm which can be at best O(log(n)). So I went ahead and implemented that with some help from the wikipedia page for the Quicksort algorithm.

Scoring:
This part was actually the easiest. It was really straight forward and quick to implement.

The real time sucker was getting regex to work. First I had to download and install the extension to Visual Studio 2008 known as VS2008 Feature Pack. Then I had to work with the very limited documentation to figure out how to actually search through a string with a regular expression and retrieve the matched values. Because this has several components to it, I think this is my longest solution thus far. Here it is.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <regex>

using std::tr1::smatch;
using std::tr1::regex;
using std::string;
using std::vector;
using std::ifstream;
using std::cout;

void Swap(string& a, string& b);
void QuickSort(vector<tring>& list, int startIndex, int endIndex);
int Partition(vector<string>& list, int startIndex, int endIndex, int pivotIndex);
int CalcNameScore(string name, int index);

int main()
{
//obtains the string of names
string line;
ifstream file ("names.txt");
if (file.is_open())
  std::getline(file, line);

//setup the regex
smatch match;
const regex ex("[A-Z]+");

//extract the names from the string
string::const_iterator first = line.begin();
string::const_iterator last = line.end();
vector<string> list;
while (std::tr1::regex_search(first, last, match, ex))
{
 list.push_back(match[0]);
 first += match.position() + match.length();
}

//sort the list using Quick Sort
QuickSort(list, 0, list.size() - 1);

//calculate the total name score
int totalNameScore = 0;
for (int i = 0; i < list.size(); ++i)
 totalNameScore += CalcNameScore(list[i], i);
cout << totalNameScore;
}

//simply swaps two values
inline void swap(string& a, string& b)
{
string temp = a;
a = b;
b = temp;
}

void QuickSort(vector<string>& list, int startIndex, int endIndex)
{
if (startIndex < endIndex)
{
 int pivotIndex = startIndex;
 pivotIndex = Partition(list, startIndex, endIndex, pivotIndex);
 QuickSort(list, startIndex, pivotIndex - 1);
 QuickSort(list, pivotIndex + 1, endIndex);
}
}

int Partition(vector<string>& list, int startIndex, int endIndex, int pivotIndex)
{
string pivotValue = list[pivotIndex];
swap(list[pivotIndex], list[endIndex]);
int storeIndex = startIndex;
for (int i = startIndex; i < endIndex; ++i)
{
 if (pivotValue.compare(list[i]) > 0)
  swap(list[i], list[storeIndex++]);
}
swap(list[storeIndex], list[endIndex]);
return storeIndex;
}


int CalcNameScore(string name, int index)
{
int score = 0;
//add up the value from each character in the name
for (int i = 0; i < name.length(); ++i)
 score += name[i] - 'A' + 1;
//returns the score of the name
//index is 0 based so it is necessary to increase by one
return score * (index + 1);
}

*saved game*