Ninety-Nine Prolog Problems

99.pl

% 01 - Find the last element of a list.
my_last(X,[X]).
my_last(X,[_|Xs]) :- my_last(X, Xs).

% 02 - Find the last but one element of a list.
my_but_last(X,[X,_]).
my_but_last(X,[_|Xs]) :- my_but_last(X,Xs).

% 03 - Find the K'th element of a list.
element_at(X,[X|_],1).
element_at(X,[_|Xs],K) :- K1 is K - 1, element_at(X,Xs,K1).

% 04 - Find the number of elements of a list.
my_length([],0).
my_length([_|Xs],K) :- my_length(Xs,K1), K is K1 + 1.

% 05 - Reverse a list.
my_reverse(Xs,Ys) :- my_reverse_(Xs,Ys,[]).
my_reverse_([],Xs,Xs).
my_reverse_([X|Xs],Ys,Zs) :- my_reverse_(Xs,Ys,[X|Zs]).

% 06 - Find out whether a list is a palindrome.
palindrome(Xs) :- my_reverse(Xs,Xs).

% 07 - Flatten a nested list structure.
my_flatten(X,[X]) :- not(is_list(X)).
my_flatten([],[]).
my_flatten([X|Xs],Zs) :- my_flatten(X,Y), my_flatten(Xs,Ys), append(Y,Ys,Zs).

% 08 - Eliminate consecutive duplicates of list elements.
compress([],[]).
compress([X],[X]).
compress([X,X|Xs],Ys) :- compress([X|Xs],Ys).
compress([X,Y|Ys],[X|Zs]) :- X \= Y, compress([Y|Ys],Zs).

% 09 - Pack consecutive duplicates of list elements into sublists.
pack([],[]).
pack([X|Xs],[Z|Zs]) :- pack_(X,Xs,Ys,Z), pack(Ys,Zs).
pack_(X,[],[],[X]).
pack_(X,[Y|Ys],[Y|Ys],[X]) :- X \= Y.
pack_(X,[X|Xs],Ys,[X|Zs]) :- pack_(X,Xs,Ys,Zs).

% 10 - Run-length encoding of a list.
encode(Xs,Zs) :- pack(Xs,Ys), maplist(encode_,Ys,Zs).
encode_([X|Xs],[K,X]) :- my_length([X|Xs],K).

% 11 - Modified run-length encoding.
encode_modified(Xs,Zs) :- pack(Xs,Ys), maplist(encode_modified_,Ys,Zs).
encode_modified_([X],X).
encode_modified_([X|Xs],[K,X]) :- my_length([X|Xs],K), K > 1.

% 12 - Decode a run-length encoded list.
decode([],[]).
decode([X|Xs],[X|Ys]) :- not(is_list(X)), decode(Xs,Ys).
decode([[1,X]|Xs],[X|Ys]) :- decode(Xs,Ys).
decode([[K,X]|Xs],[X|Ys]) :- K > 1, K1 is K - 1, decode([[K1,X]|Xs],Ys).

% 13 - Run-length encoding of a list (direct solution).
encode_direct([],[]).
encode_direct([X|Xs],[Z|Zs]) :- encode_direct_(X,Xs,Ys,1,Z), encode_direct(Ys,Zs).
encode_direct_(X,[],[],1,X).
encode_direct_(X,[],[],K,[K,X]) :- K > 1.
encode_direct_(X,[Y|Ys],[Y|Ys],1,X) :- X \= Y.
encode_direct_(X,[Y|Ys],[Y|Ys],K,[K,X]) :- X \= Y, K > 1.
encode_direct_(X,[X|Xs],Ys,K,T) :- K1 is K + 1, encode_direct_(X,Xs,Ys,K1,T).

% 14 - Duplicate the elements of a list.
dupli([],[]).
dupli([X|Xs],[X,X|Ys]) :- dupli(Xs,Ys).

% 15 - Duplicate the elements of a list a given number of times.
dupli(Xs,K,Ys) :- dupli(Xs,K,Ys,K).
dupli([],_,[],_).
dupli([_|Xs],N,Ys,0) :- dupli(Xs,N,Ys,N).
dupli([X|Xs],N,[X|Ys],K) :- K > 0, K1 is K - 1, dupli([X|Xs],N,Ys,K1).

% 16 - Drop every N'th element from a list.
drop(Xs,K,Ys) :- drop(Xs,K,Ys,K).
drop([],_,[],_).
drop([_|Xs],N,Ys,1) :- drop(Xs,N,Ys,N).
drop([X|Xs],N,[X|Ys],K) :- K > 1, K1 is K - 1, drop(Xs,N,Ys,K1).

% 17 - Split a list into two parts; the length of the first part is given.
split(Xs,0,[],Xs).
split([X|Xs],K,[X|Ys],Zs) :- K > 0, K1 is K - 1, split(Xs,K1,Ys,Zs).

% 18 - Extract a slice from a list.
slice([X|_],1,1,[X]).
slice([X|Xs],1,K,[X|Ys]) :- K > 1, K1 is K - 1, slice(Xs,1,K1,Ys).
slice([_|Xs],I,K,Ys) :- I > 1, I1 is I - 1, K1 is K - 1, slice(Xs,I1,K1,Ys).

% 19 - Rotate a list N places to the left.
rotate(Xs,0,Xs).
rotate(Xs,K,Zs) :- K > 0, split(Xs,K,Ys1,Ys2), append(Ys2,Ys1,Zs).
rotate(Xs,K,Zs) :- K < 0, length(Xs,K1), K2 is K1 + K, rotate(Xs,K2,Zs).

% 20 - Remove the K'th element from a list.
remove_at(X,[X|Xs],1,Xs).
remove_at(X,[Y|Ys],K,[Y|Zs]) :- K > 1, K1 is K - 1, remove_at(X,Ys,K1,Zs).

% 21 - Insert an element at a given position into a list.
insert_at(X,Xs,1,[X|Xs]).
insert_at(X,[Y|Ys],K,[Y|Zs]) :- K > 1, K1 is K - 1, insert_at(X,Ys,K1,Zs).

% 22 - Create a list containing all integers within a given range.
range(X,X,[X]).
range(X,K,[X|Xs]) :- X < K, X1 is X + 1, range(X1,K,Xs).
range(X,K,[X|Xs]) :- X > K, X1 is X - 1, range(X1,K,Xs).

% 23 - Extract a given number of randomly selected elements from a list.
rnd_select(_,0,[]).
rnd_select(Xs,K,[X|Zs]) :- K > 0, K1 is K - 1, my_length(Xs,L), I is random(L) + 1, remove_at(X,Xs,I,Ys), rnd_select(Ys,K1,Zs).

% 24 - Lotto: Draw N different random numbers from the set 1..M.
lotto(K,N,Ys) :- range(1,N,Xs), rnd_select(Xs,K,Ys).

% 25 - Generate a random permutation of the elements of a list.
rnd_permu(Xs,Ys) :- my_length(Xs,L), rnd_select(Xs,L,Ys).

% 26 - Generate the combinations of K distinct objects chosen from the N elements of a list.
combination(0,_,[]).
combination(K,Xs,[Z|Zs]) :- K > 0, K1 is K - 1, combination_(Xs,Ys,Z), combination(K1,Ys,Zs).
combination_([X|Xs],Xs,X).
combination_([_|Xs],Ys,Y) :- combination_(Xs,Ys,Y).