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.