Get the latest tech news
Word numbers: Billion approaches (2008)
ITA Software recruits computer scientists using puzzles such as the following. If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter? In a series of posts, Dylan Thurston and I will solve this problem step by step, introducing concepts such as monoids and differentiation along the way.
The definition of* in the instance above enforces left-to-right evaluation: the leftmost choice is the outermost loop. We can now concisely define the list of 10 9 −1 strings at the core of the ITA problem, in a way that expresses its repetitive structure. If you ignore the order of strings in these lists, the code above is just a context-free grammar for numbers in English.
Or read this on Hacker News