Project Euler Problem 22 Solution

Project Euler & HackerRank Problem 22 Solution

Names scores
by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank

Project Euler Problem 22 Statement

Using names.txt, 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

Opening, reading and parsing the input file

The names consist of only uppercase characters A through Z and have the form:

"MARY","PATRICIA","LINDA","BARBARA","ELIZABETH","JENNIFER","MARIA", …

The remote file, file_url, is opened as a local file handle using the urllib2 library’s function urlopen.

file_url = 'https://projecteuler.net/project/resources/p022_names.txt'
names = sorted(urllib2.urlopen(file_url).readline()[1:−1].split('","'))

The file is read as one long string ignoring the first and last quote. The names are stored into a list by splitting the string at the quote–comma–quote (",") delimiter. This effectively removes all quotation marks and commas. The list is then sorted alphabetically into ascending order. The use of a list is necessary to solve the HackerRank version of this problem.

After processing, the list looks like this:

names: [AARON, ABBEY, ABBIE, ABBY, ABDUL, ABE, …]

Calculating name scores

The second part of the program uses two loops: one to select each name and the other to parse it into individual characters.

s = 0
for lineNumber, name in enumerate(names, start=1):
    s+= lineNumber * sum(ord(c)−64 for c in name)

The first loop uses the enumerate() function which returns a tuple containing an incremental counter (variable lineNumber) and the corresponding name value by iterating over the names list. By default, enumerate() starts the counter, lineNumber, at 0 unless you redefine it, as I did, using an optional second integer argument. An alternate form for the second argument can include the keyword start to improve readability.

The second loop calculates the name score by iterating each character (string variable c) in the string variable name, summing its character values, and multiplying the sum by the ordinal position of the name in the list. Name scores are summed into variable s.

The ord() function calculates the ASCII value for each character. An ASCII 'A' is 65, 'B' is 66, …, and 'Z' is 90 so we subtract 64 from the ASCII value to normalize the range [65, 90] to [1, 26] as required to calculate a name score.

Using Python’s lambda function and list comprehensions

The above code refactored into using a lambda function and a list comprehension. This is more Pythonic and a succinct way of expressing this algorithm.

score = lambda word: sum(ord(c)−64 for c in word)
s = sum(lineNumber*score(name) for lineNumber, name in enumerate(names, 1))

HackerRank version

Instead of printing a score for the whole file, HackerRank Project Euler 22 wants the score for individual names. Up to 100 queries can be batched at one time.

Python Source Code

download Python source code Use this link to download the Project Euler Problem 22: Names scores Python source.

Last Word

The data file, names.txt, is available on the repl.it page by clicking the files repl.it external files icon in the top left corner.

See also, Project Euler 42: Coded triangle numbers