[C/C++] Project Euler #22 Names Scores

The problem requires calculating the total of all name scores in a given text file containing names. The steps to solve the problem are:
1. Parse the input file: Read a file that contains a single line of comma-separated names, each enclosed in double quotes.
2. Sort the names alphabetically: Sort the list of names in ascending order.
3. Compute name scores:
• Assign a score to each name based on the alphabetical value of its letters (A=1, B=2, …, Z=26).
• Multiply the alphabetical value by the position of the name in the sorted list (1-based index).
4. Calculate the total score: Sum all the name scores to get the final result.

For example, if the file contains the names "COLIN", "ALEX", "BOB", the sorted order is "ALEX", "BOB", "COLIN". If "COLIN" has an alphabetical value of 53 and is in position 3, its score is  \(53 \times 3 = 159\).

 

This problem involves calculating name scores and multiplying them by their sorted position, which is a relatively straightforward algorithm.

For sorting, you can use the built-in qsort() function available in C/C++, or apply a simple algorithm, and it wouldn’t make much difference.

I decided to implement heap sort. While heap sort isn’t necessarily the best, it has advantages in certain scenarios. Initially, I planned to process the data directly from a file, and in such cases, heap sort or insertion sort can be beneficial. Unlike other sorting methods, which first load data into an array and then sort it, heap sort and insertion sort have the advantage of handling insertions more efficiently during the sorting process since insertions occur naturally in these methods.

Looking at the given data file, it seemed more practical to simply copy and paste the data into the source code or use #include "names.txt" rather than parsing it from a file. Since the names are enclosed in double quotes and separated by commas, there wasn’t a compelling reason to go through the process of reading and parsing a file.

Because of this, the program itself doesn’t have any particularly challenging aspects.

 

name scores

Here’s the source code.

//------------------------------------------------
//    Project Euler #22 - Names Scores
//        - by Aubrey Choi
//        - created at 2015-01-25
//------------------------------------------------
#include <stdio.h>
#include <string.h>

void heapsort(const char *array[], int n);
const char *getfirst(const char *array[], int *n);
int getvalue(const char *str);

int main()
{
    const char *names[] = {
        #include "names.txt"
    };

    int n = sizeof(names)/sizeof(const char *);

    heapsort(names, n);

    int sum = 0, s = 1;
    while( n )
    {
        const char *p = getfirst(names, &n);
        sum += getvalue(p) * s++;
    }

    printf("Ans = %d\n", sum);
}

void heapify(const char *arrary[], int n, int k);

void heapsort(const char *array[], int n)
{
    for( int i = n/2-1 ; i >= 0 ; i-- )
    {
        heapify(array, n, i);
    }
}

const char *getfirst(const char *array[], int *pn)
{
    int n = --(*pn);
    const char *ret = array[0];
    array[0] = array[n];
    heapify(array, n, 0);
    return ret;
}

int getvalue(const char *str)
{
    int v = 0;
    while( *str ) v += *str++ - 'A' + 1;
    return v;
}

void heapify(const char *array[], int n, int k)
{
    int l = k*2+1, r = k*2+2;
    int m = l;
    if( l >= n ) return;
    if( r < n && strcmp(array[l], array[r]) > 0 ) m = r;
    if( strcmp(array[k], array[m]) > 0 )
    {
        const char *t = array[k];
        array[k] = array[m];
        array[m] = t;
        heapify(array, n, m);
    }
}