Shahzad Bhatti Welcome to my ramblings and rants!

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.

September 15, 2007

PROLOG roots in ERLANG

Filed under: Computing — bhatti @ 3:27 pm

I have been trying Erlang lately and since Erlang has a lot of its roots in PROLOG and its first VM (JAM) was written in PROLOG, I thought I would look at some similarities in syntax. So I picked up “PROLOG Though Examples by Kononenko and Lavrac”, which has been collecting dust on my bookshelf since 1989. Here are some similarities I found:

  • atoms or symbols start with lower case.
  • variables start with Uppercase or underscore (anonymous variables).
  • statements end with period.
  • structures are similar to records.
  • lists are declared same, with [1, 2, 3] syntax. Also, [Head|Tail] syntax is same.
  • strings are represented as array of ASCII codes.
  • arithmetic operators are same “> < >= =< =:= =\= div mod”
  • a lot of list functions are similar to BIFs in ERLANG such as member, conc (called append in ERLANG), insert, delete.
  • both can read terms from a file using consult function.

Despite all these similarities both languages are fundamentally different, as PROLOG was written for Expert systems and its interpreter took in facts and rules and deduced inferences and included sophisticated backtracking (e.g. cut) features. While, ERLANG is a functional language with strong support for concurrent and distributed applications.

September 12, 2007

Erlang solutions to Problem 1-25 of “L-99: Ninety-Nine Lisp Problems”

Filed under: Computing — admin @ 1:57 pm

L-99: Ninety-Nine Lisp Problems provides a good exercise for learning new language so here is my attempt at Erlang solutions of problems 1 through 25:

  1 -module(lisp99).
  2 -compile(export_all).
  3
  4 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  5 % My solutions to L-99: Ninety-Nine Lisp Problems from 
  6 % http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html
  7 % Based on a Prolog problem list by werner.hett@hti.bfh.ch
  8 % Note: I am using BIFs for a lot of solutions because learning language library APIs is just as 
  9 % important as learning language constructs.
 10 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 11
 12 %%%%%%%%%%%%%%%%%%%%%%%%%
 13 %%% P01 (*) Find the last box of a list.
 14 %%%%%%%%%%%%%%%%%%%%%%%%%
 15 last(L) ->
 16     lists:nthtail(length(L)-1, L).
 17
 18 %%%%%%%%%%%%%%%%%%%%%%%%%
 19 %%% P02 (*) Find the last but one box of a list.
 20 %%%%%%%%%%%%%%%%%%%%%%%%%
 21 last_but(L) ->
 22     lists:nthtail(length(L)-2, L).
 23
 24 %%%%%%%%%%%%%%%%%%%%%%%%%
 25 %%% P03 (*) Find the K'th element of a list.
 26 %%%%%%%%%%%%%%%%%%%%%%%%%
 27 kth(L, K) ->
 28     lists:nth(K, L).
 29
 30 %%%%%%%%%%%%%%%%%%%%%%%%%
 31 %%% P04 (*) Find the number of elements of a list.
 32 %%%%%%%%%%%%%%%%%%%%%%%%%
 33 len(L) ->
 34     length(L).
 35
 36 %%%%%%%%%%%%%%%%%%%%%%%%%
 37 %%% P05 (*) Reverse a list.
 38 %%%%%%%%%%%%%%%%%%%%%%%%%
 39 rev(L) ->
 40     lists:reverse(L).
 41
 42 %%%%%%%%%%%%%%%%%%%%%%%%%
 43 %%% P06 (*) Find out whether a list is a palindrome.
 44 %%%%%%%%%%%%%%%%%%%%%%%%%
 45 palindrome(L) ->
 46     L == lists:reverse(L).
 47
 48
 49 %%%%%%%%%%%%%%%%%%%%%%%%%
 50 %%% P07 (**) Flatten a nested list structure.
 51 %%%%%%%%%%%%%%%%%%%%%%%%%
 52 flatten(L) ->
 53     lists:flatten(L).
 54
 55 %%%%%%%%%%%%%%%%%%%%%%%%%
 56 %%% P08 (**) Eliminate consecutive duplicates of list elements.
 57 %%%%%%%%%%%%%%%%%%%%%%%%%
 58 compress(L) ->
 59   lists:reverse(lists:foldl(fun compress/2, [], L)).
 60 compress(H, [H|T]) ->
 61   [H|T];
 62 compress(H, L) ->
 63   [H|L].
 64
 65
 66 %%%%%%%%%%%%%%%%%%%%%%%%%
 67 %%% P09 (**) Pack consecutive duplicates of list elements into sublists.
 68 %%%%%%%%%%%%%%%%%%%%%%%%%
 69 pack(L) ->
 70   lists:reverse(lists:foldl(fun pack/2, [], L)).
 71 pack(H, [[H|T]|TT]) ->
 72   [[H,H|T]|TT];
 73 pack(H, L) ->
 74   [[H]|L].
 75
 76 %%%%%%%%%%%%%%%%%%%%%%%%%
 77 %%% P10 (*) Run-length encoding of a list.
 78 %%%%%%%%%%%%%%%%%%%%%%%%%
 79 encode(L) ->
 80   lists:reverse(lists:foldl(fun encode/2, [], L)).
 81 encode(H, []) ->
 82   [[1, H]];
 83 encode(H, [[N,H]|T]) ->
 84   [[N+1,H]|T];
 85 encode(H, [[_N,_X]|_T]=L) ->
 86   [[1,H]|L].
 87
 88 %%%%%%%%%%%%%%%%%%%%%%%%%
 89 %%% P11 (*) Modified run-length encoding.
 90 %%%%%%%%%%%%%%%%%%%%%%%%%
 91 encode_modified(L) ->
 92   lists:reverse(lists:foldl(fun encode_modified/2, [], L)).
 93 encode_modified(H, []) ->
 94   [H];
 95 encode_modified(H, [H|T]) ->
 96   [[2,H]|T];
 97 encode_modified(H, [[N,H]|T]) ->
 98   [[N+1,H]|T];
 99 encode_modified(H, [[_N,_X]|_T]=L) ->
