99 Lisp Prolog Erlang problems
Since I have been lapsing in my Erlang practice, I am playing with L-99: Ninety-Nine Lisp Problems, based on a Prolog problem list – which is fitting, since the first Erlang interpreter was written in Prolog…
I’ll post links to my solutions when I have enough – I have done P01 to P20, with the exception of P13. Feels good to get back in the groove…
Update
I posted some sample code in the comments, but here is a permanent link to the source code.
January 17th, 2007 at 6:45 pm
A good source of exercises, indeed! I will try in Erlang and Prolog too.
Maybe you can post a solution from time to time, so we can compare? There are many solutions sometimes, the simpler ones not being tail-recursive or too greedy in memory.
January 17th, 2007 at 7:23 pm
P01
mylast(A) -> mylast(A,[]).
mylast([],B) -> B;
mylast([H|T],A) ->
mylast(T,H).
P02
mybutlast(A) -> mybutlast(A, [], []).
mybutlast([], A, B) -> A;
mybutlast([H|T], A, B) ->
mybutlast(T, B, H).
P03
kthelem(A, N) -> kthelem(A, 1, N).
kthelem([], _, _) -> {error, out_of_range};
kthelem([H|T], Current, Current) -> H;
kthelem([H|T], Current, N) ->
kthelem(T, Current+1, N).
P04
len(A) -> len(A, 0).
len([], Len) -> Len;
len([H|T], Len) -> len(T, Len+1).
P05
reverse([]) -> [];
reverse([H|T]) -> reverse(T,[H]).
reverse([], L) -> L;
reverse([H|T], L) ->
reverse(T, [H|L]).
P06
palindrome(A) ->
B=reverse(A),
case A of
B -> true;
_ -> false
end.
P07
I had difficulties with this one, and ended up getting a hint or three from lists:flatten/1’s source code
flatten(List) when is_list(List) ->
do_flatten(List, []).
flatten(List, Tail) when is_list(List), is_list(Tail) ->
do_flatten(List, Tail).
do_flatten([H|T], Tail) when is_list(H) ->
do_flatten(H, do_flatten(T, Tail));
do_flatten([H|T], Tail) ->
[H|do_flatten(T, Tail)];
do_flatten([], Tail) ->
Tail.
P08
compress(A) -> compress(A, [], []).
compress([], L, _) -> flatten(L);
compress([H|T], L, H) -> compress(T, L, H);
compress([H|T], L, X) -> compress(T, [L,H], H).
P09
pack(A) -> pack(A,[],[],[]).
pack([], X, Liste, Acc) -> reverse([flatten([Acc,X])|Liste]);
pack([H|T], H, Liste,Acc) ->
pack(T, H, Liste, [H,Acc]);
pack([H|T], [], Liste, Acc) ->
pack(T, H, Liste, [H]);
pack([H|T], X, Liste, []) ->
pack(T, H, [[X]|Liste], []);
pack([H|T], X, Liste, Acc) ->
pack(T, H, [flatten([Acc,X])|Liste], []).
P10
runlen(A) -> runlen(A,[],[],[]).
runlen([], X, Liste, Acc) ->
runlengths([flatten([Acc,X])|Liste],[]);
runlen([H|T], H, Liste,Acc) ->
runlen(T, H, Liste, [H,Acc]);
runlen([H|T], [], Liste, Acc) ->
runlen(T, H, Liste, [H]);
runlen([H|T], X, Liste, []) ->
runlen(T, H, [[X]|Liste], []);
runlen([H|T], X, Liste, Acc) ->
runlen(T, H, [flatten([Acc,X])|Liste], []).
%% Compute sums
runlengths([],Acc) -> Acc;
runlengths([H|T],Acc) ->
[Elem|_]=H,
runlengths(T,[[len(H), Elem]|Acc]).
P11
runlen2(A) -> runlen2(A,[],[],[]).
runlen2([], X, Liste, Acc) ->
io:format(”list looks like: ~p~n”,[lists:reverse([flatten([Acc,X])|Liste])]),
runlengths2([flatten([Acc,X])|Liste],[]);
runlen2([H|T], H, Liste,Acc) ->
runlen2(T, H, Liste, [H,Acc]);
runlen2([H|T], [], Liste, Acc) ->
runlen2(T, H, Liste, [H]);
runlen2([H|T], X, Liste, []) ->
runlen2(T, H, [[X]|Liste], []);
runlen2([H|T], X, Liste, Acc) ->
runlen2(T, H, [flatten([Acc,X])|Liste], []).
%% Compute sums
runlengths2([],Acc) -> Acc;
runlengths2([H|T],Acc) ->
[Elem|_]=H,
Len=len(H),
case Len of
1 -> runlengths2(T,[[Elem]|Acc]);
_ -> runlengths2(T,[[len(H), Elem]|Acc])
end.
P12
decoderunlength(A) -> decoderunlength(A, []).
decoderunlength([], Acc) -> reverse(Acc);
decoderunlength([H|T], Acc) ->
Len=len(H),
case Len of
1 -> decoderunlength(T, [H|Acc]);
_ -> decoderunlength(T, [deflate(H)|Acc])
end.
deflate([Len, Elem]) -> deflate(Elem, 1, Len, [Elem]).
deflate(Elem, Current, Current, Liste) -> Liste;
deflate(Elem, Current, Len, Liste) ->
deflate(Elem, Current+1, Len, [Elem|Liste]).
P14
dupli(A) -> dupli(A, []).
dupli([], Acc) -> reverse(Acc);
dupli([H|T], Acc) ->
dupli(T, [H,H|Acc]).
P15
repli(A, Times) -> repli(A, Times, []).
repli([], Times, Acc) -> reverse(flatten(Acc));
repli([H|T], Times, Acc) ->
repli(T, Times, [deflate([Times, H])|Acc]).
P16
%% I had first misunderstood the problem and wrote a routine
%% that drops the nth element only
drop(A, N) -> drop(A, 1, N, []).
drop([], _, _, Acc) -> reverse(Acc);
drop([H|T], Current, Current, Acc) -> flatten(reverse([T|Acc]));
drop([H|T], Current, N, Acc) ->
drop(T, Current+1, N, [H|Acc]).
%% And now the correct solution
dropnth(A, N) -> dropnth(A, 1, N, []).
dropnth([], _, _, Acc) -> reverse(Acc);
dropnth([H|T], Current, Current, Acc) ->
dropnth(T, 1, Current, Acc);
dropnth([H|T], Current, N, Acc) ->
dropnth(T, Current+1, N, [H|Acc]).
P17
split(A, Len) -> split(A, 1, Len, []).
split([], _, _, Acc) -> reverse(Acc);
split([H|T], Current, Current, Acc) -> [reverse([H|Acc])|[T]];
split([H|T], Current, Len, Acc) ->
split(T, Current+1, Len, [H|Acc]).
P18
slice(A, Start, End) when Start > End ->
{error, start_point_greater_than_endpoint};
slice(A, 0, End) ->
{error, start_point_is_null};
slice(A, Start, End) -> slice(A, 1, Start, End, []).
slice([], End, Start, End, Acc) -> reverse(Acc);
slice([H|T], End, Start, End, Acc) -> reverse([H|Acc]);
slice([H|T], Start, Start, End, Acc) ->
slice(T, Start+1, Start, End, [H|Acc]);
slice([H|T], Current, Start, End, _) when Current
slice(T, Current+1, Start, End, []);
slice([H|T], Current, Start, End, Acc) ->
slice(T, Current+1, Start, End, [H|Acc]).
P19
lrot(A, N) -> lrot(A, 1, N, []).
lrot([], _, _, Acc) -> {error};
lrot([H|T], Current, Current, Acc) ->
flatten([T|reverse([H|Acc])]);
lrot([H|T], Current, N, Acc) ->
lrot(T, Current+1, N, [H|Acc]).
January 17th, 2007 at 9:26 pm
P20 solved in P16
P21
insertAt(Elem, Liste, Position) -> insertAt(Liste, 1, Position, Elem, []).
insertAt([], _, _, Elem, Acc) -> reverse(Acc);
insertAt([H|T], Current, Current, Elem, Acc) -> flatten(reverse([T, H, Elem|Acc]));
insertAt([H|T], Current, N, Elem, Acc) ->
insertAt(T, Current+1, N, Elem, [H|Acc]).
P22
range(Start, End) ->
if
Start == End -> [Start];
Start > End -> {error, “Start > End”};
Start range(Start, End, [])
end.
range(End, End, Acc) -> reverse([End|Acc]);
range(Start, End, Acc) ->
range(Start+1, End, [Start|Acc]).
P23
rndSelect(Liste, Len) -> rndSelect(Liste, Len, []).
rndSelect([], _, Acc) -> reverse(Acc);
rndSelect(Liste, 0, Acc) -> reverse(Acc);
rndSelect(Liste, N, Acc) ->
L=len(Liste),
Rnd=random:uniform(L),
[NewListe, Number]=extract(Liste, 1, Rnd, []),
rndSelect(NewListe, N-1, [Number|Acc]).
extract([H|T], Current, Current, Acc) -> [flatten(reverse([T|Acc])), H];
extract([H|T], Current, N, Acc) ->
extract(T, Current+1, N, [H|Acc]).
P24
lottoSelect(N, Max) ->
rndSelect(range(1,Max),N).
P25
rndPermu(Liste) -> rndSelect(Liste, len(Liste)).
January 18th, 2007 at 1:08 pm
I haven’t finished yet, but here are my comments and code.
P01
The problem with your solution is that it returns the empty list when the input is the empty list, but also when the last element of a non-empty list is the empty list… In the first case, there should be an error, i.e. either a user-defined exception or a VM-level exception. If I understand the philosophy of Erlang, I would write
P02
The English is broken in the question and the example is different from the Prolog version. In LISP, it seems the output is the list of the two last elements, whereas in Prolog it is indeed the last element which is the “result”. I assume the latter interpretation, as you did. You have the same problem as with P01. So I would rather write
P03
Since the only possible error here is for index to be out of range, I would not bother to return an error, so the logic of the application is not obscured by the logic of errors (since there is only one possible here). It is unusual for me, but it seems this is the Erlang way, don’t you agree? But there is a logical error you do not avoid here, which happens when the index is negative. Also, if you decrement the index you don’t need another index. So I wrote:
[I will submit this comment now to check whether the HTML is fine, and if so, resume.]
January 18th, 2007 at 2:28 pm
P06
Your solution is the simplest one but not the most efficient, I believe, since you construct the reversed list of the input. I have been thinking a little and came up with a different approach, that keeps the memory usage to a small constant plus the space of the input if the garbage collector is quick enough or if the input is big enough. The idea consists in splitting the input list. If there are an odd number of items, the middle item is discarded. The run-time do not rebuild individual items (just change some pointers) and the garbage collector will discover that the head of first half of the initial list is no more accessible during the splitting. If the list is big enough, it will trigger a collection. Then the two parts of the list are matched against each other, thus relying, as you do, on the run-time environment for that task. The first half of the input list is reversed by the splitting, so matching is immediate:
It would seem that the time complexity (counting a constant for each item traverses) is greater than in your solution, because I compute the length of the input list first and because we do not take into account the cost of the matching. But if we do, it is in fact the same because in your solution, the input list, of, say, N items, is reversed, which costs N, then the matching also costs N, thus total is 2N. In my code, the length computation costs N, then the half list is build at the cost of [N/2], then the matching costs [N/2], so total is 2N as well. What do you think?
P07
Why is there a flatten/2 in your code? I am learning Erlang, so I have a question: is the guard predicate is_list/1 or list/1? There is a source of inefficience with your solution:
This is not a tail-recursive call, i.e. it is not compiled as a loop, so the size of the BEAM stack will grow in proportion to the number of items in the input list from the item which is not a list, until the end. If all items in the input list are lists, no problem, the stack usage will remain reasonable, since the other clause contains a tail recursive call and one which is not. But it is unfortunate that the non tail-recursive call implies T instead of H… So I propose a little modification to solve these two sources of inefficience at once:
flatten(List) -> reverse(rev_flatten([],List)).
rev_flatten(Acc,[]) -> Acc;
rev_flatten(Acc,[Item|Items]) when list(Item) -> rev_flatten(rev_flatten(Acc,Item),Items);
rev_flatten(Acc,[Item|Items]) -> rev_flatten([Item|Acc],Items).
P08
Your solution is complex (three parameters) and inefficient because it relies on flatten/1, which is not constant stack space (despite my efforts). There is a direct and fully tail recursive solution:
This is something I like about Erlang and Prolog: non-linear patterns, i.e. patterns with repeated variables.
P09
Again, your solution is very complex (didn’t check it fully) and not efficient (relies on flatten/1. Here is a better one
Again, tail-recursivity and non-linear patterns are our best friends.
P10
Your code is incredibly complex, I did not even bother checking it, sorry, because I have a tiny and efficient solution for you:
You wonder what is this pack/3 function, thanks for asking:) The question requires to reuse pack, but I realized that pack/1 is reversing the accumulator and I need here the elements in the order of the accumulaor (which is the reversed order with respect to the input). So, instead of duplicating the code of pack/2 I instead rewrote pack/2 into a pack/3 as follows:
Notice the extra first parameter which is the function to apply to the accumulator when we are done. This makes pack/3 a higher-order function, which is a cool name:) All this to be able to parameterize what we do to the accumulator at the end. Here, in pack/1, we want to reverse it, hence
Now, in encode/2, we do not want to reverse it, thus
January 18th, 2007 at 2:32 pm
I said
but this is wrong. T may be shorter than H, in which case it was fortunate! The time complexity here does not depend on the number of the items which are not lists but on the whole structure as well (it is a tree, actually, because we deal with lists of lists, in general).
January 18th, 2007 at 2:33 pm
My last comment was about P07.
January 22nd, 2007 at 1:39 pm
I would like to learn some Ruby. What resource do you recommend?
January 23rd, 2007 at 4:40 pm
*The* Ruby book