Ninety-Nine Picat Problems

P1_01

Find the last element of a list.


% myLast(L) = last(L).

myLast([X]) = X.
myLast([_|Xs]) = myLast(Xs).

P1_02

Find the last but one element of a list.


myButLast([X,_]) = X.
myButLast([_|Xs]) = myButLast(Xs).

P1_03

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).

P1_04

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).

P1_05

Reverse a list.


% myReverse(L) = reverse(L).

myReverse(L) = myReverse(L,[]).

myReverse([],R) = R.
myReverse([X|Xs],R) = myReverse(Xs,[X|R]).

P1_06

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).

P1_07

Flatten a nested list structure.


myFlatten([X|Xs]) = myFlatten(X) ++ myFlatten(Xs).
myFlatten([]) = [].
myFlatten(X) = [X].

P1_08

Eliminate consecutive duplicates of list elements.


compress([X|Ys@[X|_]]) = compress(Ys).
compress([X|Ys]) = [X|compress(Ys)].
compress(Ys) = Ys.

P1_09

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).

P1_10

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].

p1_11

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].

p1_12

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)].

p1_13

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).

p1_14

Duplicate the elements of a list.


dupli([]) = [].
dupli([X|Xs]) = [X,X|dupli(Xs)].

p1_15

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).

p1_16

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).

p1_17

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).

p1_18

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).

p1_19

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).

p1_20

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)].

p1_21

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)].

p1_22

Create a list containing all integers within a given range.


range(X,Y) = X..Y.

p1_23

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).

p1_24

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).

p1_25

Generate a random permutation of the elements of a list.


rnd_permu(Xs) = rnd_select(Xs, len(Xs)).

p1_26

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).
                       

p1_27

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).

p1_28

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.