100   [H|L];
101 encode_modified(H, [_X|_T]=L) ->
102   [H|L].
103
104 %%%%%%%%%%%%%%%%%%%%%%%%%
105 %%% P12 (**) Decode a run-length encoded list.
106 %%%%%%%%%%%%%%%%%%%%%%%%%
107 decode(L) ->
108   lists:reverse(lists:foldl(fun decode/2, [], L)).
109 decode([N,H], L) ->
110   lists:duplicate(N, H) ++ L;
111 decode(H, L) ->
112   [H|L].
113
114 %%%%%%%%%%%%%%%%%%%%%%%%%
115 %%% P13 (**) Run-length encoding of a list (direct solution).
116 %%%%%%%%%%%%%%%%%%%%%%%%%
117 direct_encode(L) ->
118     encode_modified(L). %% it already creates RLE by counting
119
120 %%%%%%%%%%%%%%%%%%%%%%%%%
121 %%% P14 (*) Duplicate the elements of a list.
122 %%%%%%%%%%%%%%%%%%%%%%%%%
123 dupli(L) ->
124     lists:reverse(lists:foldl(fun dupli/2, [], L)).
125 dupli(H, L) ->
126     [H,H|L].
127
128 %%%%%%%%%%%%%%%%%%%%%%%%%
129 %%% P15 (**) Replicate the elements of a list a given number of times.
130 %%%%%%%%%%%%%%%%%%%%%%%%%
131 repli(L, N) ->
132     {N, L1} = lists:foldl(fun do_repli/2, {N,[]}, L),
133     lists:reverse(L1).
134 do_repli(H, {N,L}) ->
135     {N, lists:duplicate(N, H) ++ L}.
136
137 %%%%%%%%%%%%%%%%%%%%%%%%%
138 %%% P16 (**) Drop every N'th element from a list.
139 %%%%%%%%%%%%%%%%%%%%%%%%%
140 drop(L, N) ->
141     {_I, N, L1} = lists:foldl(fun do_drop/2, {1,N,[]}, L),
142     lists:reverse(L1).
143 do_drop(H, {I,N,L}) ->
144     Rem = I rem N,
145     if
146         Rem == 0 ->
147             {1,N,L};
148         true ->
149             {I+1,N,[H|L]}
150     end.
151
152 %%%%%%%%%%%%%%%%%%%%%%%%%
153 %%% P17 (*) Split a list into two parts; the length of the first part is given.
154 %%%%%%%%%%%%%%%%%%%%%%%%%
155 split(L,N) ->
156     lists:split(N,L).
157
158 %%%%%%%%%%%%%%%%%%%%%%%%%
159 %%% P18 (**) Extract a slice from a list.
160 %%%%%%%%%%%%%%%%%%%%%%%%%
161 slice(L, Start, End) ->
162     lists:sublist(L, Start, End-Start+1).
163
164
165 %%%%%%%%%%%%%%%%%%%%%%%%%
166 %%% P19 (**) Rotate a list N places to the left.
167 %%%%%%%%%%%%%%%%%%%%%%%%%
168 rotate(L, N) ->
169     N1 = if
170         N > 0 ->
171             N;
172         true ->
173             length(L) + N
174     end,
175     Len = length(L),
176     lists:reverse(do_rotate(N1, Len, L, [])).
177
178 do_rotate(I, Len, In, Out) ->
179     I1 = (I rem Len)+1,       % In Erlang offset of list starts from 1 
180     Out1 = [lists:nth(I1, In)|Out],
181     if
182         length(Out1) == Len ->
183             Out1;
184         true ->
185             do_rotate(I1, Len, In, Out1)
186     end.
187
188 %%%%%%%%%%%%%%%%%%%%%%%%%
189 %%% P20 (*) Remove the K'th element from a list.
190 %%%%%%%%%%%%%%%%%%%%%%%%%
191 remove_at(L, N) ->
192     Elem = lists:nth(N,L),
193     lists:delete(Elem,L).
194
195
196 %%%%%%%%%%%%%%%%%%%%%%%%%
197 %%% P21 (*) Insert an element at a given position into a list.
198 %%%%%%%%%%%%%%%%%%%%%%%%%
199 insert_at(Elem, L, N) ->
200     {L1,L2} = lists:split(N-1,L),         % there got to be better way
201     L1 ++ [Elem] ++ L2.
202
203 %%%%%%%%%%%%%%%%%%%%%%%%%
204 %%% P22 (*) Create a list containing all integers within a given range.
205 %%%%%%%%%%%%%%%%%%%%%%%%%
206 range(Start, End) ->
207     lists:seq(Start, End).
208
209 %%%%%%%%%%%%%%%%%%%%%%%%%
210 %%% P23 (**) Extract a given number of randomly selected elements from a list.
211 %%%%%%%%%%%%%%%%%%%%%%%%%
212 rnd_select(L, N) ->
213     rnd_select(N, L, []).
214 rnd_select(N, In, Out) ->
215     I = random:uniform(length(In)),
216     Out1 = [lists:nth(I, In) | Out],
217     In1 = remove_at(In, I),
218     if
219         length(Out1) == N ->
220             Out1;
221         true ->
222             rnd_select(N, In1, Out1)
223     end.
224
225
226 %%%%%%%%%%%%%%%%%%%%%%%%%
227 %%% P24 (*) Lotto: Draw N different random numbers from the set 1..M.
228 %%%%%%%%%%%%%%%%%%%%%%%%%
229 lotto_select(Count, Max) ->
230     L = range(1, Max),
231     rnd_select(L, Count).
232
233 %%%%%%%%%%%%%%%%%%%%%%%%%
234 %%% P25 (*) Generate a random permutation of the elements of a list.
235 %%%%%%%%%%%%%%%%%%%%%%%%%
236 rnd_permu(L) ->
237     rnd_select(L, length(L)).
238
239
240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
241 % Tests
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
243 test_last() ->
244     last("abcd").
245
246 test_last_but() ->
247     last_but("abcd").
248
249 test_kth() ->
250     [kth("abcd", 3)].
251
252 test_len() ->
253     len("abcd").
254
255 test_rev() ->
256     rev("abcd").
257
258 test_flatten() ->
259     flatten([$a, [$b, [c, d], e]]).
260
261 test_compress() ->
262     compress("aaaabccaadeeee").
263
264 test_pack() ->
265     pack("aaaabccaadeeee").
266
267 test_encode() ->
268     encode("aaaabccaadeeee").
269
270 test_encode_modified() ->
271     encode_modified([1,1,1,1,2,3,3,1,1,4,5,5,5,5]).
272
273 test_decode() ->
274     decode(encode_modified([1,1,1,1,2,3,3,1,1,4,5,5,5,5])).
275
276 test_dupli() ->
277     dupli("abccd").
278
279 test_repli() ->
280     repli("abccd",3).
281
282 test_drop() ->
283     drop("abcdefghik",3).
284
285 test_split() ->
286     split("abcdefghik",3).
287
288 test_slice() ->
289     slice("abcdefghik",3,7).
290
291 test_rotate1() ->
292     rotate("abcdefgh",3).
293
294 test_rotate2() ->
295     rotate("abcdefgh",-2).
296
297 test_remove_at() ->
298     remove_at("abcd", 2).
299
300 test_insert_at() ->
301     insert_at("alfa", "abcd", 2).
302
303 test_range() ->
304     range(4,9).
305
306 test_rnd_select() ->
307     rnd_select("abcdefgh", 3).
308
309 test_lotto_select() ->
310     lotto_select(6,49).
311
312 test_rnd_permu() ->
313     rnd_permu("abcdef").
314
315

September 10, 2007

Rosetta solution in Erlang

Filed under: Computing — bhatti @ 9:17 pm

I found a number of solutions of Rosetta problem at Yet Another Rosetta Code Problem (Perl, Ruby, Python, Haskell), but didn’t see any solution in Erlang, so here it is:

-module(rosetta).
-compile(export_all).

test() ->
  rosetta("ZYEEEEEABBCCCDDDDF").

