2

我正在处理 Project Euler 的问题 22:

使用 names.txt(右键单击并“将链接/目标另存为...”),一个 46K 的文本文件,其中包含超过 5000 个名字,首先按字母顺序对其进行排序。然后计算每个名称的字母值,将该值乘以其在列表中的字母位置以获得名称分数。

例如,当列表按字母顺序排序时,价值 3 + 15 + 12 + 9 + 14 = 53 的 COLIN 是列表中的第 938 个名称。因此,COLIN 将获得 938 × 53 = 49714 的分数。

文件中所有名称分数的总和是多少?

http://projecteuler.net/problem=22

当我在下面编译我的代码时,我得到了答案871196077。正确答案应该是871198282

进口时间

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 "运行时间:" + str(time.time() - tstart)

我试图找到一个具有类似解决方案的程序,但我只知道 Python,这限制了选项。我用我创建的更简单的文本文件运行程序,在那里我可以在没有程序的情况下得到答案,并且所有这些都有效。我用谷歌搜索了问题的答案,但这也无济于事,因为我找不到缺失的点。

我是初学者,所以我非常感谢有关程序和 Python 的任何提示,不仅是那些,这将帮助我正确解决问题。

非常感谢!

4

3 回答 3

3

你不小心弄错了一个名字。

qnames是您的代码生成的名称排序列表,sorted_names是我的:

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

为了好玩:单行 - 嵌套列表推导,你好!

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(",")]) ]) ] )

或者更具可读性:

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(",")]) ]) ] )

黑魔法是 ASCIIA是整数65,ASCIIB是整数66,依此类推——这样ord(char) - 64就可以得到char.


编辑2:

我将完整的、人类可读的解决方案塞进一行以供您娱乐。

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))

请注意大量使用列表推导[x for x in list_of_xes]而不是循环,以及sum()函数而不是for x in xes: sum += x.

这里还有一些其他技巧,但带回家的教训是列表推导和处理列表的函数可以使您的代码更简单,更易于阅读。


编辑3:

pprint.pprint()功能是一个“漂亮print()”。非常适合调试。


编辑4:

代码高尔夫版本(142 个字符):

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(",")])])])
于 2012-05-08T06:57:03.867 回答
1

我刚刚交叉检查了你的代码,看起来你无意中砍掉了最后一个单词的最后一个字符。要从最后一个单词中去掉引号,请使用:

names[-1] = names[-1][:-1]
于 2012-05-08T06:51:52.073 回答
0

当您将文件内容转换为列表时,不要尝试一次从名称中删除所有引号,而是在处理列表时删除它们。

# 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()
于 2012-08-04T15:43:03.140 回答