## Description

"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), 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?

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

(This puzzle description is © ITA Software.)

## Solution

This problem is interesting because it has an ugly, brute force solution but begs for a more considered approach. The brute force solution is to generate all of the words, write them to a file, sort them, and start counting. In keeping with the lack of elegance, that approach should be implemented in Perl. Obviously this technique will require at least 51 gigabytes of storage, based solely on the problem description. Disk space is cheap, but there's got to be a better way.

The 51 gigabyte minimum implied by the problem description prohibits running the brute force approach in memory. To get a rough idea of how much memory is required to hold all of the words, the nine digit number 123,456,789 is expressed in English (without spaces and hyphens) as:

onehundredtwentythreemillionfourhundredfiftysixthousandsevenhundredeightynine

That is 77 characters, which suggests that the full set of words will require the better part of 100 gigabytes.

That string was easily computed using Common Lisp, the first programming language that comes to mind when elegance is required. The function used is:

(defun stripped-number-word (i) "Return the English representation of I with spaces and hyphens removed." (remove-if-not #'alpha-char-p (format nil "~R" i)))

Since storing all of the words is not a reasonable option, the solution will need to trade CPU cycles for space. Fortunately, the problem provides a simple ordering. It isn't necessary to store all the numbers and words, only the total length of the words and the sum of the numbers who's corresponding words appear alphabetically before the one containing the 51 billionth letter. Breaking the search space up into multiple alphabetically ordered pieces will allow the problem to be solved by a repeated divide-and-conquer approach.

First, a little exploratory coding. A histogram of number word stems and the total length for all words with those stems will identify where the 51 billionth letter is hiding. My first cut of a histogram function is:

(defun number-word-histogram (max-value stem-size) "For all integers from 1 to MAX-VALUE, return the number of integers, the total length of the English words for their values, and their sum for those whose words are the same up to STEM-SIZE." (flet ((stem-tally (stem histogram) (multiple-value-bind (tally exists) (gethash stem histogram) (if exists tally (list 0 0 0))))) (let ((histogram (make-hash-table :test 'equal))) (dotimes (i max-value histogram) (let* ((word (stripped-number-word (1+ i))) (stem (subseq word 0 (min (length word) stem-size))) (tally (stem-tally stem histogram))) (setf (gethash stem histogram) (list (1+ (first tally)) (+ (second tally) (length word)) (+ (third tally) (1+ i)))))))))

This function creates a hash table with keys that are word stems and values that are lists of interesting information about the numbers and words associated with that stem. In addition to the total length of all words beginning with the stem, `number-word-histogram` also tracks the sum of all numbers corresponding to those words and the number of words with that stem. The number of words is useful as a sanity check during testing.

A simple test harness shows this function working correctly:

(defun test-histogram (max-value stem-size) (let ((totals (list 0 0 0))) (maphash (lambda (key value) (setf totals (mapcar #'+ totals value)) (format t "~S ~S~&" key value)) (number-word-histogram max-value stem-size)) totals)) (test-histogram 10000 4) "sixt" (1011 29533 6500161) "twot" (1000 29440 2499500) "six" (1 3 6) "ten" (1 3 10) "eigh" (1112 33603 8585321) "twel" (1 6 12) "twen" (10 96 245) "thre" (1101 33499 3534453) "thir" (11 104 358) "seve" (1112 33614 7575219) "two" (1 3 2) "one" (1 3 1) "fift" (11 93 560) "oneh" (100 1854 14950) "five" (1101 32398 5554455) "fort" (10 86 445) "tent" (1 11 10000) "onet" (1000 29440 1499500) "elev" (1 6 11) "four" (1102 32406 4544468) "sixh" (100 1854 64950) "nine" (1112 32502 9595423) "twoh" (100 1854 24950) (10000 292411 50005000)

Working correctly and performing well are two different things. Timing the performance of `number-word-histogram` on my laptop gives the following numbers:

? (time (number-word-histogram 10000 4)) (NUMBER-WORD-HISTOGRAM 10000 4) took 553 milliseconds (0.553 seconds) to run with 1 available CPU core. During that period, 445 milliseconds (0.445 seconds) were spent in user mode 16 milliseconds (0.016 seconds) were spent in system mode 32 milliseconds (0.032 seconds) was spent in GC. 5,033,584 bytes of memory allocated. # ? (time (number-word-histogram 100000 5)) (NUMBER-WORD-HISTOGRAM 100000 5) took 6,230 milliseconds (6.230 seconds) to run with 1 available CPU core. During that period, 4,513 milliseconds (4.513 seconds) were spent in user mode 170 milliseconds (0.170 seconds) were spent in system mode 152 milliseconds (0.152 seconds) was spent in GC. 55,418,672 bytes of memory allocated. # ? (time (number-word-histogram 1000000 6)) (NUMBER-WORD-HISTOGRAM 1000000 6) took 76,564 milliseconds (76.564 seconds) to run with 1 available CPU core. During that period, 48,774 milliseconds (48.774 seconds) were spent in user mode 1,879 milliseconds (1.879 seconds) were spent in system mode 2,176 milliseconds (2.176 seconds) was spent in GC. 661,388,344 bytes of memory allocated. #

Extrapolating from the last result suggests that computing the histogram up to 999,999,999 will take anywhere from 14 to 21 hours on my laptop. Fortunately, I have access to a bigger machine:

* (time (number-word-histogram 1000000 6)) Evaluation took: 9.766 seconds of real time 9.760517 seconds of total run time (9.716523 user, 0.043994 system) [ Run times consist of 0.208 seconds GC time, and 9.553 seconds non-GC time. ] 99.95% CPU 24,295,513,567 processor cycles 1,476,985,376 bytes consed

This should create the full histogram in about 2 hours and 45 minutes on one CPU of this 8 CPU box. I'll start it running while thinking about making it multithreaded and optimizing the implementation (over lunch).

While that's running, I need to modify the implementation of `number-word-histogram` to build a hashtable of only certain stems and `test-histogram` to optionally pass in a base stem.

(defun number-word-histogram (max-value stem-size &optional (base-stem nil)) "For all integers from 1 to MAX-VALUE, return the number of integers, the total length of the English words for their values, and their sum for those whose words are the same up to STEM-SIZE. If BASE-STEM is specified, the word must begin with it." (flet ((bad-stem-p (word) (and base-stem (or (< (length word) (length base-stem)) (string/= (subseq word 0 (length base-stem)) base-stem)))) (stem-tally (stem histogram) (multiple-value-bind (tally exists) (gethash stem histogram) (if exists tally (list 0 0 0))))) (let ((histogram (make-hash-table :test 'equal)) (max-stem-size (+ stem-size (length base-stem)))) (dotimes (i max-value histogram) (let ((word (stripped-number-word (1+ i)))) (unless (bad-stem-p word) (let* ((stem-length (min (length word) max-stem-size)) (stem (subseq word 0 stem-length)) (tally (stem-tally stem histogram))) (setf (gethash stem histogram) (list (1+ (first tally)) (+ (second tally) (length word)) (+ (third tally) (1+ i))))))))))) (defun test-histogram (max-value stem-size &optional (base-stem nil)) (let ((totals (list 0 0 0))) (maphash (lambda (key value) (setf totals (mapcar #'+ totals value)) (format t "~S ~S~&" key value)) (number-word-histogram max-value stem-size base-stem)) totals))

This still searches the whole range from 1 to 999,999,999 even when a base stem is specified. To limit the amount of duplicate computation, I'll add a minimum value and track the minimum and maximum values associated with each stem.

(defun number-word-histogram (max-value stem-size &optional (base-stem nil) (min-value 1)) "For all integers from MIN-VALUE to MAX-VALUE, return the number of integers, the total length of the English words for their values, and their sum for those whose words are the same up to STEM-SIZE. If BASE-STEM is specified, the word must begin with it." (flet ((bad-stem-p (word) (and base-stem (or (< (length word) (length base-stem)) (string/= (subseq word 0 (length base-stem)) base-stem)))) (stem-tally (stem histogram) (multiple-value-bind (tally exists) (gethash stem histogram) (if exists tally (list 0 0 0 0 0))))) (let ((histogram (make-hash-table :test 'equal)) (max-stem-size (+ stem-size (length base-stem)))) (do* ((i min-value (1+ i)) (word (stripped-number-word i) (stripped-number-word i))) ((> i max-value) histogram) (unless (bad-stem-p word) (let* ((stem-length (min (length word) max-stem-size)) (stem (subseq word 0 stem-length)) (tally (stem-tally stem histogram))) (setf (gethash stem histogram) (list (1+ (first tally)) (+ (second tally) (length word)) (+ (third tally) i) (if (zerop (fourth tally)) i (min i (fourth tally))) (max i (fifth tally)))))))))) (defun test-histogram (max-value stem-size &optional (base-stem nil)) (let ((totals (list 0 0 0 0 0))) (maphash (lambda (key value) (setf totals (mapcar #'+ totals value)) (format t "~S ~S~&" key value)) (number-word-histogram max-value stem-size base-stem)) totals))

A couple of quick tests show this is still working:

(test-histogram 10000 4) "sixt" (1011 29533 6500161 16 6999) "twot" (1000 29440 2499500 2000 2999) "six" (1 3 6 6 6) "ten" (1 3 10 10 10) "eigh" (1112 33603 8585321 8 8999) "twel" (1 6 12 12 12) "twen" (10 96 245 20 29) "thre" (1101 33499 3534453 3 3999) "thir" (11 104 358 13 39) "seve" (1112 33614 7575219 7 7999) "two" (1 3 2 2 2) "one" (1 3 1 1 1) "fift" (11 93 560 15 59) "oneh" (100 1854 14950 100 199) "five" (1101 32398 5554455 5 5999) "fort" (10 86 445 40 49) "tent" (1 11 10000 10000 10000) "onet" (1000 29440 1499500 1000 1999) "elev" (1 6 11 11 11) "four" (1102 32406 4544468 4 4999) "sixh" (100 1854 64950 600 699) "nine" (1112 32502 9595423 9 9999) "twoh" (100 1854 24950 200 299) (10000 292411 50005000 14082 65406) (test-histogram 10000 2 "nine") "ninete" (1 8 19 19 19) "nineth" (1000 30440 9499500 9000 9999) "ninehu" (100 1954 94950 900 999) "ninety" (10 96 945 90 99) "nine" (1 4 9 9 9) (1112 32502 9595423 10018 11125)

I'll start this one running on the big machine.

To find out where the 51 billionth letter resides, I need to sort the word stems alphabetically and compute a rolling sum of the letter counts. The first part is straightforward:

(defun sorted-stem-letters (histogram) "Return a list of word stems and the total number of word letters up to and including that stem, ordered alphabetically." (let ((letters (list))) (maphash (lambda (key value) (push (list key (second value)) letters)) histogram) (sort letters #'string< :key #'car))) (sorted-stem-letters (number-word-histogram 10000 5)) (("eight" 33603) ("eleve" 6) ("fifte" 7) ("fifty" 86) ("five" 4) ("fiveh" 1954) ("fivet" 30440) ("forty" 86) ("four" 4) ("fourh" 1954) ("fourt" 30448) ("nine" 4) ("nineh" 1954) ("ninet" 30544) ("one" 3) ("onehu" 1854) ("oneth" 29440) ("seven" 33614) ("six" 3) ("sixhu" 1854) ("sixte" 7) ("sixth" 29440) ("sixty" 86) ("ten" 3) ("tenth" 11) ("thirt" 104) ("three" 33499) ("twelv" 6) ("twent" 96) ("two" 3) ("twohu" 1854) ("twoth" 29440))

Computing the rolling sums requires adding up all of the letter counts for the pairs up to and including the current pair, and updating the current pair with that value. `mapcon` is the obvious choice for dealing with lists `cdr` by `cdr`. A moment's thought gives the solution (working the first time, of course, without any need to build it up piece by piece):

(defun rolling-sum (name-value-list) "Return a list representing the rolling sums of the values in NAME-VALUE-LIST. NAME-VALUE-LIST is assumed to be in alphabetical (or other appropriate) order." (let ((reversed-list-of-lists (mapcon #'list (reverse name-value-list)))) (reverse (mapcar #'list (mapcar #'caar reversed-list-of-lists) (mapcar (lambda (list) (apply #'+ list)) (mapcar (lambda (list) (mapcar #'cadr list)) reversed-list-of-lists)))))) (rolling-sum (sorted-stem-letters (number-word-histogram 10000 5))) (("eight" 33603) ("eleve" 33609) ("fifte" 33616) ("fifty" 33702) ("five" 33706) ("fiveh" 35660) ("fivet" 66100) ("forty" 66186) ("four" 66190) ("fourh" 68144) ("fourt" 98592) ("nine" 98596) ("nineh" 100550) ("ninet" 131094) ("one" 131097) ("onehu" 132951) ("oneth" 162391) ("seven" 196005) ("six" 196008) ("sixhu" 197862) ("sixte" 197869) ("sixth" 227309) ("sixty" 227395) ("ten" 227398) ("tenth" 227409) ("thirt" 227513) ("three" 261012) ("twelv" 261018) ("twent" 261114) ("two" 261117) ("twohu" 262971) ("twoth" 292411))

(No, I do not recommend using this function on large lists.)

To find the stem of a particular letter index, given a rolling sum list:

(defun stem-for-letter-index (histogram index) "Return from the HISTOGRAM the word stem associated with the letter INDEX." (let ((sums (rolling-sum (sorted-stem-letters histogram)))) (first (find-if (lambda (item) (<= index (second item))) sums)))) (stem-for-letter-index (number-word-histogram 10000 5) 100000) "nineh"

The histogram test running on the big machine has finished. The form `(test-histogram 999999999 12)` has partitioned the problem into 443 stems. `stem-for-letter-index` shows that the 51 billionth letter is in a word with the stem "sixhundredse". That's not terribly helpful because that stem includes numbers from 607 to 679,999,999.

This does get me closer to a solution, however. With just a few more tools, I can build a function to iteratively search through the space of word numbers, expanding only the one stem of interest in each loop to keep memory requirements tractable:

(defun unique-stem-p (stem-data) "Indicate if the STEM-DATA represents exactly one integer." (equal (fourth stem-data) (fifth stem-data))) (defun integer-value (stem-data) "Return the value of the integer in STEM-DATA. STEM-DATA is assumed to represent a unique integer." (third stem-data)) (defun min-value (stem-data) "Return the minimum value of the integer in STEM-DATA." (fourth stem-data)) (defun max-value (stem-data) "Return the maximum value of the integer in STEM-DATA." (fifth stem-data)) (defun sorted-stem-sums (histogram) "Return a list of word stems and the total sum of integers up to and including that stem, ordered alphabetically." (let ((sums (list))) (maphash (lambda (key value) (push (list key (third value)) sums)) histogram) (sort sums #'string< :key #'car))) (defun sum-of-integers (histogram stem) "Return the sum of all integers alphabetically less than or equal to STEM in HISTOGRAM." (let ((sums (rolling-sum (sorted-stem-sums histogram)))) (second (find-if (lambda (item) (string= (first item) stem)) sums)))) (defun sum-of-letter-lengths (histogram stem) "Return from the HISTOGRAM the word stem associated with the letter INDEX." (let ((sums (rolling-sum (sorted-stem-letters histogram)))) (second (find-if (lambda (item) (string= (first item) stem)) sums)))) (defun word-for-letter-index (top-of-range index &optional (initial-stem-length 10) (stem-length-increment 10)) "Alphabetically sort the words for the integers from 1 to TOP-OF-RANGE, concatenate them, and determine the integer for the word that contains the INDEXth letter. Also return the sum of all integers for the words less than or equal to the word containing the INDEXth letter." (do* ((histogram (number-word-histogram top-of-range initial-stem-length) histogram) (stem (stem-for-letter-index histogram index) (stem-for-letter-index histogram index)) (stem-data (gethash stem histogram) (gethash stem histogram))) ((unique-stem-p stem-data) (values (integer-value stem-data) (sum-of-integers histogram stem) stem-data (sum-of-letter-lengths histogram stem))) (remhash stem histogram) (maphash (lambda (key value) (setf (gethash key histogram) value)) (number-word-histogram (max-value stem-data) stem-length-increment stem (min-value stem-data)))))

`word-for-letter-index` works by successively narrowing the search space, replacing the entry in the hash table for the stem containing the letter index with more specific stems until the stem containing the letter index refers to only one integer. It returns the integer for the word containing the letter index, plus the additional results for the problem and some sanity checking data. Running this on the big machine results in:

* (word-for-letter-index 999999999 51000000000) 676746575 413540008163475743 (1 77 676746575 676746575 676746575) 51000000000

This solution has not been optimized in any way. It may be possible to tune it enough to run in reasonable time on a laptop, although a significant amount of time is spent in the format function. That's an effort for another day. The puzzle is also highly parallelizable. Modifying `number-word-histogram` to use threads would dramatically improve even untuned performance on multi-core machines.