rosetta(L) ->
  lists:reverse(lists:foldl(fun rosetta/2, [], L)).
rosetta(H, [[H|T]|TT]) ->
  [[H,H|T]|TT];
rosetta(H, L) ->
  [[H]|L].

September 5, 2007

Performance Testing with C++, Java, Ruby and Erlang

Filed under: Computing — admin @ 4:22 pm

I came across an interesting blog on classical distributed Byzantine Generals Problem from Mark Nelsons’ blog. He showed C++ implementation of Leslie Lamport algorithm. It seemed like a natural fit Erlang, but instead of writing directly in Erlang, I first wrote the algorithm into Java and Ruby (with slight redesign). Unfortunately, the original C++ source, and my Java and Ruby versions are not really truly distributed or concurrent. I just wanted to translate the original algorithm without changing a whole a lot, but Erlang gave you both distributing features and concurrency for free. You can learn about the Byzantine General problem from Mark Nelson’s post or from this brief summary, or the Wikipedia. The algorithm is heavily based on message communication where a general sends a message value (0 or 1), to his lieutenants and each lieutenant sends the value to all other lieutenants including himself. After some specific number of rounds a consensus is reached. The original C++ code defines a Node structure to store input/output values of each process, a Traits class to store configuration and a method to come up with new values. Since, some processes can be faulty (or traiters), the Traits class determines the value that a process will return. The most of the fun happens in the Process class that performs all message communication. You can download the original C++ source code.

I slightly changed the structure and got rid of static attributes and methods. In my design, the application consists of following modules:

  • Configuration – for storing configuration for simulation such as number of processes, rounds, source (general) process.
  • Strategy – that determines the value that should be returned by the process.
  • Repository – that stores hierarchical paths for messages that were communicated by the processes.
  • Process – GeneralProcesses classification that send or receive messages.
  • Engine – drives the algorithm.
  • Test – that actually invokes engine with different parameters and stores timings.

