Shahzad Bhatti

September 19, 2007

Erlang Solution for finding 51 billionth letter when converting integers from 1 to 999,999,999 are written as words.

Filed under: Computing — bhatti @ 6:54 pm

I came across an interesting problem from ITA software about If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter? For those who don’t know ITA software writes software to search airline flights and I used it when working for Orbitz. Their software is still the fastest I know and I like this problem that they posted for recruiting. Since, I am learning Erlang lately, so I gave a try in it. Here is the source code:

  1 -module(ita_puzzle).
  2 -compile(export_all).
  3
  4
  5 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  6 %%% Puzzle from ITASoftware http://www.itasoftware.com/careers/puzzles07.html
  7 %%% Word Numbers
  8 %%% "If the integers from 1 to 999,999,999 are written as words, sorted 
  9 %%%  alphabetically, and concatenated, what is the 51 billionth letter?" 
 10 %%% To be precise: if the integers from 1 to 999,999,999 are expressed in 
 11 %%% words (omitting spaces, 'and', and punctuation[1]), and sorted 
 12 %%% alphabetically so that the first six integers are
 13 %%%
 14 %%%    * eight
 15 %%%    * eighteen
 16 %%%    * eighteenmillion
 17 %%%    * eighteenmillioneight
 18 %%%    * eighteenmillioneighteen
 19 %%%    * eighteenmillioneighteenthousand
 20 %%%
 21 %%%    and the last is
 22 %%%
 23 %%%    * twothousandtwohundredtwo
 24 %%%
 25 %%% then reading top to bottom, left to right, the 28th letter completes 
 26 %%% the spelling of the integer "eighteenmillion".
 27 %%%
 28 %%% The 51 billionth letter also completes the spelling of an integer. 
 29 %%% Which one, and what is the sum of all the integers to that point?
 30 %%% [1] For example, 911,610,034 is written 
 31 %%% "ninehundredelevenmillionsixhundredtenthousandthirtyfour"; 
 32 %%% 500,000,000 is written "fivehundredmillion"; 1,709 is written 
 33 %%% "onethousandsevenhundrednine".
 34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 35
 36
 37
 38 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 39 % test function
 40 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 41 test() ->
 42     "ninehundredelevenmillionsixhundredtenthousandthirtyfour" = number_to_words(911610034),
 43     "fivehundredmillion" = number_to_words(500000000),
 44     "onethousandsevenhundrednine" = number_to_words(1709),
 45     run().
 46
 47 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 48 % Run creates 1 through 999999999, sorts them and prints the
 49 % number at 51000000000th (51-billion) letter and sum of all
 50 % numbers until that number.
 51 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 52 run() ->
 53
 54     statistics(runtime),
 55     statistics(wall_clock),
 56
 57     open(),
 58     convert_numbers(999999999),
 59     lists:foldl(fun run/2, {0, 51000000000, 0}, "abcdefghijklmnopqrstuvwxyz"),
 60     close(),
 61
 62     {_, RT} = statistics(runtime),
 63     {_, WC} = statistics(wall_clock),
 64     io:format("Completed in ~p (~p) milliseconds.~n", [RT, WC]).
 65
 66 run(Letter, {I, Max, Sum}) ->
 67     Matched = lists:sort(dets:lookup(wordfile, Letter)),
 68     lists:foldl(fun print/2, {I, Max, Sum}, Matched).
 69
 70
 71
 72
 73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 74 % Rules for creating number suffixes
 75 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 76 number_suffix(N, M) when N >= 1+303, M == 0 -> {"", 303};
 77 number_suffix(N, M) when N >= 1+100, M == 0 -> {"", 100};
 78 number_suffix(N, M) when N >= 1+63, M == 0 -> {"", 63};
 79 number_suffix(N, M) when N >= 1+60, M == 0 -> {"", 60};
 80 number_suffix(N, M) when N >= 1+57, M == 0 -> {"", 57};
 81 number_suffix(N, M) when N >= 1+54, M == 0 -> {"", 54};
 82 number_suffix(N, M) when N >= 1+51, M == 0 -> {"", 51};
 83 number_suffix(N, M) when N >= 1+48, M == 0 -> {"", 48};
 84 number_suffix(N, M) when N >= 1+45, M == 0 -> {"", 45};
 85 number_suffix(N, M) when N >= 1+42, M == 0 -> {"", 42};
 86 number_suffix(N, M) when N >= 1+39, M == 0 -> {"", 39};
 87 number_suffix(N, M) when N >= 1+36, M == 0 -> {"", 36};
 88 number_suffix(N, M) when N >= 1+33, M == 0 -> {"", 33};
 89 number_suffix(N, M) when N >= 1+30, M == 0 -> {"", 30};
 90 number_suffix(N, M) when N >= 1+27, M == 0 -> {"", 27};
 91 number_suffix(N, M) when N >= 1+24, M == 0 -> {"", 24};
 92 number_suffix(N, M) when N >= 1+21, M == 0 -> {"", 21};
 93 number_suffix(N, M) when N >= 1+18, M == 0 -> {"", 18};
 94 number_suffix(N, M) when N >= 1+15, M == 0 -> {"", 15};
 95 number_suffix(N, M) when N >= 1+12, M == 0 -> {"", 12};
 96 number_suffix(N, M) when N >= 1+9, M == 0 -> {"", 9};
 97 number_suffix(N, M) when N >= 1+6, M == 0 -> {"", 6};
 98 number_suffix(N, M) when N >= 1+3, M == 0 -> {"", 3};
 99 %%%
