6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

#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.

\$\endgroup\$
  • 3
    \$\begingroup\$ The magic 256 could be avoided by using std::begin and std::end... \$\endgroup\$ – Deduplicator May 2 '17 at 17:22
  • 1
    \$\begingroup\$ std::iota() learn something new every day. \$\endgroup\$ – Martin York May 2 '17 at 21:08
  • \$\begingroup\$ @Deduplicator I didn't mean just this one line. 256 in a declaration of data is also magic. \$\endgroup\$ – vnp May 3 '17 at 4:16
5
\$\begingroup\$

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!)

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ this should be a comment - not an answer \$\endgroup\$ – Nilzone- May 2 '17 at 17:26
  • \$\begingroup\$ Only person to spot the static member in the class constructor +1. Yep I'll remove that use of base in the constructor. \$\endgroup\$ – Martin York May 2 '17 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.