Project Euler #22 Python, 2205 points missing?

Question

I'm working on problem 22 of Project Euler:

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?

http://projecteuler.net/problem=22

When I compile my code below, I get the answer 871196077. The correct answer should be 871198282.

import time

def euler_22():

## Creates a sorted list of the names in Py_Euler_22.txt
names = open('Py_Euler_22.txt', 'r')
names = names.read()
names = names.split('","')
names[0] = names[0][1:]
names[-1] = names[-1][:-2]
names = sorted(names)

## Creates a dictionary: letter -> value
value_letters = {}
start = ord("A")
for i in range(0, 26):
    value_letters[chr(start+i)] = i+1

result = 0

for i in range(1, len(names)+1):
    name = names[i-1] 
    sum_letters = 0
    for letter in name:
        sum_letters += value_letters[letter]*i 
        # = value of the letter multiplied with the name position
    result += sum_letters
return result

tstart = time.time() print euler_22() print "Run time: " + str(time.time() - tstart)

I tried to find a program with a similar solution, but I only know Python, that limits the options. I ran the program with simpler text-files, I created, where I can get the answer without a program and all of them worked. I googled the answer to the problem, but that didn't help either, since I cant find the missing points.

I'm a beginner, so I would really appreciate any tips regarding the program and Python, not only those, that will help me to solve the problem correctly.

Thanks a lot!

Answer 1

Rather than trying to strip all the quotes from the names at once when you're converting the file contents to a list, strip them when you're processing the list.

# Project Euler Problem 22
# Name Scores

def score(name):
    total = 0

    for char in name:
        total += (ord(char) - 64) # scale so A = 1, B = 2...

    return total

def main():
    # Open the names file for reading
    infile = open('names.txt', 'r')

    # Read the entire contents of the file
    file_contents = infile.read()

    # Close the file
    infile.close()

    # Convert file contents to a list of quoted names and sort them
    list_of_names = file_contents.split(',')
    list_of_names.sort()

    position = 1
    total = 0
    for name in list_of_names:
        name = name.strip('"') # strip the quotes from names individually
        total += score(name) * position
        position += 1

    print(total)

if __name__ == "__main__":
    main()

Answer 2

I just cross-checked your code, and it looks like you're inadvertently chopping off the last character of the last word. To strip off the quotes from the last word, use:

names[-1] = names[-1][:-1]

Answer 3

You have accidentally mangled one name.

Here qnames is the sorted list of names your code produces, and sorted_names is mine:

>>> for a,b in zip(qnames, sorted_names):
...     if a != b:
...         print a, b
... 
ALONS ALONSO

---

For fun: a one-liner - nested list comprehensions, avast ye!

print sum ( [ (pos+1) * nv for pos, nv in enumerate([ sum ( [ ord(char) - 64 for char in name ] ) for name in sorted([name.strip('"') for name in open('names.txt','r').readline().split(",")]) ]) ] )

Or more readably:

print sum (
    [(pos+1) * nv for pos, nv in
        enumerate([ sum ([ ord(char) - 64 for char in name ] ) for name in
            sorted([name.strip('"') for name in
                open('names.txt','r').readline().split(",")]) ]) ] )

The black magic is that ASCII A is integer 65, ASCII B is integer 66, and so on - so ord(char) - 64 gets you the "letter value" of char.

---

Edit 2:

The full, human-readable, solution that I crammed into one line for your amusement.

with open('names.txt','r') as f:
    data = f.readline();

names = [name.strip('"') for name in data.split(",")]
sorted_names = sorted(names)
name_values = [ sum ( [ ord(char) - 64 for char in name ] ) for name in sorted_names ]
name_position_values = [ (pos+1) * nv for pos, nv in enumerate(name_values) ]
total_sum = sum(name_position_values)

# debug output
from pprint import pprint
#position, word value, position * word value, word
pprint(zip(xrange(1,len(names)+1),name_values,name_position_values,sorted_names))

Note the heavy use of list comprehensions [x for x in list_of_xes] instead of loops, and the sum() function instead of for x in xes: sum += x.

There are some other tricks in here, but the take-home lesson is that list comprehensions and functions that process lists can make your code much simpler and easier to read.

---

Edit 3:

The pprint.pprint() function is a "pretty print()". It's great for debugging.

---

Edit 4:

Code golf version (142 chars):

print sum([(p+1)*v for p,v in enumerate([sum(map(ord,n))-64*len(n) for n in sorted([n[1:-1] for n in open('names.txt').read().split(",")])])])