Project Euler Solution 22

Problem Statement#

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

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?

Solution#

This problem just requires a best sorting algorithm to solve it. Also we must find a solution to separate the names in the file. The names in the file is stored as shown below without any space.

"MARY","PATRICIA","LINDA","BARBARA","ELIZABETH"

So my first step was to separate the names in the file leaving comma and quotation into an array of pointers.
My second step was to sort the names using a well known best sorting algorithm called quick sort.
Now the names are ready to find name scores.

Now let us see an example for quick sort on the above names.

Initially the unsorted array of names looks as shown below.

Pivot	l = 1	2	3	h = 4
MARY	PATRICIA	LINDA	BARBARA	ELIZABETH

Now moving from left to right strating with ‘l = 1’, find a name bigger in alphabetical order than the pivot name “MARY”. The name “PATRICIA” at ‘l = 1’ is itself a lager name than pivot name. So stay at l = 1.

Now moving from right to left starting with ‘h = 4’, find a name smaller than “MARY”. The name “ELIZABETH” is smaller than “MARY”. So stay at h = 4.

Next step is to swap “PATRICIA” and “ELIZABETH”. Now the array looks like this

Pivot	l = 1	2	3	h = 4
MARY	ELIZABETH	LINDA	BARBARA	PATRICIA

Continue the above steps until l = h or l > h

Now ELIZABETH < MARY, so move l one step forward so l=2. “LINDA” at l = 2 is larger than “MARY”.

PATRICIA > MARY, so move h one step down so h=3. “BARBARA” at h = 3 is smaller than “MARY”.

So swap LINDA and PATRICIA . Now the array looks as below

Pivot	1	l = 2	h = 3	4
MARY	ELIZABETH	BARBARA	LINDA	PATRICIA

Continuing with the above steps,

Pivot	1	h = 2	l = 3	4
MARY	ELIZABETH	BARBARA	LINDA	PATRICIA

Now l > h, so our next step is to swap names in ‘pivot’ and ‘h’. After this step the pivot name is placed at its final position.

0	1	2	3	4
BARBARA	ELIZABETH	MARY	LINDA	PATRICIA

Now perform the above steps on two arrays: one containing names less than “MARY” and the other containing names greater than “MARY”. The two arrays are

0	1
BARBARA	ELIZABETH

3	4
LINDA	PATRICIA

Considering the first array

pivot	l = h = 1
BARBARA	ELIZABETH

l = h = 1, so swap names in pivot and h.

ELIZABETH

BARBARA

We have only one array containing single name, which means they are sorted.

Consider the second array

pivot = 3	l = h = 4
LINDA	PATRICIA

When moving from left to right to find a larger name, PATRICIA is greater than LINDA, so l=4. But when moving from right to left to find smaller name than LINDA, PATRICIA is greater, so move h one step down to get h = 3.

h = pivot = 3	l = 4
LINDA	PATRICIA

Now h and pivot points to the same name, which means they are already sorted.

3	4
LINDA	PATRICIA

The final sorted array looks as follows

0	1	3	4	5
ELIZABETH	BARBARA	MARY	LINDA	PATRICIA

Let us see the program

Implementation#

#include <stdio.h>#include <string.h>
int Sort_Names(int, int);int total_no_of_names;char *all_names[6000];
int main(){    FILE * f_read;    char c;    char name[6000][20];    int i = 0, j = 0, k, name_val;    long long int tot_name_score = 0;    f_read = fopen("namespe022.txt", "rt");    while ((c = fgetc(f_read)) != EOF)    {        if (c == 34) {}        else if (c == 44)        {            i++;            j = 0;        }        else        {            name[i][j] = c;            j++;        }    }    fclose(f_read);    total_no_of_names = i;    for (i = 0; i <= total_no_of_names; i++)    {        all_names[i] = name[i];    }    Sort_Names(0, total_no_of_names);    for (i = 0; i <= total_no_of_names; i++)    {        k = 0;        name_val = 0;        while (k < strlen(all_names[i]))        {            name_val = name_val + (all_names[i][k] - 64);            k++;        }        tot_name_score = (i + 1) *name_val + tot_name_score;    }    printf("%lld", tot_name_score);    return 0;}
int Sort_Names(int low, int high){    char *pivot, *temp;    int l, h;    pivot = all_names[low];    l = low + 1, h = high;    while (l <= h)    {        while (strcmp(all_names[l], pivot) < 0) l++;        while (strcmp(all_names[h], pivot) > 0) h--;        if (l < h)        {            temp = all_names[l];            all_names[l] = all_names[h];            all_names[h] = temp;            l++;            h--;        }    }    all_names[low] = all_names[h];    all_names[h] = pivot;    if (h > low)    {        Sort_Names(low, h - 1);    }    if (l < high)    {        Sort_Names(h + 1, high);    }}

Sample Output#

Sample Output