将数字从1到999,999,999的单词排序为字符串

Question

有趣的编程难题:

如果从1到999,999,999的整数被写成单词,按字母顺序排列并连接,那么第51亿字母是什么？

确切地说:如果从1到999,999,999的整数用单词表示(省略空格,'和',以及标点符号 - 请参见下面的格式说明),并按字母顺序排序,以便前六个整数是

• 八
• 十八
• eighteenmillion
• eighteenmillioneight
• eighteenmillioneighteen
• eighteenmillioneighteenthousand

最后是

• twothousandtwohundredtwo

然后从上到下,从左到右阅读,第28个字母完成整数"十八万"的拼写.

第510亿字母也完成了整数的拼写.哪一个,那个点的所有整数的总和是多少？

注:例如,911,610,034写成"ninehundredelevenmillionsixhundredthnthlenthlethirtythourfour"; 500,000,000写成"五亿"; 1,709写的是"onethousandsevenhundrednine".

我碰到这个无意中发现了一个编程博客"有时候理智的",并不能认为这样做的一个整洁的方式,笔者相关的职位说,他最初试图通过内存1.5GB吃了10分钟,他会只有20,000,000("二十亿").

谁能想到 拿出 与组共享一个新的/聪明的方法呢？

Answer 1

编辑:解决了!

您可以创建一个按排序顺序输出数字的生成器.有一些用于比较连接字符串的规则,我认为我们大多数人都隐含地知道:

• a <a + b,其中b非空.
• a + b <a + c,其中b <c.
• a + b <c + d,其中a <c,a不是c的子集.

如果您从前1000个数字的排序列表开始,您可以通过附加"千"或"百万"并连接另一组1000来轻松生成其余数字.

这是Python中的完整代码:

import heapq

first_thousand=[('', 0), ('one', 1), ('two', 2), ('three', 3), ('four', 4),
                ('five', 5), ('six', 6), ('seven', 7), ('eight', 8),
                ('nine', 9), ('ten', 10), ('eleven', 11), ('twelve', 12),
                ('thirteen', 13), ('fourteen', 14), ('fifteen', 15),
                ('sixteen', 16), ('seventeen', 17), ('eighteen', 18),
                ('nineteen', 19)]
tens_name = (None, 'ten', 'twenty', 'thirty', 'forty', 'fifty', 'sixty',
             'seventy','eighty','ninety')
for number in range(20, 100):
    name = tens_name[number/10] + first_thousand[number%10][0]
    first_thousand.append((name, number))
for number in range(100, 1000):
    name = first_thousand[number/100][0] + 'hundred' + first_thousand[number%100][0]
    first_thousand.append((name, number))

first_thousand.sort()

def make_sequence(base_generator, suffix, multiplier):
    prefix_list = [(name+suffix, number*multiplier)
                   for name, number in first_thousand[1:]]
    prefix_list.sort()
    for prefix_name, base_number in prefix_list:
        for name, number in base_generator():
            yield prefix_name + name, base_number + number
    return

def thousand_sequence():
    for name, number in first_thousand:
        yield name, number
    return

def million_sequence():
    return heapq.merge(first_thousand,
                       make_sequence(thousand_sequence, 'thousand', 1000))

def billion_sequence():
    return heapq.merge(million_sequence(),
                       make_sequence(million_sequence, 'million', 1000000))

def solve(stopping_size = 51000000000):
    total_chars = 0
    total_sum = 0
    for name, number in billion_sequence():
        total_chars += len(name)
        total_sum += number
        if total_chars >= stopping_size:
            break
    return total_chars, total_sum, name, number

运行需要一段时间,大约一个小时.第510亿个字符是六百七十万个七十万五千五百五十五的最后一个字符,这一点的整数之和为413,540,008,163,475,743.

Answer 2

我将前20个整数的名称和数十个,数百个和数千个的名称排序,计算出每个数字的起始数量,并从那里开始.

例如,前几个是[ eight, eighteen, eighthundred, eightmillion, eightthousand, eighty, eleven, ....

以"八"开头的数字是8."八百",800-899,800,000-899,999,800,000,000-899,999,999.等等.

可以找到并总计0(由空字符串表示)到99的单词串联中的字母数; 这可以乘以"千"= 8或"百万"= 7加入更高的范围.800-899的值将是"eighthundred"长度的100倍加上0-99的长度.等等.

Answer 3

这个家伙有一个用Haskell编写的难题的解决方案.显然Michael Borgwardt使用Trie寻找解决方案是正确的.

Answer 4

这些字符串将有很多很多共同的前缀 - 一个trie的完美用例,这将大大减少内存使用量,也可能还有运行时间.