Project Euler 22: Names scores by Loki

Question

Started working through Project Euler this weekend.

Project Euler 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 ×ばつかける 53 =わ 49714.

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

#include <iostream>
#include <fstream>
#include <iterator>
#include <string>
#include <set>
#include <numeric>
#include "PunctFacet.h"
using ThorsAnvil::Util::PunctFacet;
long scoreName(std::string const& name)
{
 return std::accumulate(std::begin(name), std::end(name), 0L, 
 [](long v1, char x){return v1 + x - 'A' + 1;});
}
int main()
{
 // Open a file that considers " and , as space and thus ignores them
 std::ifstream data;
 data.imbue(std::locale(std::locale(), new PunctFacet(std::locale(), "\",")));
 data.open("euler/e22.data");
 // read all the names in a set (its sorted) 
 std::set<std::string> names{std::istream_iterator<std::string>(data),
 std::istream_iterator<std::string>()};
 // Calculate the result
 long score = 0;
 long loop = 1;
 for(auto name: names) {
 score += (loop * scoreName(name));
 ++loop;
 }
 std::cout << score << "\n";
}

PunctFacet.h

#ifndef THORSANVIL_UTIL_PUNCT_FACET_H
#define THORSANVIL_UTIL_PUNCT_FACET_H
#include <locale>
#include <string>
#include <sstream>
namespace ThorsAnvil
{
 namespace Util
 {
// This is my facet that will treat the characters in `extraSpace`
// as space characters and thus ignore them with formatted input
class PunctFacet: public std::ctype<char>
{
 public:
 typedef std::ctype<char> base;
 typedef base::char_type char_type;
 PunctFacet(std::locale const& l, std::string const& extraSpace)
 : base(table)
 {
 std::ctype<char> const& defaultCType = std::use_facet<std::ctype<char> >(l);
 // Copy the default value from the provided locale
 static char data[256];
 for(int loop = 0;loop < 256;++loop) { data[loop] = loop;}
 defaultCType.is(data, data+256, table);
 // Modifications to default to include extra space types.
 for(auto space: extraSpace) {
 table[space] |= base::space;
 }
 }
 private:
 base::mask table[256];
};
 }
}
#endif

Results

> g++ -O3 -std=c++14 euler/e22.cpp
> time ./a.out
871198282
real 0m0.018s
user 0m0.009s
sys 0m0.007s

Answer 1

#include <numeric>!

I see no reason why individual score is computed via std::accumulate, but the total uses a loop. I recommend std::inner_product there, at least for consistency.

Similarly, the

 for(int loop = 0;loop < 256;++loop) { data[loop] = loop;}

is

 std::iota(data, data + 256, 0);

Of course, a magic 256 shall be replaced by a symbolic name.

I don't feel comfortable with std::set used just to avoid sorting. It obscures the intention. You seem to have the same feeling, and put the clarifying comment. I recommend to be explicit: read the names into a vector, and sort it. BTW, it would also reduce space requirements.

• Deduplicator: The magic 256 could be avoided by using std::begin and std::end...
• Loki Astari: std::iota() learn something new every day.
• vnp: @Deduplicator I didn't mean just this one line. 256 in a declaration of data is also magic.

Answer 2

Include your own headers before standard headers

I'd write:

#include "PunctFacet.h"
#include <fstream>
#include <iterator>
#include <string>
#include <set>
#include <numeric>

That way, if you accidentally forget a necessary definition in your own header (by virtue of an earlier include happening to provide it), you increase your chances of discovering it at an early stage.

Avoid magic constants

Where does that 256 come from? If it's supposed to be equal to base::table_size, then just use the constant, to be consistent with the base class.

Review visibility of types

I don't see a need to make the base type public - it seems that this is provided for implementation convenience only (and it tends to get confusing when you have a hierarchy where many, but not all, classes provide such a member).

Spell-check your comments

// read all the names in a set (it's sorted)
 ^^^^

(Okay, I'm over-doing it now!)

Answer 3

I wonder why data in ThorsAnvil::Util::PunctFacet::PunctFacet is static instead of automatic storage class.

I also wonder why you don't use your base-typedef in that ctor.

• Nilzone-: this should be a comment - not an answer
• Loki Astari: Only person to spot the static member in the class constructor +1. Yep I'll remove that use of base in the constructor.