在字作为字符串排序编号，从1到999,999,999 [英] Sorting numbers from 1 to 999,999,999 in words as strings

问题描述

有趣的编程之谜：

如果整数从1到999999999   写为词语，排序   按字母顺序排列，然后连接起来，是什么   是51亿个字母？

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

要为precise：如果从1整数   以999,999,999是前pressed在口头上   （省略空格，和，并   标点符号 - 见注释下面的格式），并分类   按字母顺序，以使前六   整数是

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

  
• 8
  
• 18
  
• eighteenmillion
  
• eighteenmillioneight
  
• eighteenmillioneighteen
  
• eighteenmillioneighteenthousand
  

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

和最后才是

  
• twothousandtwohundredtwo
  

然后读从上到下，左到   没错，在28日的信完成   整数拼写   eighteenmillion。

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

51亿个字母也完成   一个整数的拼写。哪一个，   什么是所有的总和   整数到这一点？

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?

注意：的例如，911610034是   书面   ninehundredelevenmillionsixhundredtenthousandthirtyfour;   5亿写入   fivehundredmillion; 1709写入   onethousandsevenhundrednine。

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

我碰到这个偶然在一个编程博客有时候理智的和不能想到一个整洁的方式这样做时，相关帖子的作者说，他最初的尝试吃通过内存在10分钟内1.5GB，而他只和好了2000万（twentymillion）。

I stumbled across this on a programming blog 'Occasionally Sane', and couldn't think of a neat way of doing it, the author of the relevant post says his initial attempt ate through 1.5GB of memory in 10 minutes, and he'd only made it up to 20,000,000 ("twentymillion").

谁能<打击>想 <打击>的拿出的 同组一个新的/聪明的办法处理这一份额？

Can anyone think of come up with share with the group a novel/clever approach to this?

推荐答案

编辑：解决

您可以创建一个生成器，输出数字的排序顺序。有比较串联字符串一些规则，我想大多数人都知道含蓄：

You can create a generator that outputs the numbers in sorted order. There are a few rules for comparing concatenated strings that I think most of us know implicitly:

• A＆LT; A + B，其中B是非空的。
• A + B＆LT;一个+ c，其中b将角
• A + B＆LT; C + D，其中A＆LT; c和一个不是C的子集。

如果你开始第一个1000号的排序列表，你可以很容易地通过添加千生成休息或万和连接的1000另一组。

If you start with a sorted list of the first 1000 numbers, you can easily generate the rest by appending "thousand" or "million" and concatenating another group of 1000.

下面是完整的code，Python中的：

Here's the full code, in 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亿个字是sixhundredseventysixmillionsevenhundredfortysixthousandfivehundredseventyfive的最后一个字符，而整数到该点的总和413,540,008,163,475,743。

It took a while to run, about an hour. The 51 billionth character is the last character of sixhundredseventysixmillionsevenhundredfortysixthousandfivehundredseventyfive, and the sum of the integers to that point is 413,540,008,163,475,743.

这篇关于在字作为字符串排序编号，从1到999,999,999的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！