Word numbers, Part 1: Billion approaches
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. We will use the programming language Haskell: every post will be a literate program that you can run as is. For example, you can download this post as a program.
Our basic strategy is quintessential computer science: first write a program to specify the problem, then interpret the program creatively to find the solution before the the universe ends. Our first step, then, is to specify how to write integers as words in English. Such a specification defines a long list of strings
["one", "two", ..., "onehundred", ..., "ninehundredninetyninemillionninehundredninetyninethousandninehundredninetynine"]
of type [String] . There is a lot of repetitive structure within and among these strings. We need to express this structure concisely so that we can exploit it later to solve the problem efficiently.
The structure we will use is that lists of strings form a seminearring. To use the nice-looking symbols + and * for operations in a seminearring, we hide the definitions of these operators from the Prelude , but we will keep the same infix precedences.
{-# OPTIONS -W -fglasgow-exts #-} module WordNumbers1 where import Prelude hiding ((+), (*), sum, product) import qualified Prelude as P infixl 6 + infixl 7 *
A seminearring is first of all a monoid. A monoid is a set along with an associative operation + and its identity element zero .
... continue reading