Here is the Java implementation (I am showing multiple java classes here, but you can download the complete source code from here. I kept most of the algorithm as it was, which turned out to be really memory hog when you increase number of processes. In fact, I could not run the Java application for more than 10 processes with 512MB memory. Here is the source code for the Java version:

public enum Value {
    ZERO,
    ONE,
    FAULTY,
    UNKNOWN
}
public interface ValueStrategy {

    public Node getSourceValue();

    public Value getValue(
            Value value,
            int source,
            int destination,
            String path);


    public Value getDefaultValue();


    public boolean isFaulty(int process);
}
public interface Broadcaster {
    public void broadcast(int round, int id, Node source, String path);
}
public interface PathRepository {

    public void generateChildren();

    public List<String> getRankList(int rank, int source);

    public List<String> getPathChildren(String path);
}
public class Configuration {
    private int source;
    private int roundsOfMessages;
    private int numberOfProcesses;

    //
    Configuration(int source, int roundsOfMessages, int numberOfProcesses) {
        this.source = source;
        this.roundsOfMessages = roundsOfMessages;
        this.numberOfProcesses = numberOfProcesses;
    }

    //
    public int getSource() {
        return source;
    }


    public int getRoundsOfMessages() {
        return roundsOfMessages;
    }


    public int getNumberOfProcesses() {
        return numberOfProcesses;
    }
}
public class DefaultEngine implements Engine, Broadcaster {
    static final boolean debug = System.getProperty("debug", "false").equals("true");
    private Configuration configuration;
    private PathRepository repository;
    private List<Process> processes;
    private ValueStrategy strategy;

    //
    public DefaultEngine(int source, int roundsOfMessages, int numberOfProcesses) {
        this.configuration = new Configuration(source, roundsOfMessages, numberOfProcesses);
        this.strategy = new DefaultValueStrategy(configuration);
        this.repository = new DefaultPathRepository(configuration);
        this.processes = new ArrayList<Process>();
    }

    public void broadcast(int round, int id, Node source, String path) {
        for (int j = 0; j < configuration.getNumberOfProcesses(); j++) {
            if (j != configuration.getSource()) {
                Value value = strategy.getValue(
                        source.input,
                        id,
                        j,
                        path);
                if (debug) {
                    String sourcePath = path.substring(0, path.length() - 1);
                    System.out.println("Sending for round " + round + " from process " + id + " to " + j + ": {" + value +
                            ", " + path + ", " + Value.UNKNOWN + "}, getting value from source " + sourcePath);
                }
                getProcesses().get(j).receiveMessage(path, new Node(value, Value.UNKNOWN));
            }
        }
    }


    public List<Process> getProcesses() {
        return processes;
    }

    public void run() {
        //
        // Starting at round 0 and working up to round M, call the
        // SendMessages() method of each process. It will send the appropriate
        // message to all other sibling processes.
        //
        for (int i = 0; i <= configuration.getRoundsOfMessages(); i++) {
            for (int j = 0; j < configuration.getNumberOfProcesses(); j++) {
                processes.get(j).sendMessages(i);
            }
        }

        //
        // All that is left is to print out the results. For non-faulty processes,
        // we call the Decide() method to see what what the process decision was
        //
        for (int j = 0; j < configuration.getNumberOfProcesses(); j++) {
            if (processes.get(j).isSource()) System.out.print("Source ");
            System.out.print("Process " + j);
            if (!processes.get(j).isFaulty()) {
                System.out.print(" decides on value " +
                        processes.get(j).decide());
            } else {
                System.out.print(" is faulty");
            }
            System.out.println();
        }
    }


    public void start() {
        //
        for (int i = 0; i < configuration.getNumberOfProcesses(); i++) {
            Process process = i == configuration.getSource() ? new GeneralProcess(i, configuration, repository, this, strategy) : new Process(i, configuration, repository, this, strategy);
            processes.add(process);
        }
        repository.generateChildren();
    }
}
public class DefaultPathRepository implements PathRepository {
    private Map<String, List<String>> children;
    private Map<Integer, Map<Integer, List<String>>> pathByRank;
    private Configuration configuration;
    static final boolean debug = System.getProperty("debug", "false").equals("true");

    //
    public DefaultPathRepository(Configuration configuration) {
        this.configuration = configuration;
        this.children = new HashMap<String, List<String>>();
        this.pathByRank = new HashMap<Integer, Map<Integer, List<String>>>();
    }

    public Map<String, List<String>> getChildren() {
        return children;
    }

    public List<String> getPathChildren(String path) {
        List<String> pathList = children.get(path);
        if (pathList == null) {
            pathList = new ArrayList<String>();
            children.put(path, pathList);
        }
        return pathList;
    }


    public List<String> getRankList(int rank, int source) {
        Map<Integer, List<String>> pathMap = pathByRank.get(rank);
        if (pathMap == null) {
            pathMap = new HashMap<Integer, List<String>>();
            pathByRank.put(rank, pathMap);
        }
        List<String> pathList = pathMap.get(source);
        if (pathList == null) {
            pathList = new ArrayList<String>();
            pathMap.put(source, pathList);
        }
        return pathList;
    }

    public void generateChildren() {
        generateChildren(configuration.getSource(), new boolean[configuration.getNumberOfProcesses()], "", 0);
    }


    private void generateChildren(int source, boolean[] ids, String path, int rank) {
        ids[source] = true;
        path += toCharString(source);
        getRankList(rank, source).add(path);

        //
        if (rank < configuration.getRoundsOfMessages()) {
            for (int i = 0; i < ids.length; i++) {
                if (!ids[i]) {
                    boolean[] newIds = new boolean[ids.length];
                    System.arraycopy(ids, 0, newIds, 0, ids.length);
                    generateChildren(i, newIds, path, rank + 1);
                    getPathChildren(path).add(path + toCharString(i));
                }
            }
        }

        //
        if (debug) {
            System.out.print("generateChildren(" + source + "," + rank + "," + path + "), children = ");
            List<String> list = getPathChildren(path);
            for (String s : list) {
                System.out.print(s + " ");
            }
            System.out.println();
        }
    }


    //
    private char toChar(int n) {
        return (char) (n + '0');
    }

    private String toCharString(int n) {
        return String.valueOf(toChar(n));
    }
}
public class DefaultValueStrategy implements ValueStrategy {
    private Configuration configuration;
    private Node sourceValue;

    //
    DefaultValueStrategy(Configuration configuration) {
        this.configuration = configuration;
        this.sourceValue = new Node(Value.ZERO, Value.UNKNOWN);
    }

    //
    // This method returns the true value of the source's value. The source may send
    // faulty values to other processes, but the Node returned by this value will be
    // in its root node.
    //
    // In this case, the General's node has in input value of 0, which makes that
    // the desired value. Of course, since the General is faulty, this doesn't really
    // matter.
    //
    public Node getSourceValue() {
        return sourceValue;
    }

    //
    // During message, GetValue() is called to get the value returned by a given process
    // during a messaging round. 'value' is the input value that it should be sending to
    // the destination process (if it isn't faulty), source is the source process ID,
    // destination is the destination process ID, and Path is the path being used for this
    // particular message.
    //
    // In this particular implementation, we have two faulty processes - the source
    // process, which returns a sort-of random value, and process ID 2, which returns
    // a ONE always, in contradiction of the General's desired value of 0.
    //
    public Value getValue(Value value, int source, int destination, String path) {
        if (configuration.getSource() == source) return (destination & 1) != 0 ? Value.ZERO : Value.ONE;
        else if (source == 2) return Value.ONE;
        return value;
    }


    //
    // When breaking a tie, GetDefault() is used to get the default value.
    //
    // This is an arbitrary decision, but it has to be consistent across all processes.
    // More importantly, the processes have to arrive at a correct decision regardless
    // of whether the default value is always 0 or always 1. In this case we've set it to
    // a value of 1.
    //
    public Value getDefaultValue() {
        return Value.ONE;
    }

    //
    // This method is used to identify fault processes by ID
    //
    public boolean isFaulty(int process) {
        return process == configuration.getSource() || process == 2;
    }
}
public interface Engine extends Runnable {
    public void start();
}
public class GeneralProcess extends Process {
    public GeneralProcess(int id, Configuration configuration, PathRepository repository, Broadcaster broadcaster, ValueStrategy strategy) {
        super(id, configuration, repository, broadcaster, strategy);
        nodes.put("", strategy.getSourceValue());
    }


    @Override
    public Value decide() {
        //
        // The source process doesn't have to do all the work - since it's the decider,
        // it simply looks at its input value to pick the appropriate decision value.
        //
        return nodes.get("").input;
    }
}

public class Node {
    Value input;
    Value output;

    Node() {
        this(Value.FAULTY, Value.FAULTY);
    }

    Node(Value input, Value output) {
        this.input = input;
        this.output = output;
    }
}
public class Process {
    protected int id;
    protected Configuration configuration;
    protected ValueStrategy strategy;
    protected Map<String, Node> nodes;
    protected PathRepository repository;
    protected Broadcaster broadcaster;
    static final boolean debug = System.getProperty("debug", "false").equals("true");

    public Process(int id, Configuration configuration, PathRepository repository, Broadcaster broadcaster, ValueStrategy strategy) {
        this.id = id;
        this.strategy = strategy;
        this.repository = repository;
        this.broadcaster = broadcaster;
        this.configuration = configuration;
        this.nodes = new HashMap<String, Node>();
    }

    static int totalMessages;

    //
    //
    // Receiving a message is pretty simple here, it means that some other process
    // calls this method on the current process with path and a node. All we do
    // is store the value, we'll use it in the next round of messaging.
    //
    public void receiveMessage(String path, Node node) {
        nodes.put(path, node);
        totalMessages++;
    }


    //
    // After constructing all messages, you need to call SendMessages on each process,
    // once per round. This routine will send the appropriate messages for each round
    // to all th eother processes listed in the vector passed in as an argument.
    //
    // Deciding on what messages to send is pretty simple. If we look at the static
    // map pathsByRank, indexed by round and the processId of this process, it gives
    // the entire set of taraget paths that this process needs to send messages to.
    // So there is an iteration loop through that map, and this process sends a message
    // to the correct target process for each path in the map.
    //
    public void sendMessages(int round) {
        List<String> pathList = repository.getRankList(round, id);
        for (String path : pathList) {
            String sourcePath = path.substring(0, path.length() - 1);
            Node source = nodes.get(sourcePath);
            if (source == null) throw new IllegalStateException("Failed to find source node for " + sourcePath);
            broadcaster.broadcast(round, id, source, path);
        }
    }

    //
    // After all messages have been sent, it's time to Decide.
    //
    // This part of the algorithm follows the description in the article closely.
    // It has to work its way from the leaf values up to the root of the tree.
    // The first round consists of going to the leaf nodes, and copying the input
    // value to the output value.
    //
    // All subsequent rounds consist of getting the majority of the output values from
    // each nodes children, and copying that to the nodes output value.
    //
    // When we finally reach the root node, there is only one node with an output value,
    // and that represents this processes decision.
    //
    public Value decide() {
        //
        // Step 1 - set the leaf values
        //
        for (int i = 0; i < configuration.getNumberOfProcesses(); i++) {
            List<String> pathList = repository.getRankList(configuration.getRoundsOfMessages(), i);
            for (String path : pathList) {
                Node node = nodes.get(path);
                node.output = node.input;
            }
        }
        //
        // Step 2 - work up the tree
        //
        for (int round = configuration.getRoundsOfMessages() - 1; round >= 0; round--) {
            for (int i = 0; i < configuration.getNumberOfProcesses(); i++) {
                List<String> pathList = repository.getRankList(round, i);
                for (String path : pathList) {
                    Node node = nodes.get(path);
                    node.output = getMajority(path);
                }
            }
        }
        List<String> pathList = repository.getRankList(0, configuration.getSource());
        String topPath = pathList.get(0);
        return nodes.get(topPath).output;
    }

    //
    // This routine calculates the majority value for the children of a given
    // path. The logic is pretty simple, we increment the count for all possible
    // values over the children. If there is a clearcut majority, we return that,
    // otherwise we return the default value defined by the strategy class.
    //
    public Value getMajority(String path) {
        Map<Value, Integer> counts = new HashMap<Value, Integer>();
        counts.put(Value.ONE, new Integer(0));
        counts.put(Value.ZERO, new Integer(0));
        counts.put(Value.UNKNOWN, new Integer(0));
        Collection<String> list = repository.getPathChildren(path);
        int n = 0;
        if (list == null) {
            if (debug) System.out.println("No child found for '" + path + "'");
        } else {
            n = list.size();
            for (String child : list) {
                Node node = nodes.get(child);
                if (node != null) {
                    counts.put(node.output, counts.get(node.output) + 1);
                } else if (debug) {
                    //System.out.println("Could not find node for count with path " + child);
                }
            }
        }
        //
        //
        if (counts.get(Value.ONE) > (n / 2)) return Value.ONE;
        else if (counts.get(Value.ZERO) > (n / 2)) return Value.ZERO;
        else if (counts.get(Value.ONE).intValue() == counts.get(Value.ZERO).intValue() &&
                counts.get(Value.ONE) == (n / 2)) return strategy.getDefaultValue();
        return Value.UNKNOWN;
    }


    //
    // A utility routine that tells whether a given process is faulty
    //
    public boolean isFaulty() {
        return strategy.isFaulty(id);
    }

    //
    // Another somewhat handy utility routine
    //
    public boolean isSource() {
        return configuration.getSource() == id;
    }
}

 Here is the ruby version, which is pretty much same as the Java version (except a bit smaller). The operator overloading and power of collections give Ruby the terseness over Java version. Again, the application is consisted of classes for process, strategy, repository, engine, node, and config. The benchmarks are kicked off from ByzGeneralTest, which calls Engine, which in turn creates Repository, Strategy, Generals and LProcesses (lieutenants).

class Configuration
	attr_reader :source, :num_rounds, :num_procs
	def initialize(source, num_rounds, num_procs)
		@source = source
		@num_rounds = num_rounds
		@num_procs = num_procs
	end
	def to_s
		"#{@source}|#{@num_rounds}|#{@num_procs}"
	end
end
class Node
	attr_accessor :input
	attr_accessor :output
	def initialize(input = Value::FAULTY, output = Value::FAULTY)
		@input = input
		@output = output
	end
	def to_s
		"#{@input}/#{@output}"
	end
end
class Value
	ZERO = '0'
	ONE = '1'
	FAULTY = 'X'
	UNKNOWN = '?'
end
class PathRepository
	attr_accessor :children
	attr_accessor :path_by_rank
	attr_accessor :config
		def initialize(config)
		@config = config
		@children = Hash.new {|h,k| h[k] = []}
		@path_by_rank = Hash.new {|h,k| h[k] = Hash.new {|hh,kk| hh[kk] = []}}
	end
		def path_children(path)
		@children[path]
	end
		def rank_list(rank, source)
		@path_by_rank[rank][source]
	end
		def generate_children(source = @config.source, ids = new_ids, path = "", rank = 0)
		ids[source] = true
		path = "#{path}#{source}"
		@path_by_rank[rank][source].push path
				if rank < @config.num_rounds
			for i in 0...@config.num_procs
			unless ids[i]
				generate_children(i, new_ids(ids), path, rank + 1)
				@children[path].push("#{path}#{i}")
			end
		end
	end
		if (DEBUG)
		print("generate_children(#{source}, #{rank}, #{path}, children = ")
		@children[path].each do |child|
			print(child + " ")
		end
		puts("")
	end
end
private
def new_ids(old_ids = nil)
	#old_ids.nil? ? Array.new(@config.num_procs) {|i| false} : Array.new(old_ids)
	old_ids.nil? ? Hash.new {|h,k| h[k] = false} : old_ids.dup
end
end
class ValueStrategy
	attr_accessor :config
	attr_accessor :source_value
		def initialize(config)
		@config = config
		@source_value = Node.new(Value::ZERO, Value::UNKNOWN)
	end
		def create_value(value, source, destination, path)
		if @config.source == source
			(destination & 1) != 0 ? Value::ZERO : Value::ONE
		elsif source == 2
			Value::ONE
		else
			value
		end
	end
			def get_default
		return Value::ONE
	end
		def faulty?(process)
		process == @config.source || process == 2
	end
end
class LProcess
	@@total_messages = 0
	attr_reader :id
	attr_reader :config
	attr_reader :strategy
	attr_reader :repository
	attr_reader :broadcaster
	#
	def initialize(id, config, repository, broadcaster, strategy)
		@id = id
		@config = config
		@repository = repository
		@strategy = strategy
		@broadcaster = broadcaster
		@nodes = Hash.new
	end
			def self.total_messages
		@@total_messages
	end
	def self.reset_total_messages
		@@total_messages = 0
	end
		def receive_message(path, node)
		@nodes[path] = node
		@@total_messages += 1
	end
		def send_messages(round)
		@repository.rank_list(round, @id).each do |path|
			source_path = path.slice(0, path.length-1)
			source = @nodes[source_path]
			raise "Source path #{source_path} not found" if source.nil?
			broadcaster.broadcast(round, @id, source, path)
		end
	end
		def decide
		#### Step 1 - set the leaf values
		for i in 0...@config.num_procs
		@repository.rank_list(@config.num_rounds, i).each do |path|
			node = @nodes[path]
			node.output = node.input
		end
	end
		### Step 2 - work up the tree
	(@config.num_rounds - 1).step 0, -1 do |round|
		for i in 0...@config.num_procs
		@repository.rank_list(round, i).each do |path|
			@nodes[path].output = find_majority(path)
		end
	end
end
path_list = @repository.rank_list(0, @config.source)
top_path = path_list[0]
@nodes[top_path].output
end
def find_majority(path)
	counts = Hash.new(0)
	list = @repository.path_children(path)
	n = 0
	if list
		n = list.size
		list.each do |child|
			node = @nodes[child]
			counts[node.output] = counts[node.output] + 1 if node
		end
	end
	#
	if (counts[Value::ONE] > ( n / 2 ) )
		Value::ONE
	elsif (counts[Value::ZERO] > ( n / 2 ) )
		Value::ZERO
	elsif (counts[Value::ONE] == counts[Value::ZERO] &&
	counts[Value::ONE] == (n / 2))
	@strategy.get_default
else
	Value::UNKNOWN
end
end
def faulty?
	@strategy.faulty?(id)
end
def source?
	@config.source == id
end
end
class GeneralProcess < LProcess
	def initialize(id, config, repository, broadcaster, strategy)
		super(id, config, repository, broadcaster, strategy)
		@nodes[""] = @strategy.source_value
	end
			def decide
		@nodes[""].input
	end
end
class Engine
	attr_reader :config
	attr_reader :repository
	attr_reader :procs
	attr_reader :strategy
		def initialize(source, num_rounds, num_procs)
		@config = Configuration.new(source, num_rounds, num_procs)
		@strategy = ValueStrategy.new(config)
		@repository = PathRepository.new(config)
		@procs = []
	end
		def broadcast(round, id, source, path)
		for j in 0...@config.num_procs
		unless j == @config.source
			value = @strategy.create_value(source.input, id, j, path)
			if (DEBUG)
				source_path = path.slice(0, path.length-1)
				puts("Sending for round #{round} from process #{id} to #{j} : #{value}, #{path}, #{Value::UNKNOWN}, getting value from source #{source_path}")
			end
			@procs[j].receive_message(path, Node.new(value, Value::UNKNOWN))
		end
	end
end
def run
	for i in 0...@config.num_rounds
	for j in 0...@config.num_procs
	@procs[j].send_messages(i)
end
end
for j in 0...@config.num_procs
print("Source ") if @procs[j].source?
print("Process #{j}")
unless @procs[j].faulty?
	print("decides on value #{@procs[j].decide}")
else
	print(" is faulty")
end
puts("")
end
end
def start
	for i in 0...@config.num_procs
	process = i == @config.source ?
	GeneralProcess.new(i, @config, @repository, self, @strategy) :
	LProcess.new(i, @config, @repository, self, @strategy)
	@procs.push(process)
end
@repository.generate_children
end
end
class ByzGeneralTest < Test::Unit::TestCase
	def setup
	end
			def run_engine(m, n, source)
		r = Benchmark.realtime() do
			puts("Starting|#{m}|#{n}|#{source}")
			engine = Engine.new(source, m, n)
			engine.start
			engine.run
		end
		puts("Finished|#{m}|#{n}|#{source}|#{LProcess.total_messages}|#{r*1000}")
		Process.reset_total_messages
	end
			def xtest_once
		n = 5
		m = 6
		source = 3
		run_engine(m, n, source)
	end
		def test_multiple
		5.step 50, 5 do |n|
			10.step 100, 10 do |m|
				source = n / 3
				run_engine(m, n, source)
			end
		end
	end
end
Test::Unit::UI::Console::TestRunner.run(ByzGeneralTest)

Finally here is the Erlang source code (Again I am showing multiple modules here). I tried to break the structure same as my Java and Ruby version and the application consisted of process, strategy, repository, engine, node, and config modules. The benchmarks were kicked off from the byz_general_test, which invoked engine and engine created processes for repository, generals and lieutenants. Another distinction is difference between active objects and regular functions. In this design, repository and processes are active objects that can receive messages via Erlang’s message communication primitives. Also, I added message counter just to keep track of number of messages for the simulation (though it is not requirement for the algorithm). I used ets APIs in repository to store paths of messages.

-module(config).
-compile(export_all).


-record(config, {source, num_procs, num_rounds}).

new(S, N, M) ->
  #config{source = S, num_procs = N, num_rounds = M}.

get_source(Self) ->
  Self#config.source.
get_num_procs(Self) ->
  Self#config.num_procs.
get_num_rounds(Self) ->
  Self#config.num_rounds
-module(counter).
-export([start/0, get_value/0, increment/0, reset/0, die/0, test_counter/0]).
-include("byz_general_test.hrl").

start() ->
  register(message_counter, spawn(fun() -> loop(0) end)).


get_value() ->
  lib_util:rpc(message_counter, value).


increment() ->
  message_counter ! {self(), increment}.

reset() ->
  message_counter ! {self(), reset}.


die() ->
  message_counter ! {self(), die, "Exiting"}.



loop(N) ->
  receive
    {_From, increment} ->
      loop(N + 1);
    {_From, reset} ->
      loop(0);
    {From, value} ->
      From ! {message_counter, N},
      loop(N);
    {_From, die, Reason} ->
      unregister(message_counter),
      exit(Reason);
    Any ->
      io:format("Unexpected message ~p~n", [Any])
  end.



test_counter() ->
  start(),
  increment(),
  increment(),
  2 = get_value(),
  reset(),
  0 = get_value(),
  die()
-module(engine).
-export([start/3, init/0, run/0, reset/0, test/0]).

init() ->
  counter:start(),
  repository:start().

reset() ->
  counter:reset(),
  repository:reset().

start(Source, N, M) ->
  Config = config:new(Source, N, M),
  put(config, Config),
  ProcIds = lists:seq(0, config:get_num_procs(Config) - 1),
  Pids = lists:map(fun(I) -> process:start(I, Config) end, ProcIds),
  put(pids, Pids),
  lists:foreach(fun(Pid) -> process:init(Pid, Pids) end, Pids),
  repository:generate_children(Config),
  Config.

run() ->
  Config = get(config),
  Ids = lists:seq(0, config:get_num_procs(Config) - 1),
  lists:foreach(fun(Id) -> send_message(Id) end, Ids),
  lists:foreach(fun(Id) -> print_result(Id) end, Ids).

get_pid(Id) ->
  Pids = get(pids),
  lists:nth(Id + 1, Pids).

send_message(Id) ->
  Config = get(config),
  RoundIds = lists:seq(0, config:get_num_rounds(Config) - 1),
  lists:foreach(fun(Round) -> send_message(Id, Round) end, RoundIds).

send_message(Id, Round) ->
  Pid = get_pid(Id),
  process:send_messages(Pid, Round, Id).

print_result(Id) ->
  Config = get(config),
  Source = config:get_source(Config),
  case Source of
    Id ->
      io:format("Source ");
    _ ->
      true
  end,
  io:format("Process ~p ", [Id]),

  Pid = get_pid(Id),
  Faulty = process:is_faulty(Pid),
  if
    Faulty ->
      io:format(" is faulty~n");
    true ->
      Decision = process:decide(Pid),
      io:format(" decides on value ~p~n", [Decision])
  end.

test() ->
  init(),
  Config = start(3, 5, 6),
  run(),
  Config.
-module(lib_util).
-compile(export_all).

rpc(Pid, Request) ->
  Pid ! {self(), Request},
  receive
    {Pid, Response} ->
      Response
  end.
-module(node).
-include("byz_general_test.hrl").
-compile(export_all).

-record(node, {input, output}).

new() ->
  #node{input = ?FAULTY, output = ?FAULTY}.
new(I, O) ->
  #node{input = I, output = O}.


set_input(Self, I) ->
  Self#node{input = I}.
get_input(Self) ->
  Self#node.input.

set_output(Self, O) ->
  Self#node{output = O}.
get_output(Self) ->
  Self#node.output.
set_output_as_input(Self) ->
  O = get_output(Self),
  Self#node{output = O}.
-module(process).
-export([init/2, start/2, receive_message/3, send_messages/3, decide/1, find_majority/2, is_faulty/1, is_source/1, test_process/0]).
-include("byz_general_test.hrl").


%
%%% starts process loop
%
start(Id, Config) ->
  spawn(fun() -> loop(Id, Config) end).

receive_message(Pid, Path, Node) ->
  %lib_util:rpc(Pid, {receive_message, Path, Node}).
  Pid ! {self(), {receive_message, Path, Node}}.

send_messages(Pid, Round, Id) ->
  %lib_util:rpc(Pid, {send_messages, Round, Id}).
  Pid ! {self(), {send_messages, Round, Id}}.

init(Pid, Pids) ->
  Pid ! {self(), init, Pids}.

decide(Pid) ->
  lib_util:rpc(Pid, decide).

find_majority(Pid, Path) ->
  lib_util:rpc(Pid, {find_majority, Path}).

is_faulty(Pid) ->
  lib_util:rpc(Pid, is_faulty).

is_source(Pid) ->
  lib_util:rpc(Pid, is_source).

put(config, Config),
put(allPids, AllPids),
SourcePid = lists:nth(config:get_source(Config)+ 1, AllPids),
put(lieutenants, AllPids -- [SourcePid]),
Nodes = dict:new(),
put(nodes, Nodes),
Source = config:get_source(Config),
SourceValue = strategy:source_value(),
if
Source =:= Id ->
Nodes1 = dict:store("", SourceValue, Nodes),
put(nodes, Nodes1);
true ->
true
end .


%
%%% stores message receievd in nodes dictionary
%%% we are also keeping track of total number of messages received in simulation.
%
receive_message(Path, Node) ->
  Nodes = get(nodes),
  Nodes1 = dict:store(Path, Node, Nodes),
  put(nodes, Nodes1),
  counter:increment().

get_node(Path) ->
  Nodes = get(nodes),
  Response = dict:find(Path, Nodes),
  case Response of
    {ok, Node} ->
      Node;
    _ ->
      %io:format("Failed to find node for path ~p~n", [Path]),
      node:new()
  end.

%
%%%
%
psend_messages(Round, Id) ->
  L = repository:get_rank_list(Round, Id),
  lists:foreach(
    fun(Path) ->
      psend_messages(Round, Id, Path) end, L).

psend_messages(Round, Id, Path) ->
  Length = string:len(Path),
  SourcePath = if
                 Length > 1 ->
                   string:substr(Path, 1, Length - 1);
                 true ->
                   ""
               end,
  Source = get_node(SourcePath),
  broadcast(Round, Id, Source, Path).


%
%%% broadcast message to all processes
%
broadcast(Round, Id, SourceNode, Path) ->
  Config = get(config),
  ProcIds = lists:seq(0, config:get_num_procs(Config) - 1),
  IdsToProcess = ProcIds -- [config:get_source(Config)],
  lists:foreach(
    fun(Dest) ->
      broadcast(Round, Id, SourceNode, Path, Dest) end, IdsToProcess).

broadcast(_Round, Id, SourceNode, Path, Dest) ->
  Config = get(config),
  Value = strategy:create_value(Config, node:get_input(SourceNode), Id, Dest, Path),
  ProcPids = get(allPids),
  ProcPid = lists:nth(Dest + 1, ProcPids),
  receive_message(ProcPid, Path, node:new(Value, ?UNKNOWN)).


decide() ->
  %%% Step 1 - set the leaf values
  Config = get(config),
  ProcIds = lists:seq(0, config:get_num_procs(Config) - 1),
  lists:foreach(fun(X) -> reset_node(X) end, ProcIds),
  %%% Step 2 - work up the tree
  RoundIds = lists:reverse(lists:seq(0, config:get_num_rounds(Config) - 1)),
  lists:foreach(
    fun(Round) ->
      set_node_value(Round) end, RoundIds),
  Source = config:get_source(Config),
  Result = repository:get_rank_list(0, Source),
  case Result of
    [] ->
      ?UNKNOWN;
    [TopPath] ->
      node:get_output(get_node(TopPath));
    [TopPath | _] ->
      node:get_output(get_node(TopPath))
  end.


set_node_value(Round) ->
  Config = get(config),
  ProcIds = lists:seq(0, config:get_num_procs(Config) - 1),
  lists:foreach(
    fun(Id) ->
      set_node_value(Round, Id) end, ProcIds).

set_node_value(Round, Id) ->
  L = repository:get_rank_list(Round, Id),
  lists:foreach(
    fun(Path) ->
      set_node_value(Round, Id, Path) end, L).

set_node_value(_Round, _Id, Path) ->
  Nodes = get(nodes),
  Node = get_node(Path),
  Value = find_majority(Path),
  Nodes1 = dict:store(Path, node:set_output(Node, Value), Nodes),
  put(nodes, Nodes1).

reset_node(I) ->
  Config = get(config),
  Nodes = get(nodes),
  L = repository:get_rank_list(config:get_num_rounds(Config), I),
  lists:foreach(fun(Path) ->
    Node = get_node(Path),
    Nodes1 = dict:store(Path, node:set_output_as_input(Node), Nodes),
    put(nodes, Nodes1)
                end, L).


increment_count(Child) ->
  Counts = get(counts),
  Node = get_node(Child),
  Count = dict:fetch(node:get_output(Node), Counts) + 1,
  Counts1 = dict:store(node:get_output(Node), Count, Counts),
  put(counts, Counts1).

find_majority(Path) ->
  Counts = dict:new(),
  Counts1 = dict:store(?ONE, 0, Counts),
  Counts2 = dict:store(?ZERO, 0, Counts1),
  Counts3 = dict:store(?UNKNOWN, 0, Counts2),
  put(counts, Counts3),
  L = repository:get_children_path(Path),
  N = length(L),
  lists:foreach(fun(Child) ->
    increment_count(Child) end, L),
  Counts4 = get(counts),
  OneCount = dict:fetch(?ONE, Counts4),
  ZeroCount = dict:fetch(?ZERO, Counts4),

  if
    OneCount > (N / 2) ->
      ?ONE;
    ZeroCount > (N / 2) ->
      ?ZERO;
    OneCount == ZeroCount andalso OneCount == (N / 2) ->
      strategy:get_default();
    true ->
      ?UNKNOWN
  end.


loop(Id, Config) ->
  receive
    {_From, init, AllPids} ->
      init(Id, Config, AllPids),
      loop(Id, Config);
    {_From, {receive_message, Path, Node}} ->
      receive_message(Path, Node),
      %From ! {self(), done},
      loop(Id, Config);
    {_From, {send_messages, Round, Id}} ->
      psend_messages(Round, Id),
      %From ! {self(), done},
      loop(Id, Config);
    {From, decide} ->
      From ! {self(), decide()},
      loop(Id, Config);
    {From, is_faulty} ->
      From ! {self(), strategy:is_faulty(Config, Id)},
      loop(Id, Config);
    {From, is_source} ->
      From ! {self(), config:get_source(Config) == Id},
      loop(Id, Config);
    {From, {find_majority, Path}} ->
      From ! {self(), find_majority(Path)},
      loop(Id, Config);
    Any ->
      io:format("Unexpected ~p~n", [Any]),
      loop(Id, Config)
  end.


test_process() ->
  counter:start(),
  repository:start(),
  Config = config:new(3, 5, 6),
  Pid = start(0, Config),
  init(Pid, [Pid, 1, 2, 3, 4, 5, 6]),
  Path = "mypath",
  Node = node:new(),
  receive_message(Pid, Path, Node),
  send_messages(Pid, 0, 0),
  ?UNKNOWN = decide(Pid),
  ?ONE = find_majority(Pid, Path),
  false = is_faulty(Pid),
  false = is_source(Pid).
-module(repository).
-export([start/0, reset/0, get_rank_list/2, get_children_path/1, generate_children/1, die/0, test_generate/0, test_path_ranks/0, test_children/0]).
-include("byz_general_test.hrl").


start() ->
  register(repository, spawn(fun() -> init_loop() end)).


init_loop() ->
  Children = ets:new(children, [set]),
  PathsByRank = ets:new(path_ranks, [set]),
  loop(Children, PathsByRank).

get_children_path(Path) ->
  lib_util:rpc(repository, {get_children_path, Path}).

get_rank_list(Rank, Source) ->
  lib_util:rpc(repository, {get_rank_list, Rank, Source}).

generate_children(Config) ->
  repository ! {self(), generate_children, Config}.

reset() ->
  repository ! {self(), reset}.

die() ->
  repository ! {self(), die, "Exiting"}.


table_lookup(Tab, Key) ->
  Result = ets:lookup(Tab, Key),
  case Result of
    [] ->
      [];
    error ->
      [];
    {ok, Value} ->
      lists:reverse(Value);
    [{Key, Value}] ->
      lists:reverse(Value)
  end.

table_insert(Tab, Key, Value) ->
  NewValue = case table_lookup(Tab, Key) of
               [] ->
                 [Value];
               L ->
                 [Value | L]
             end,
  ets:insert(Tab, {Key, NewValue}).



set_children_path(Children, PathKey, PathValue) ->
  table_insert(Children, PathKey, PathValue).

get_children_path(Children, Path) ->
  table_lookup(Children, Path).

get_rank_list(PathsByRank, Rank, Source) ->
  table_lookup(PathsByRank, {Rank, Source}).


set_rank_list(PathsByRank, Rank, Source, Path) ->
  Key = {Rank, Source},
  table_insert(PathsByRank, Key, Path).


generate_children(Config, Children, PathsByRank) ->
  generate_children(
    Config, Children, PathsByRank,
    config:get_source(Config),
    [],
    "",
    0).

generate_children(Config, Children, PathsByRank, Source, Ids, Path, Rank) ->
  Ids1 = [Source | Ids],
  Path1 = Path ++ integer_to_list(Source),
  set_rank_list(PathsByRank, Rank, Source, Path1),
  %%%
  Rounds = config:get_num_rounds(Config),
  if
    Rank < Rounds ->
      IdsToProcess = lists:seq(0, config:get_num_procs(Config) - 1) -- Ids1,
      lists:foreach(
        fun(Source1) -> generate_children(Config, Children, PathsByRank, Source1, Ids1, Path1, Rank + 1),
          set_children_path(Children, Path1, Path1 ++ integer_to_list(Source1))
        end, IdsToProcess);
    true ->
      true
  end,
  Children.


loop(Children, PathsByRank) ->
  receive
    {From, {get_rank_list, Rank, Source}} ->
      From ! {repository, get_rank_list(PathsByRank, Rank, Source)},
      loop(Children, PathsByRank);
    {From, {get_children_path, Path}} ->
      From ! {repository, get_children_path(Children, Path)},
      loop(Children, PathsByRank);
    {_From, reset} ->
      ets:delete_all_objects(Children),
      ets:delete_all_objects(PathsByRank),
      loop(Children, PathsByRank);
    {_From, generate_children, Config} ->
      generate_children(Config, Children, PathsByRank),
      loop(Children, PathsByRank);
    {_From, die, Reason} ->
      ets:delete(Children),
      ets:delete(PathsByRank),
      exit(Reason);
    Any ->
      io:format("Unexpected message~p~n", [Any])
  end.




benchmark_byz_general() ->
  engine:init(),
  benchmark_byz_general(5).

benchmark_byz_general(N) when N < 100 ->
  benchmark_byz_general(N, 10),
  benchmark_byz_general(N + 10);
benchmark_byz_general(N) when N >= 100 ->
  true.

benchmark_byz_general(N, M) when M < 100 ->
  statistics(runtime),
  statistics(wall_clock),
  Source = round(N / 3),
  io:format("Starting|~p|~p|~p~n", [M, N, Source]),
  engine:start(Source, N, M),
  engine:run(),
  {_, RT} = statistics(runtime),
  {_, WC} = statistics(wall_clock),
  io:format("Finished|~p|~p|~p|~p|~p|~p~n", [M, N, Source, counter:get_value(), RT, WC]),
  engine:reset(),
  benchmark_byz_general(N, M + 10);
benchmark_byz_general(_N, M) when M >= 100 ->
  true.

I merged the results with following script:

class Stats
     attr_accessor :processes
     attr_accessor :rounds
     attr_accessor :messages
     attr_accessor :java_time
     attr_accessor :erlang_time
     attr_accessor :cpp_time
     attr_accessor :ruby_time
     def initialize(procs, rounds, msgs)
      @processes = procs.to_i
      @rounds = rounds.to_i
      @messages = msgs.to_i
    end
    def key
      "#{@processes}/#{@rounds}"
    end
    def to_s
      "#{@processes},#{rounds},#{@messages},#{@cpp_time},#{@ruby_time},#{@java_time},#{@erlang_time}"
    end
  end
 
  stats = {}
 
  files = ["cpp.out", "ruby.out", "java.out", "erlang.out"]
  count_setter = ["cpp_time=", "ruby_time=", "java_time=", "erlang_time="]
  for i in 0...files.length
      File.open(files[i], "r").readlines.each do |line|
          if line =~ /Finish/
              t = line.split("|")
              stat = Stats.new(t[2], t[1], t[4])
              time = t[5].to_i
              stat.send(count_setter[i], time)
              stats[stat.key] = stat
           end
       end
  end
 
 
  puts "Processes,Rounds,Messages,CPP Time,Ruby Time,Java Time,Erlang Time"
  stats.values.sort_by {|stat| stat.processes * stat.rounds}.each do |stat|
    puts stat
  end
 

And here are the results of benchmark that I ran on my Dell notebook (Note I used time function in C++ which only returns timing in seconds, so C++ timings are actually not precise.):

Conclusion:

This was interesting problem that tested limits of these languages. For example, I found when using more than 10 processes things got really nasty. The Java program gave up with OutOfMemory. The Erlang program dumped crashed, though I would have used OTP’s supervisors if I was writing more fault tolerant application. Ruby program became too slow, so I had to kill it. Java turned out to be the performance leader in this case and I was a bit surprised when Erlang’s response time became really high with 9 processes. As, I mentioned earlier, the C++, Java and Ruby versions are not really concurrent and their message passing is really method invocation. As far as mapping algorithm to the language, I found that Erlang fit very nicely for distributed algorithms that involve a lot of communications. I left the C++, Java and Ruby version very simple and didn’t try to implement truly independent processes and communication because that would have required a lot more effort.

Resources:

Source Code

Powered by WordPress