Problem 22 : Names Scores

Names scores

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 × 53 = 49714.
What is the total of all the name scores in the file?

                                                                                                       (https://projecteuler.net/problem=22)

Simple problem, simple algorithm, so let's directly get into the solution.

We will read in that 46K files, because I don't want to manually store the five thousand Strings into a giant array... I mean... really....

public static String[] read()
{
    String[] text = new String[5000];
    File file = new File(text022);
    try (BufferedReader br = new BufferedReader(new FileReader(file)))
    {
        String line = br.readLine();
        line = line.replace("\"", "");
        text = line.split(" ");
    }
    catch (IOException e)
    {
        System.err.println(e);
    }
    return text;
}

After that, we sort the array, as the problem stated, in alphabetical order.

I used java.util.Arrays to use the function sort() to put them in order.

If we want to create our own solution for sorting, (and if so, I have to talk about either one of Quicksort, Mergesort, or heapsort, which are considered the fastest sorting algorithms out there), yet most programmers will use the built-in functions to quickly solve the problem.

import java.util.Arrays;

...

public class Problem022 implements textFile.Texts
{
    private static String[] NAME = read();
 
    public static void run()
    {
        Arrays.sort(NAME);
  
        ...
    }
 
}

For each name, we will get the value for each char in the String.

Here, I will use the trick I used in the problem 20, where I used the intrinsic value of the primitive data types stored in Java:

for (int i=0; i < NAME.length; i++)
{
    sum = 0;
    char[] arr = NAME[i].toCharArray();
    for (char c : arr) sum += c - 'A' + 1;
    score += sum * (i+1);
}

The logic behind this algorithm is simple.

The character 'A' will have some value in computer. And character 'B' will also have some value in computer, but no matter what value that is, its value will be 1 bigger than the value of 'A' because the computer stores the values in chronological order.

So value('B') - value('A') = 1.

Because the problem counts the characters from 1 starting with 'A', we will simply add +1 at the end.

(Look at the code above.)

Combined solution:

Arrays.sort(NAME);
  
int score = 0, sum = 0;
  
for (int i=0; i < NAME.length; i++)
{
    sum = 0;
    char[] arr = NAME[i].toCharArray();
    for (char c : arr) sum += c - 'A' + 1;
    score += sum * (i+1);
}
System.out.println(score);

Answer is 871198282
Execution time is 27.967796 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem022.java