Word numbers

I read about a programming puzzle today on programming.reddit. Here’s the problem:

“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[1]), 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?

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

I’ve thought about this, and I can’t think of an efficient way to solve this. In a world of infinite memory and processor power you would:

  1. Generate the numbers from 1 to 999,999,999
  2. Apply a number_to_words() function on every number and into a mapping of the form ([number], [number in english])
  3. Sort the list on the numbers in english
  4. Count characters and sum numbers until character 51,000,000,000 is reached

The problem is that this would take WAY too long and WAY too much memory. I initially thought that a lazy data structure would work, but since you need to sort the list, you need to have all the elements, so you’re kinda screwed anyhow. I made a quick test where I wrote the numbers to a file to save on memory, but I was up to 1.5 GB by the time (± 10 minutes) I reached twentymillion; needless to say I stopped the process right there.

Does anyone have a brilliant idea how this could be solved? Maybe by generating the numbers starting with 8 first, then by 5, then 4, etc.?

About these ads

3 thoughts on “Word numbers

  1. You could use a Trie (http://en.wikipedia.org/wiki/Trie) to sort the strings very quickly and efficiently. You don’t need to concatenate the strings after you have sorted them, it should suffice to traverse the trie while keeping track of the number of characters examined and the sum of the integers seen so far.

  2. Pingback: Sorting numbers from 1 to 999,999,999 in words as strings | Ask Programming & Technology

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s