Project Euler 22: Names scores

Question

Description of challenge:

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?

I quickly created a solution: it was fairly easy, but I am specifically concerned about the performance, which I am unsure of. What I do know is:

• string.split(): \$O(n)\$
• Arrays.sort(): \$O(n \log n)\$ Worst Case
• Remaining code: \$O(nm)\,ドル where \$n\$ is the length, and \$m\$ is the average length of the names

The code is below:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
public class ProjectEuler22 {
 private static final String filePath = "names.txt";
 private static final int ASCII_VALUE_TO_INT = 64; // naming
 public static void main(String[] args) {
 long time = System.nanoTime();
 String[] names = readAllNames().split("\",\"");
 names[0] = names[0].substring(1);
 int length = names.length; // extra "
 names[length - 1] = names[length - 1].substring(0,
 names[length - 1].length()); // extra "
 Arrays.sort(names);
 int total = 0;
 for (int i = 0; i < length; i++) {
 total += getValueOfName(names[i], i + 1);
 }
 time = System.nanoTime() - time;
 System.out.println("The result is: " + total + "\nTime taken (ns): "
 + time);
 }
 private static String readAllNames() {
 try (BufferedReader reader = new BufferedReader(
 new FileReader(filePath))) {
 return reader.readLine();
 } catch (IOException e) {
 e.printStackTrace();
 return null;
 }
 }
 /**
 * Gets the value of the given string. If there are characters other than
 * [A-Z], then it will ignore it. Note that the problem file only contains
 * names with all caps.
 * 
 * @param string
 * the name to get the value of
 * @param i
 * the index of the name
 * @return the value of the name
 */
 private static int getValueOfName(String string, int i) {
 char[] array = string.toCharArray();
 int sum = 0;
 for (char c : array) {
 if (Character.isUpperCase(c)) {
 sum += c - ASCII_VALUE_TO_INT;
 }
 }
 return sum * i;
 }
}

Output:

The result is: 871198282
Time taken (ns): 19757146

Time taken seems to be around 20_000_000 nanoseconds.

Specific concerns:

1. Is there a better way to solve this? (As said above)
2. Where it says the // naming comment, is the naming fine? Anywhere else where the naming is off?
3. Anything else?

Answer 1

readAllNames()

• This function has nothing to do with names. I'd name it readFirstLine(), and have it accept a File parameter for clarity and possible versatility.
• If you don't know what to do with an exception, just propagate it. This is probably the wrong level at which to decide the exception-handling policy.

private static String readFirstLine(File f) throws IOException {
 try (BufferedReader br = new BufferedReader(new FileReader(f))) {
 return br.readLine();
 }
}

getValueOfName()

• There's not much point in passing i. The caller can perform that multiplication.
• Once you get rid of i, then the task is just to sum the letter values, so I'd rename the function. Note that reducing the task of the function also simplifies its JavaDoc.
• ASCII_VALUE_TO_INT is awkwardly named, and it is defined as a magic number. 'A' - 1 is shorter and more self-explanatory.

/**
 * Sum of values of the uppercase letters, treating 'A' as 1, 'Z' as 26.
 * Ignores all other characters.
 */
private static int letterSum(String s) {
 int sum = 0;
 for (char c : s.toCharArray()) {
 if (Character.isUpperCase(c)) {
 sum += c - ('A' - 1);
 }
 }
 return sum;
}

main()

• The code to strip the " characters is mildly nasty. Taking the substring before splitting would have been simpler. However, you can just sloppily drop that code, since leaving the quotes will affect neither the sort order nor the letter sums.
• I'd prefer two separate calls to System.out.println().

public static void main(String[] args) throws IOException {
 File f = new File("names.txt");
 long time = System.nanoTime();
 String[] names = readFirstLine(f).split(",");
 Arrays.sort(names);
 int total = 0;
 for (int i = 0; i < names.length; i++) {
 total += (i + 1) * letterSum(names[i]);
 }
 time = System.nanoTime() - time;
 System.out.println("The result is: " + total);
 System.out.println("Time taken: " + time + " ns");
}

I get running times about 30% faster than yours. It turns out that String.split(",") is speedier than String.split("\",\"").

Answer 2

1. Well, there's a potentially more efficient way:

   Read the whole file into a byte-array (It's not even a measly 64K), thus avoiding any conversion overhead and most object-allocations, extract the start-indices of all the names, and sort them.

   Is it equally nice? Probably not. And it will only speed it up by a constant factor, because more just isn't there to be had.
   Anyway, measure it because while going down a level gives opportunities for optimization, it's easy to get it wrong.

2. If you don't want to go quite that far, here's an easy one: Strip the trailing " from the last name, and you can drop the test whether you actually have a letter in getValueOfName.

3. Getting to your constants name, that's atrocious. Because, you know, using a named constant for that at all is so bad.
   You can simply use a character-literal: 'A'-1

4. You fail to close the file in readAllNames if newing the BufferedReader fails. Admittedly that's unlikely in such a small program, but anyway.
   Also, why do you catch IOException there, but then return null which immediately causes a NPE in turn in main?

• TheCoffeeCup: I do #2 already, but leave the check there. I forgot to remove it earlier.
• 200_success: When the BufferedReader is auto-closed, it also closes its underlying FileReader.
• Deduplicator: @200_success: Yes, you are right. Still, creating that BufferedReader can throw, in which case there's no safety-net: stackoverflow.com/questions/4785343/what-if-new-fails