Ninety-Nine Picat Problems
|
Find the last element of a list.
% myLast(L) = last(L).
myLast([X]) = X.
myLast([_|Xs]) = myLast(Xs).
Find the last but one element of a list.
myButLast([X,_]) = X.
myButLast([_|Xs]) = myButLast(Xs).
Find the K'th element of a list. The first
element in the list is number 1.
% elementAt(L,K) = L[K].
elementAt([X|_],1) = X.
elementAt([_|Xs],K) = Kth, K > 1 => Kth = elementAt(Xs,K-1).
Find the number of elements of a list.
% myLength(L) = len(L).
myLength(L) = myLength(L,0).
myLength([],Len) = Len.
myLength([_|Xs],Len) = myLength(Xs,Len+1).
Reverse a list.
% myReverse(L) = reverse(L).
myReverse(L) = myReverse(L,[]).
myReverse([],R) = R.
myReverse([X|Xs],R) = myReverse(Xs,[X|R]).
Find out whether a list is a palindrome. A palindrome can
be read forward or backward; e.g. (x a m a x).
isPalindrome(Xs) => Xs == reverse(Xs).
Flatten a nested list structure.
myFlatten([X|Xs]) = myFlatten(X) ++ myFlatten(Xs).
myFlatten([]) = [].
myFlatten(X) = [X].
Eliminate consecutive duplicates of list elements.
compress([X|Ys@[X|_]]) = compress(Ys).
compress([X|Ys]) = [X|compress(Ys)].
compress(Ys) = Ys.
Pack consecutive duplicates of list elements into sublists.
If a list contains repeated elements they should be placed
in separate sublists.
pack([]) = [].
pack([X|Xs]) = Ls =>
Ls = [[X|L]|LsR],
pack(Xs,X,L,LsR).
pack([X|Xs],X,L,LsR) =>
L = [X|LR],
pack(Xs,X,LR,LsR).
pack(Xs,_X,L,LsR) =>
L = [],
LsR = pack(Xs).
Run-length encoding of a list. Use the result of problem P09
to implement the so-called run-length encoding data
compression method. Consecutive duplicates of elements are
encoded as lists (N E) where N is the number of duplicates
of the element E.
encode(Xs) = Ys =>
Xs1 = pack(Xs),
Ys = [(N,E) : [E|Es] in Xs1, N = len(Es)+1].
Modify the result of problem 10 in such a way that if an
element has no duplicates it is simply copied into the
result list. Only elements with duplicates are transferred
as (N E) lists.
encodeModified(Xs) = Ys =>
Xs1 = encode(Xs),
Ys = [cond(N==1,E,(N,E)) : (N,E) in Xs1].
Decode a run-length encoded list.
Given a run-length code list generated as specified in
problem 11. Construct its uncompressed version.
decodeModified([]) = [].
decodeModified([(N,E)|Xs]) = [E : _ in 1..N] ++ decodeModified(Xs).
decodeModified([X|Xs]) = [X|decodeModified(Xs)].
Run-length encoding of a list (direct solution).
Implement the so-called run-length encoding data compression
method directly. I.e. don't explicitly create the sublists
containing the duplicates, as in problem 9, but only count
them. As in problem P11, simplify the result list by
replacing the singleton lists (1 X) by X.
encodeDirect([]) = [].
encodeDirect([X|Xs]) = Ls =>
encodeDirect(Xs,X,1,Ls).
encodeDirect([X|Xs],X,Count,L) =>
encodeDirect(Xs,X,Count+1,L).
encodeDirect(Xs,X,Count,L) =>
(Count == 1 -> L = [X|L1]; L = [(Count,X)|L1]),
L1 = encodeDirect(Xs).
Duplicate the elements of a list.
dupli([]) = [].
dupli([X|Xs]) = [X,X|dupli(Xs)].
Replicate the elements of a list a given number of times.
repli(Xs,N) = Ys =>
repli(Xs,N,Ys).
repli([],_N,Ys) => Ys = [].
repli([X|Xs],N,Ys) =>
repli_aux(X,N,Ys,Ys1),
repli(Xs,N,Ys1).
repli_aux(_X,0,Ys,YsR) => Ys = YsR.
repli_aux(X,N,Ys,YsR) => Ys = [X|Ys1], repli_aux(X,N-1,Ys1,YsR).
Drop every N'th element from a list.
dropEvery(Xs,N) = Ys =>
dropEvery(Xs,N,Ys).
dropEvery([],_N,Ys) => Ys = [].
dropEvery(Xs,N,Ys) =>
dropEveryHelper(Xs,Xs1,N,Ys,Ys1),
dropEvery(Xs1,N,Ys1).
dropEveryHelper([],XsR,_N,Ys,YsR) => XsR = [], Ys = YsR.
dropEveryHelper([_|Xs],XsR,1,Ys,YsR) =>
XsR = Xs,
YsR = Ys.
dropEveryHelper([X|Xs],XsR,N,Ys,YsR) =>
Ys = [X|Ys1],
dropEveryHelper(Xs,XsR,N-1,Ys1,YsR).
Split a list into two parts; the length of the first part
is given.
my_split(Xs,N) = (Part1,Part2) =>
my_split(Xs,N,Part1,Part2).
my_split(Xs,0,Part1,Part2) => Part1 = [], Part2 = Xs.
my_split([X|Xs],N,Part1,Part2) =>
Part1 = [X|Part1R],
my_split(Xs,N-1,Part1R,Part2).
Extract a slice from a list.
Given two indices, i and k, the slice is the list
containing the elements between the i'th and k'th element
of the original list (both limits included). Start counting
the elements with 1.
import util.
my_slice(Xs,I,K) = drop(Xs,I-1).take(K-I+1).
Rotate a list N places to the left.
import util.
rotate(L,N) = Res, N >= 0 =>
Len = len(L),
M = N mod Len,
Res = L.drop(M) ++ L.take(M).
rotate(L,N) = Res =>
AbsN = -N,
Len = len(L),
M = AbsN mod Len,
Res = L.drop(Len-M) ++ L.take(Len-M).
Remove the K'th element from a list.
removeAt([],_K) = [].
removeAt(Xs,0) = Xs.
removeAt([_X|Xs],1) = Xs.
removeAt([X|Xs],K) = [X|removeAt(Xs,K-1)].
Insert an element at a given position into a list.
insertAt(X,Ys,1) = [X|Ys].
insertAt(X,[Y|Ys],N) = [Y|insertAt(X,Ys,N-1)].
Create a list containing all integers within a given range.
range(X,Y) = X..Y.
Extract a given number of randomly selected elements from a
list.
rnd_select(_,N) = _, N<0 => throw("N must be greater than zero.").
rnd_select(L,N) = Res =>
Len = len(L),
Flags = new_array(Len),
gen_randoms(N,Len,Flags,Is),
Res = [L[I] : I in Is].
gen_randoms(0,_Len,_Flags,Is) => Is = [].
gen_randoms(N,Len,Flags,Is) =>
I = random() mod Len+1,
(var(Flags[I]) ->
Is = [I|Is1],
N1 = N-1
;
Is = Is1,
N1 = N
),
gen_randoms(N1,Len,Flags,Is1).
Draw N different random numbers from the set 1..M.
diff_select(N,M) = Is =>
Flags = new_array(M),
gen_randoms(N,M,Flags,Is).
Generate a random permutation of the elements of a list.
rnd_permu(Xs) = rnd_select(Xs, len(Xs)).
Generate the combinations of K distinct objects chosen from
the N elements of a list.
combinations(N,Xs) = combinations(N,Xs,len(Xs)).
combinations(0,_Xs,_Size) = [[]].
combinations(N,Xs,N) = [Xs].
combinations(N,[X|Xs],Size) = [[X|Comb] : Comb in combinations(N-1,Xs,Size-1)]
++
combinations(N,Xs,Size-1).
Group the elements of a set into disjoint subsets.
a) In how many ways can a group of 9 people work in 3
disjoint subgroups of 2, 3 and 4 persons? Write a function
that generates all the possibilities and returns them in a
list.
b) Generalize the above predicate in a way that we can
specify a list of group sizes and the predicate will return
a list of groups.
group([],_) = [[]].
group([N|Ns],Xs) = [[G|Gs] : (G,Rs) in combinations1(N,Xs), Gs in group(Ns,Rs)].
combinations1(N,Xs) = [(Comb,CombR) : Comb in combinations(N,Xs),
CombR = difference(Xs,Comb)].
difference(Xs,[]) = Xs.
difference(Xs,[Y|Ys]) = difference(delete(Xs,Y),Ys).
Sorting a list of lists according to length of sublists
a) We suppose that a list contains elements that are lists
themselves. The objective is to sort the elements of this
list according to their length. E.g. short lists first,
longer lists later, or vice versa.
b) Again, we suppose that a list contains elements that are
lists themselves. But this time the objective is to sort the
elements of this list according to their length frequency;
i.e., in the default, where sorting is done ascendingly,
lists with rare lengths are placed first, others with a more
frequent length come later.
lsort(Ls) = Res =>
Xs = [(len(L),L) : L in Ls],
Ys = sort(Xs),
Res = [L : (_,L) in Ys].
lfsort(Ls) = Res =>
Xs = [(len(L),L) : L in Ls],
Ys = sort(Xs),
Zs = group_by_len(Ys),
Res = restore_lists(sort(Zs)).
group_by_len([]) = [].
group_by_len([(Len,L)|Xs]) = [(Count,[L|G])|Ys] =>
group_by_len_aux(Xs,Len,1,Count,G,Ys).
group_by_len_aux([],_Len,Count0,Count,G,Ys) => G = [], Ys = [], Count = Count0.
group_by_len_aux([(Len,L)|Xs],Len,Count0,Count,G,Ys) =>
G = [L|GR],
group_by_len_aux(Xs,Len,Count0+1,Count,GR,Ys).
group_by_len_aux(Xs,_Len,Count0,Count,G,Ys) =>
G = [],
Count = Count0,
Ys = group_by_len(Xs).
restore_lists([]) = [].
restore_lists([(_,Ls)|Ys]) = Res =>
Ls1 = restore_lists(Ys),
Res = Ls ++ Ls1.