100 number_suffix(N, _) when N >= 1+303 -> {"centillion", 303};
101 number_suffix(N, _) when N >= 1+100 -> {"googol", 100};
102 number_suffix(N, _) when N >= 1+63 -> {"vigintillion", 63};
103 number_suffix(N, _) when N >= 1+60 -> {"novemdecillion", 60};
104 number_suffix(N, _) when N >= 1+57 -> {"octodecillion", 57};
105 number_suffix(N, _) when N >= 1+54 -> {"septendecillion", 54};
106 number_suffix(N, _) when N >= 1+51 -> {"sexdecillion", 51};
107 number_suffix(N, _) when N >= 1+48 -> {"quindecillion", 48};
108 number_suffix(N, _) when N >= 1+45 -> {"quattuordecillion", 45};
109 number_suffix(N, _) when N >= 1+42 -> {"tredecillion", 42};
110 number_suffix(N, _) when N >= 1+39 -> {"duodecillion", 39};
111 number_suffix(N, _) when N >= 1+36 -> {"undecillion", 36};
112 number_suffix(N, _) when N >= 1+33 -> {"decillion", 33};
113 number_suffix(N, _) when N >= 1+30 -> {"nonillion", 30};
114 number_suffix(N, _) when N >= 1+27 -> {"octillion", 27};
115 number_suffix(N, _) when N >= 1+24 -> {"septillion", 24};
116 number_suffix(N, _) when N >= 1+21 -> {"sextillion", 21};
117 number_suffix(N, _) when N >= 1+18 -> {"quintillion", 18};
118 number_suffix(N, _) when N >= 1+15 -> {"quadrillion", 15};
119 number_suffix(N, _) when N >= 1+12 -> {"trillion", 12};
120 number_suffix(N, _) when N >= 1+9 -> {"billion", 9};
121 number_suffix(N, _) when N >= 1+6 -> {"million", 6};
122 number_suffix(N, _) when N >= 1+3 -> {"thousand", 3};
123 number_suffix(_, M) when M >= 100 -> {"hundred", 2};
124 number_suffix(N, _) when N > 2 -> {"", 2};
125 number_suffix(_, M) when M >= 90 -> {"ninety", 1};
126 number_suffix(_, M) when M >= 80 -> {"eighty", 1};
127 number_suffix(_, M) when M >= 70 -> {"seventy", 1};
128 number_suffix(_, M) when M >= 60 -> {"sixty", 1};
129 number_suffix(_, M) when M >= 50 -> {"fifty", 1};
130 number_suffix(_, M) when M >= 40 -> {"fourty", 1};
131 number_suffix(_, M) when M >= 30 -> {"thirty", 1};
132 number_suffix(_, M) when M >= 20 -> {"twenty", 1};
133 number_suffix(_, _) -> {undefined, 0}.
134
135
136 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
137 % Rules for converting numbers to words.
138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
139 get_word("90") -> "ninety";
140 get_word("80") -> "eighty";
141 get_word("70") -> "seventy";
142 get_word("60") -> "sixty";
143 get_word("50") -> "fifty";
144 get_word("40") -> "fourty";
145 get_word("30") -> "thirty";
146 get_word("20") -> "twenty";
147 get_word("19") -> "nineteen";
148 get_word("18") -> "eighteen";
149 get_word("17") -> "seventeen";
150 get_word("16") -> "sixteen";
151 get_word("15") -> "fifteen";
152 get_word("14") -> "fourteen";
153 get_word("13") -> "thirteen";
154 get_word("12") -> "twelve";
155 get_word("11") -> "eleven";
156 get_word("10") -> "ten";
157 get_word("9") -> "nine";
158 get_word("8") -> "eight";
159 get_word("7") -> "seven";
160 get_word("6") -> "six";
161 get_word("5") -> "five";
162 get_word("4") -> "four";
163 get_word("3") -> "three";
164 get_word("2") -> "two";
165 get_word("1") -> "one";
166 get_word([$0|T]) -> get_word(T);
167 get_word(_N) -> "".
168
169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
170 % Opening Dets file
171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
172 open() ->
173     File = "./ita_puzzles.dat",
174     file:delete(File),
175     case dets:open_file(wordfile, [{type, bag}, {file, [File]}]) of
176         {ok, wordfile} ->
177             wordfile;
178         {error,_Reason} ->
179             io:format("cannot open word file ~p~n", [File]),
180             exit(eDetsOpen)
181     end.
182
183 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
184 % Closing Dets file
185 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
186 close() -> dets:close(wordfile).
187
188
189 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
190 % Converting numbers from 1 to some range and store it in dets table.
191 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
192 convert_numbers(1) ->
193     true;
194 convert_numbers(Num) ->
195     Word = number_to_words(Num),
196     dets:insert(wordfile, {hd(Word), Word, Num}),
197     convert_numbers(Num-1).
198
199 print(_X, {Max, Max, Sum}) ->
200     {Max, Max, Sum};
201 print({H, Word, Num}, {I, Max, Sum}) ->
202     %io:format("Number ~p ~p~n", [Num, Word]),
203     Len = length(Word),
204     Sum1 = Num + Sum,
205     I1 = I + Len,
206     if
207         I < Max, I1 >= Max -> Letter = lists:nth(Max-I, Word),
208             io:format("Found ~pth letter ~p, Word ~p Num ~p, sum ~p~n", [Max, Letter, Word, Num, Sum1]);
209         true ->
210             true
211     end,
212     {I1, Max, Sum1}.
213
214
215 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
216 % Converting a number to word
217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
218 number_to_words(Num) ->
219     lists:flatten(number_to_words(integer_to_list(Num), [])).
220
221 number_to_words([], Out) ->
222     Out;
223
224 number_to_words(L, Out) ->
225     Len = length(L),
226     {Suffix, Cutoff} = number_suffix(Len, list_to_integer(L)),
227     number_to_words(Suffix, Cutoff, Len, L, Out).
228
229 number_to_words(undefined, _Cutoff, _Len, L, Out) ->
230     [get_word(L)|Out];
231
232 number_to_words(Suffix, _Cutoff, Len, [_H|T], Out) when Len =< 2 ->
233     Suffix ++ get_word(T) ++ Out;
234
235 number_to_words(Suffix, Cutoff, Len, [H|_T]=L, Out) ->
236     {L1, L2} = lists:split(Len-Cutoff, L),
237     get_word(H) ++ number_to_words(L1, [Suffix]) ++ number_to_words(L2, Out).
238
239
240

This problem consists of two sub-problems, first one, which is relatively easy is to convert numbers into words, but the hardest problem is sorting and iterating over the results. And it’s going to take a long time to finish all that. I will have to run the program overnight and will post my solution once it is finished. By the way, I would have loved to see foldl method in dets that takes order_by function, unfortunately I had to create some hack to get chunks of data and then sort in memory. Any suggestions to improve this code would be welcome.

No Comments

No comments yet.

RSS feed for comments on this post. TrackBack URL

Sorry, the comment form is closed at this time.

Powered by WordPress