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

Question

有趣 programming puzzle :

If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?

To be precise: if the integers from 1 to 999,999,999 are expressed in words (omitting spaces, ‘and’, and punctuation - see note below for format), and sorted alphabetically so that the first six integers are

• eight
• eighteen
• eighteenmillion
• eighteenmillioneight
• eighteenmillioneighteen
• eighteenmillioneighteenthousand

and the last is

• twothousandtwohundredtwo

then reading top to bottom, left to right, the 28th letter completes the spelling of the integer “eighteenmillion”.

The 51 billionth letter also completes the spelling of an integer. Which one, and what is the sum of all the integers to that point?

Note: For example, 911,610,034 is written “ninehundredelevenmillionsixhundredtenthousandthirtyfour”; 500,000,000 is written “fivehundredmillion”; 1,709 is written “onethousandsevenhundrednine”.

我在一个编程博客上偶然发现了这个 'Occasionally Sane' ，并且想不出一个巧妙的方法，relevant post 的作者说他最初的尝试在 10 分钟内吃掉了 1.5GB 的内存，而他只达到了 20,000,000(“两千万”)。

任何人都可以想到 想出 与小组分享一个新颖/聪明的方法吗？

Answer 1

编辑:已解决!

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

• a < a+b，其中 b 为非空值。
• a+b < a+c，其中 b < c。
• a+b < c+d，其中 a < c，并且 a 不是 c 的子集。

如果您从前 1000 个数字的排序列表开始，您可以通过附加“thousand”或“million”并连接另一组 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

跑了一段时间，大概一个小时。第 51 个十亿字符是 sixhundredseventys6millionsevenhundredfortysixthousandfivehundredseventyfive 的最后一个字符，到该点的整数之和为 413,540,008,163,475,743。