/* 99 problems in Picat. Here are some - more or less faithful - port of "99 problems in Prolog" from https://github.com/sunilnandihalli/99-problems-in-prolog Note: In order for have reversibility, some use CP operators instead, e.g. #>, #= instead of of "traditional" operators (>, =). This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ % import util. import cp. main => go. go => L = [1,2,3,4,5,6,2], % #1 my_last(X1,L), writeln(my_last=X1), % #2 last_but_one(X2,L), writeln(last_but_one=X2), % #3 element_at(X3,L,3), writeln(element_at=X3), element_at(I3,L,2), writeln(element_at=I3), % #4 my_length(L,Len4), writeln(my_length=Len4), % #5 my_reverse(L,L5), writeln(my_reverse=L5), % #6 L6 = [a,b,b,a], if is_palindrome(L6) then writeln([L6,is_palindrome]) end, L6b = [a,b,b,a,s], if is_palindrome(L6b) then writeln([L6b,is_palindrome]) else writeln([L6b,is_not_palindrome]) end, % #7 my_flatten([1,2,[3,4],5,[6,[7,[8,9]]]],L7), writeln(my_flatten=L7), % #8 compress([1,1,1,3,2,2,1,4,2,5,5,3,6,5], L8a), writeln(compress=L8a), compress2([1,1,1,3,2,2,1,4,2,5,5,3,6,5], L8), % compress2([], L8), % % compress2(L8,[1,2,3]), % don't work (not surprisingly) writeln(compress2=L8), % #9 pack([1,1,1,2,1,3,3,3,1,4,4], L9a), writeln(pack=L9a), pack2([1,1,1,2,1,3,3,3,1,4,4], L9), writeln(pack2=L9), % #10 encode([1,1,1,2,1,3,3,3,1,4,4], L10a), writeln(encode=L10a), encode2([1,1,1,2,1,3,3,3,1,4,4], L10), writeln(encode2=L10), % #11 encode_modified([1,1,1,2,1,3,3,3,1,4,4], L11a), writeln(encode_modified=L11a), encode_modified2([1,1,1,2,1,3,3,3,1,4,4], L11b), writeln(encode_modified2=L11b), % #12 decode(L11b, L12a), writeln(decode=L12a), decode2(L11b, L12b), writeln(decode2=L12b), % #13 encode_direct([1,1,1,2,1,3,3,3,1,4,4], L13), writeln(encode_direct=L13), % #14 dupli([1,2,3,4,5], L14), writeln(dupli=L14), dupli2([1,2,3,4,5], L14b), writeln(dupli2=L14b), % #15 dupli([1,2,3,4,5], 3, L15), writeln(dupliN=L15), % it's not reversible % dupli(L15b, 3, [1,1,1,2,2,2,3,3,3]), % writeln(dupliNRev=L15b), % #16 drop([1,2,3,4,5], 2, L16), writeln(drop=L16), % #17 split([1,2,3,4,5,6,7,8], 3, L17a,L17b), writeln(split=[L17a,L17b]), split(L17c, 3, [1,2,3],[4,5,6,7]), writeln(splitrev1=L17c), split([1,2,3,4,5,6,7,8], 3, L17d,[4,5,6,7,8]), writeln(splitrev2=L17d), % #18 slice([1,2,3,4,5,6,7],2,5,L18), writeln(slice=L18), % #19 rotate([a,b,c,d,e,f,g,h],3,L19), writeln(rotate=L19), rotate([a,b,c,d,e,f,g,h],-2,L19b), writeln(rotateb=L19b), % #20 remove_at(X20,[1,2,3,4,5,6,7],3, L20), writeln(remove_at=[X20,L20]), % #21 insert_at(3,[1,2,4,5,6,7], 3, L21), writeln(insert_at=L21), % #22 range(1,10, L22), writeln(range=L22), % It's reversible when using CP (#>) so I keep this range(N20a,N20b, [1,2,3,4]), writeln(rangerev=[N20a,N20b]), range(N20c,4, [1,2,3,4]), writeln(rangerev=[N20c]), % #23 rnd_select([2,3,5,7,11,13], 6, L23a), writeln(rnd_select=L23a), rnd_select2([2,3,5,7,11,13], 10, L23b), writeln(rnd_select=L23b), % #24 lotto(7,35,L24), writeln(lotto=L24), writeln(lotto2=lotto2(7,35)), % #25 rnd_permu([1,2,3,4,5],L25), writeln(rnd_permu=L25), % #26 L26All = findall(L26, $combination(3,[1,2,3,4,5], L26)), writeln(combination=L26All), % #27 group3([1,2,3,4,5,6,7,8,9], L27a,L27b,L27c), writeln(group3=[L27a,L27b,L27c]), group([1,2,3,4,5,6,7,8,9], [2,3,4],L27d), writeln(group2=L27d), % #28 % #29 % #30 % #31 P31 = [P : P in 2..100, is_prime(P)], writeln(is_prime=P31), % #32 gcd2(10,70,P32), writeln(gcd2=P32), % #33 if coprime(10,11) then println("10 and 11 are coprimes") end, if coprime(10,12) then println("10 and 12 are coprimes") end, % #34 totient_phi(20,Phi34), writeln(totient_phi=Phi34), % #35 prime_factors(600851475143,P35), writeln(prime_factors=P35), % #36 writeln(prime_factors_mult), prime_factors_mult(315, P36), writeln(prime_factors_mult=P36), prime_factors_mult(2305567963945518424753102147331756070, P36b), writeln(prime_factors_mult=P36b), % #37 totient_phi_2(36,Phi37), writeln(totient_phi_2=Phi37), Phi37b= [[N,P] : N in 1..100, totient_phi_2(N,P)], write(totient_phi_2=Phi37b), % #38 totient_test(1000002), % #39 prime_list(50,100, P39), writeln(prime_list=P39), prime_list2(50,100, P39b), writeln(prime_list2=P39b), println("timing prime_list/2:"), time(prime_list(2,1000000, P39c)), % writeln(len=P39c.length), println("timing prime_list2/2:"), time(prime_list2(2,1000000, P39d)), % writeln(len=P39d.length), % #40 goldbach(28,P40), writeln(goldbach=P40), foreach(I in 4..2..20) goldbach2(I,G), writeln([I,G, G.length]) end, % #41 goldbach_list(4,20), % #42 % #43 % #44 % #45 % #46 % truth_table(A,B,and(A,or(A,B))), p54_test(), nl. % P01 (*): Find the last element of a list % % my_last(X,L) :- X is the last element of the list L % (element,list) (?,?) % % Note: last(?Elem, ?List) is predefined % Prolog code: % my_last(X,[X]). % my_last(X,[_|L]) :- my_last(X,L). my_last(X,[Y]) => X=Y. my_last(X,[_|L]) => my_last(X,L). % P02 (*): Find the last but one element of a list % % last_but_one(X,L) :- X is the last but one element of the list L % (element,list) (?,?) % % Prolog code: % last_but_one(X,[X,_]). % last_but_one(X,[_,Y|Ys]) :- last_but_one(X,[Y|Ys]). last_but_one(X,[Y,_]) => X = Y. last_but_one(X,[_,Y|Ys]) => last_but_one(X,[Y|Ys]). % P03 (*): Find the K'th element of a list. % The first element in the list is number 1. % % element_at(X,L,K) :- X is the K'th element of the list L % (element,list,integer) (?,?,+) % % Note: nth1(?Index, ?List, ?Elem) is predefined % % Prolog code % element_at(X,[X|_],1). % element_at(X,[_|L],K) :- K > 1, K1 is K - 1, element_at(X,L,K1). element_at(X,[Y|_],1) => X = Y. element_at(X,[_|L],K) => K > 1, K1 = K - 1, element_at(X,L,K1). % P04 (*): Find the number of elements of a list. % % my_length(L,N) :- the list L contains N elements % (list,integer) (+,?) % % Note: length(?List, ?Int) is predefined % % Prolog code: % my_length([],0). % my_length([_|L],N) :- my_length(L,N1), N is N1 + 1. my_length([],N) => N = 0. my_length([_|L],N) => my_length(L,N1), N = N1 + 1. % P05 (*): Reverse a list. % % my_reverse(L1,L2) :- L2 is the list obtained from L1 by reversing % the order of the elements. % (list,list) (?,?) % % Note: reverse(+List1, -List2) is predefined % Prolog code: % my_reverse(L1,L2) :- my_rev(L1,L2,[]). % my_rev([],L2,L2) :- !. % my_rev([X|Xs],L2,Acc) :- my_rev(Xs,L2,[X|Acc]). my_reverse(L1,L2) => my_rev(L1,L2,[]). my_rev([],L2,L3) => L2 = L3. my_rev([X|Xs],L2,Acc) => my_rev(Xs,L2,[X|Acc]). % P06 (*): Find out whether a list is a palindrome % A palindrome can be read forward or backward; e.g. [x,a,m,a,x] % % is_palindrome(L) => L is a palindrome list % (list) (?) % is_palindrome(L) => my_reverse(L,L). % P07 (**): Flatten a nested list structure. % % my_flatten(L1,L2) :- the list L2 is obtained from the list L1 by % flattening; i.e. if an element of L1 is a list then it is replaced % by its elements, recursively. % (list,list) (+,?) % % Note: flatten(+List1, -List2) is a predefined predicate my_flatten(X,Y), not list(X) ?=> Y = [X]. my_flatten([],X) => X = []. my_flatten([X|Xs],Zs) => my_flatten(X,Y), my_flatten(Xs,Ys), append(Y,Ys,Zs). % P08 (**): Eliminate consecutive duplicates of list elements. % % compress(L1,L2) :- the list L2 is obtained from the list L1 by % compressing repeated occurrences of elements into a single copy % of the element. % (list,list) (+,?) % % Prolog version: % compress([],[]). % compress([X],[X]). % compress([X,X|Xs],Zs) :- compress([X|Xs],Zs). % compress([X,Y|Ys],[X|Zs]) :- X \= Y, compress([Y|Ys],Zs). compress([],Y) => Y=[]. compress([X],Y1) => Y1=[X]. compress([X,X|Xs],Zs) => compress([X|Xs],Zs). compress([X,Y|Ys],Z1) => Z1=[X|Zs], X != Y, compress([Y|Ys],Zs). compress2(X,Y) => Y1 = [X[1]], foreach(I in 2..X.length, X[I] != X[I-1]) Y1 := Y1 ++ [X[I]] end, Y = Y1. % P09 (**): Pack consecutive duplicates of list elements into sublists. % pack(L1,L2) :- the list L2 is obtained from the list L1 by packing % repeated occurrences of elements into separate sublists. % (list,list) (+,?) pack([],Y) => Y = []. pack([X|Xs],[Z|Zs]) => transfer(X,Xs,Ys,Z), pack(Ys,Zs). pack(X1,Z1) => X1=[X|Xs],Z1=[Z|Zs],transfer(X,Xs,Ys,Z), pack(Ys,Zs). % transfer(X,Xs,Ys,Z) Ys is the list that remains from the list Xs % when all leading copies of X are removed and transfered to Z transfer(X,Y1,Y2,Y) ?=> Y1=[], Y2=[], Y = [X]. transfer(X,Y1,Y2,Z) ?=> Y1=Y2, Y1 = [Y|_Ys], X != Y, Z = [X]. transfer(X,Y1,Ys,Z1) ?=> Y1=[X|Xs], Z1=[X|Zs], transfer(X,Xs,Ys,Zs). pack2(X,Y) => Y1 = [], Tmp = [X[1]], foreach(I in 2..X.length) if X[I] == X[I-1] then Tmp := Tmp ++ [X[I]] else Y1 := Y1 ++ [Tmp], Tmp := [X[I]] end end, if Tmp.length > 0 then Y1 := Y1 ++ [Tmp] end, Y = Y1. % P10 (*): Run-length encoding of a list % % encode(L1,L2) :- the list L2 is obtained from the list L1 by run-length % encoding. Consecutive duplicates of elements are encoded as terms [N,E], % where N is the number of duplicates of the element E. % (list,list) (+,?) % % :- ensure_loaded(p09). encode(L1,L2) => pack2(L1,L), transform(L,L2). % Prolog code: % transform([],[]). % transform([[X|Xs]|Ys],[[N,X]|Zs]) :- length([X|Xs],N), transform(Ys,Zs). transform(X,Y) ?=> X = [], Y = []. transform(X1, Z1) ?=> X1 = [[X|Xs]|Ys],Z1=[[N,X]|Zs], N = length([X|Xs]), transform(Ys,Zs). encode2(L1,L2) => pack2(L1,L), transform2(L,L2). transform2(L,L2) => Tmp = [], foreach(E in L) Tmp := Tmp ++ [[E.length,E[1]]] end, L2 = Tmp. % P11 (*): Modified run-length encoding % encode_modified(L1,L2) :- the list L2 is obtained from the list L1 by % run-length encoding. Consecutive duplicates of elements are encoded % as terms [N,E], where N is the number of duplicates of the element E. % However, if N equals 1 then the element is simply copied into the % output list. % (list,list) (+,?) encode_modified(L1,L2) => encode(L1,L), strip(L,L2). strip([],Y) ?=> Y = []. strip([[1,X]|Ys],Z1) ?=> Z1=[X|Zs], strip(Ys,Zs). strip([[N,X]|Ys],Z1) ?=> Z1=[[N,X]|Zs], N > 1, strip(Ys,Zs). encode_modified2(L1,L2) => encode2(L1,L), strip2(L,L2). strip2([],[]) => true. strip2(X,Y) => Y1 = [], foreach(E in X) if E[1] == 1 then Y1 := Y1 ++ [E[2]] else Y1 := Y1 ++ [E] end end, Y = Y1. % P12 (**): Decode a run-length compressed list. % decode(L1,L2) :- L2 is the uncompressed version of the run-length % encoded list L1. % (list,list) (+,?) % Note this is a decode of encode_modified/2. decode([],Y) ?=> Y = []. decode([X|Ys],Z1) ?=> not list(X), Z1=[X|Zs], decode(Ys,Zs). decode([[1,X]|Ys],Z1) ?=> Z1 = [X|Zs], decode(Ys,Zs). decode([[N,X]|Ys],Z1) ?=> N > 1, N1 = N - 1, Z1 = [X|Zs], decode([[N1,X]|Ys],Zs). decode2(X,Y) => Y1 = [], foreach(E in X) if list(E) then Y1 := Y1 ++ [E[2] : _I in 1..E[1]] else Y1 := Y1 ++ [E] end end, Y = Y1. % P13 (**): Run-length encoding of a list (direct solution) % encode_direct(L1,L2) :- the list L2 is obtained from the list L1 by % run-length encoding. Consecutive duplicates of elements are encoded % as terms [N,E], where N is the number of duplicates of the element E. % However, if N equals 1 then the element is simply copied into the % output list. % (list,list) (+,?) % Prolog code: % encode_direct([],[]). % encode_direct([X|Xs],[Z|Zs]) :- count(X,Xs,Ys,1,Z), encode_direct(Ys,Zs). encode_direct([],Y) ?=> Y = []. encode_direct([X|Xs],Z1) ?=> Z1=[Z|Zs], count(X,Xs,Ys,1,Z), encode_direct(Ys,Zs). % count(X,Xs,Ys,K,T) Ys is the list that remains from the list Xs % when all leading copies of X are removed. T is the term [N,X], % where N is K plus the number of X's that can be removed from Xs. % In the case of N=1, T is X, instead of the term [1,X]. % Prolog code % count(X,[],[],1,X). % count(X,[],[],N,[N,X]) :- N > 1. % count(X,[Y|Ys],[Y|Ys],1,X) :- X \= Y. % count(X,[Y|Ys],[Y|Ys],N,[N,X]) :- N > 1, X \= Y. % count(X,[X|Xs],Ys,K,T) :- K1 is K + 1, count(X,Xs,Ys,K1,T). count(X,[],[],1,X1) => X1=X. count(X,[],Y2,N,NX) => Y2=[],NX=[N,X], N > 1. count(X,Y1,Y2,N,NX) ?=> NX=[N,X], N=1,Y1=[Y|_Ys], Y2 = Y1, X != Y. count(X,Y1,Y2,N,NX) ?=> Y1=[Y|_Ys], Y2=Y1, NX=[N,X], N > 1, X != Y. count(X,X1,Ys,K,T) => X1=[X|Xs], count(X,Xs,Ys,K+1,T). % P14 (*): Duplicate the elements of a list % % dupli(L1,L2) :- L2 is obtained from L1 by duplicating all elements. % (list,list) (?,?) % dupli(X,Y) ?=> X = [], Y = []. % dupli([X|Xs],[X,X|Ys]) ?=> writeln(dupli2), dupli(Xs,Ys). dupli(X1,Y1) ?=> X1 = [X|Xs], Y1 = [X,X|Ys], dupli(Xs,Ys). dupli2(X,Y) => Y1 = [], foreach(E in X) Y1 := Y1 ++ [E,E] end, Y = Y1. % P15 (**): Duplicate the elements of a list agiven number of times % % dupli(L1,N,L2) :- L2 is obtained from L1 by duplicating all elements % N times. % (list,integer,list) (?,+,?) dupli(L1,N,L2) ?=> dupli(L1,N,L2,N). % dupli(L1,N,L2,K) :- L2 is obtained from L1 by duplicating its leading % element K times, all other elements N times. % (list,integer,list,integer) (?,+,?,+) % dupli([],_,Y,_) ?=> Y = []. dupli(X1,N,Ys,0) ?=> X1=[_|Xs], dupli(Xs,N,Ys,N). dupli(X1,N,X2,K) ?=> X1 = [X|Xs], X2 = [X|Ys], K > 0, dupli([X|Xs],N,Ys,K-1). % P16 (**): Drop every N'th element from a list % % drop(L1,N,L2) :- L2 is obtained from L1 by dropping every N'th element. % (list,integer,list) (?,+,?) drop(L1,N,L2) => drop(L1,N,L2,N). % drop(L1,N,L2,K) :- L2 is obtained from L1 by first copying K-1 elements % and then dropping an element and, from then on, dropping every % N'th element. % (list,integer,list,integer) (?,+,?,+) drop([],_,Y,_) => Y = []. drop([_|Xs],N,Ys,1) => drop(Xs,N,Ys,N). drop([X|Xs],N,Y1,K) => Y1=[X|Ys],K > 1, K1 = K - 1, drop(Xs,N,Ys,K1). % P17 (*): Split a list into two parts % % split(L,N,L1,L2) :- the list L1 contains the first N elements % of the list L, the list L2 contains the remaining elements. % (list,integer,list,list) (?,+,?,?) split(L,0,L1,L2) => L1=[], L2 = L. split(L,N,L1,Zs) => L=[X|Xs], L1=[X|Ys], N > 0, N1 = N - 1, split(Xs,N1,Ys,Zs). % P18 (**): Extract a slice from a list % % slice(L1,I,K,L2) :- L2 is the list of the elements of L1 between % index I and index K (both included). % (list,integer,integer,list) (?,+,+,?) slice(L1,1,1,L2) => L1=[X|_], L2=[X]. slice(L1,1,K,L2) => L1=[X|Xs], L2=[X|Ys], K > 1, K1 = K - 1, slice(Xs,1,K1,Ys). slice(L1,I,K,Ys) => L1=[_|Xs],I > 1, I1 = I - 1, K1 = K - 1, slice(Xs,I1,K1,Ys). % P19 (**): Rotate a list N places to the left % rotate(L1,N,L2) :- the list L2 is obtained from the list L1 by % rotating the elements of L1 N places to the left. % Examples: % rotate([a,b,c,d,e,f,g,h],3,[d,e,f,g,h,a,b,c]) % rotate([a,b,c,d,e,f,g,h],-2,[g,h,a,b,c,d,e,f]) % (list,integer,list) (+,+,?) rotate(L1,N,L2) ?=> N >= 0, my_length(L1,NL1), N1 = N mod NL1, rotate_left(L1,N1,L2). rotate(L1,N,L2) ?=> N < 0, % original Prolog code: % length(L1,NL1), N1 is NL1 + (N mod NL1), rotate_left(L1,N1,L2). my_length(L1,NL1), N1 = (NL1 + N) mod NL1, rotate_left(L1,N1,L2). rotate_left(L,0,L1) => L1=L. rotate_left(L1,N,L2) => N > 0, split(L1,N,S1,S2), append(S2,S1,L2). % P20 (*): Remove the K'th element from a list. % The first element in the list is number 1. % % remove_at(X,L,K,R) :- X is the K'th element of the list L; R is the % list that remains when the K'th element is removed from L. % (element,list,integer,list) (?,?,+,?) remove_at(X,L,1,R) => L=[X|Xs], R=Xs. remove_at(X,L,K,R) => L=[Y|Xs], R=[Y|Ys], K #> 1, K1 #= K - 1, remove_at(X,Xs,K1,Ys). % P21 (*): Insert an element at a given position into a list % The first element in the list is number 1. % % insert_at(X,L,K,R) :- X is inserted into the list L such that it % occupies position K. The result is the list R. % (element,list,integer,list) (?,?,+,?) insert_at(X,L,K,R) => remove_at(X,R,K,L). % P22 (*): Create a list containing all integers within a given range. % % range(I,K,L) :- I <= K, and L is the list containing all % consecutive integers from I to K. % (integer,integer,list) (+,+,?) % Prolog code: % range(I,I,[I]). % range(I,K,[I|L]) :- I < K, I1 is I + 1, range(I1,K,L). % Note: Using #< makes it reversible which means that the mode is (?,?,?). range(I,I2,L) ?=> I=I2, L = [I]. range(I,K,L2) ?=> L2=[I|L], I #< K, I1 = I + 1, range(I1,K,L). % P23 (**): Extract a given number of randomly selected elements % from a list. % rnd_select(L,N,R) :- the list R contains N randomly selected % items taken from the list L. % (list,integer,list) (+,+,-) % Note: This is random selection without replacement, which % assumes that N must be <= L.length rnd_select(_,0,R) ?=> R = []. rnd_select(Xs,N,R) ?=> R = [X|Zs], N > 0, my_length(Xs,L), % I = random(L) + 1, % Picat's random don't work like this I = 1+random2() mod L, remove_at(X,Xs,I,Ys), N1 = N - 1, rnd_select(Ys,N1,Zs). % % Variant using list compresension: mode (+,+,-) % Note: We don't assume anything about N and L.length. % This is random selection _with_ replacement rnd_select2(L,N,R) => R1 = [], Len = L.length, foreach(_I in 1..N) E = L[1+random2() mod Len], R1 := R1 ++ [E] end, R = R1. % P24 (*): Lotto: Draw N different random numbers from the set 1..M % % lotto(N,M,L) :- the list L contains N randomly selected distinct % integer numbers from the interval 1..M % (integer,integer,number-list) (+,+,-) % Prolog code: lotto(N,M,L) => range(1,M,R), rnd_select(R,N,L). % as a function lotto2(N,M) = L => range(1,M,R), rnd_select(R,N,L). % P25 (*): Generate a random permutation of the elements of a list % % rnd_permu(L1,L2) :- the list L2 is a random permutation of the % elements of the list L1. % (list,list) (+,-) rnd_permu(L1,L2) => my_length(L1,N), rnd_select(L1,N,L2). % P26 (**): Generate the combinations of k distinct objects % chosen from the n elements of a list. % % combination(K,L,C) :- C is a list of K distinct elements % chosen from the list L % Prolog code % combination(0,_,[]). % combination(K,L,[X|Xs]) :- el(X,L,R),K1 is K-1, combination(K1,R,Xs). combination(0,_,C) => C = []. combination(K,L,C) => C=[X|Xs], el(X,L,R), K1 = K-1, combination(K1,R,Xs). % Find out what the following predicate el/3 exactly does. el(X,L1,L) ?=> L1=[X|L]. el(X,L1,R) => L1 = [_|L], el(X,L,R). % P27 (**) Group the elements of a set into disjoint subsets. % Problem a) % group3(G,G1,G2,G3) :- distribute the 9 elements of G into G1, G2, and G3, % such that G1, G2 and G3 contain 2,3 and 4 elements respectively group3(G,G1,G2,G3) => selectN(2,G,G1), subtract(G,G1,R1), selectN(3,R1,G2), subtract(R1,G2,R2), selectN(4,R2,G3), subtract(R2,G3,[]). % selectN(N,L,S) :- select N elements of the list L and put them in % the set S. Via backtracking return all posssible selections, but % avoid permutations; i.e. after generating S = [a,b,c] do not return % S = [b,a,c], etc. selectN(0,_,S) => S = []. selectN(N,L,S1) => N > 0, S1 = [X|S], el(X,L,R), selectN(N-1,R,S). % el(X,[X|L],L). % el(X,[_|L],R) :- el(X,L,R). % subtract/3 is predefined in Prolog, but not in Picat subtract([], _, L3) ?=> L3 = []. subtract(L1, B, D) ?=> L1 = [A|C], membchk(A, B), subtract(C, B, D). subtract(L1, C, L3) ?=> L1= [A|B], L3 =[A|D], subtract(B, C, D). % Problem b): Generalization % group(G,Ns,Gs) :- distribute the elements of G into the groups Gs. % The group sizes are given in the list Ns. group([],Ns,Gs) => Ns = [], Gs = []. group(G,NN,G2) => NN = [N1|Ns], G2 = [G1|Gs], selectN(N1,G,G1), subtract(G,G1,R), group(R,Ns,Gs). % P28 (**) Sorting a list of lists according to length % % a) length sort % % lsort(InList,OutList) :- it is supposed that the elements of InList % are lists themselves. Then OutList is obtained from InList by sorting % its elements according to their length. lsort/2 sorts ascendingly, % lsort/3 allows for ascending or descending sorts. % (list_of_lists,list_of_lists), (+,?) % hakank: I skip this for now... % P31 (**) Determine whether a given integer number is prime. % is_prime(P) :- P is a prime number % (integer) (+) table is_prime(2) => true. is_prime(3) => true. is_prime(P), P > 3, P mod 2 != 0 => not has_factor(P,3). % has_factor(N,L) :- N has an odd factor F >= L. % (integer, integer) (+,+) has_factor(N,L), N mod L == 0 => true. has_factor(N,L) => L * L <= N, L2 = L + 2, has_factor(N,L2). % P32 (**) Determine the greatest common divisor of two positive integers. % gcd(X,Y,G) :- G is the greatest common divisor of X and Y % (integer, integer, integer) (+,+,?) gcd2(X,0,X2) => X > 0, X = X2. gcd2(X,Y,G) => Y > 0, Z = X mod Y, gcd2(Y,Z,G). % Declare gcd as an arithmetic function; so you can use it % like this: ?- G is gcd(36,63). % :- arithmetic_function(gcd/2). % P33 (*) Determine whether two positive integer numbers are coprime. % Two numbers are coprime if their greatest common divisor equals 1. % coprime(X,Y) :- X and Y are coprime. % (integer, integer) (+,+) coprime(X,Y) => gcd2(X,Y,1). % P34 (**) Calculate Euler's totient function phi(m). % Euler's so-called totient function phi(m) is defined as the number % of positive integers r (1 <= r < m) that are coprime to m. % Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note: phi(1) = 1. % totient_phi(M,Phi) :- Phi is the value of the Euler's totient function % phi for the argument M. % (integer, integer) (+,-) totient_phi(1,Phi) => Phi = 1. totient_phi(M,Phi) => t_phi(M,Phi,1,0). % t_phi(M,Phi,K,C) => Phi = C + N, where N is the number of integers R % such that K <= R < M and R is coprime to M. % (integer,integer,integer,integer) (+,-,+,+) t_phi(M,Phi,M2,Phi2) ?=> M=M2, Phi=Phi2. t_phi(M,Phi,K,C), K < M, coprime(K,M) => C1 = C + 1, K1 = K + 1, t_phi(M,Phi,K1,C1). t_phi(M,Phi,K,C), K < M => K1 = K + 1, t_phi(M,Phi,K1,C). % P35 (**) Determine the prime factors of a given positive integer. % prime_factors(N, L) :- N is the list of prime factors of N. % (integer,list) (+,?) prime_factors(N,L), N > 0 => prime_factors(N,L,2). % prime_factors(N,L,K) :- L is the list of prime factors of N. It is % known that N does not have any prime factors less than K. prime_factors(1,L,_) => L=[]. prime_factors(N,FL,F) ?=> % N is multiple of F FL = [F|L], R = N // F, N == R * F, prime_factors(R,L,F). prime_factors(N,L,F) => next_factor(N,F,NF), prime_factors(N,L,NF). % N is not multiple of F % next_factor(N,F,NF) :- when calculating the prime factors of N % and if F does not divide N then NF is the next larger candidate to % be a factor of N. next_factor(_,2,NF), NF=3 => true. next_factor(N,F,NF), F * F < N => NF = F + 2. next_factor(N,_,N2), N=N2 => true. % F > sqrt(N) % P36 (**) Determine the prime factors of a given positive integer (2). % Construct a list containing the prime factors and their multiplicity. % Example: % ?- prime_factors_mult(315, L). % L = [[3,2],[5,1],[7,1]] % prime_factors_mult(N, L) => L is the list of prime factors of N. It is % composed of terms [F,M] where F is a prime factor and M its multiplicity. % (integer,list) (+,?) prime_factors_mult(N,L), N > 0 => prime_factors_mult(N,L,2). % prime_factors_mult(N,L,K) => L is the list of prime factors of N. It is % known that N does not have any prime factors less than K. prime_factors_mult(1,F,_) => F=[]. prime_factors_mult(N,FML,F) ?=> divide(N,F,M,R), % F divides N FML = [[F,M]|L], next_factor(R,F,NF), prime_factors_mult(R,L,NF). prime_factors_mult(N,L,F) => % F does not divide N next_factor(N,F,NF), prime_factors_mult(N,L,NF). % divide(N,F,M,R) => N = R * F**M, M >= 1, and F is not a factor of R. % (integer,integer,integer,integer) (+,+,-,-) divide(N,F,M,R) => divi(N,F,M,R,0), M > 0. divi(N,F,M,R,K) ?=> S = N // F, N == S * F, % F divides N K1 = K + 1, divi(S,F,M,R,K1). divi(N,_,M,N2,M2) => N2 = N, M2 = M. % P37 (**) Calculate Euler's totient function phi(m) (improved). % See problem P34 for the definition of Euler's totient function. % If the list of the prime factors of a number m is known in the % form of problem P36 then the function phi(m) can be efficiently % calculated as follows: % % Let [[p1,m1],[p2,m2],[p3,m3],...] be the list of prime factors (and their % multiplicities) of a given number m. Then phi(m) can be calculated % with the following formula: % % phi(m) = (p1 - 1) * p1 ** (m1 - 1) * (p2 - 1) * p2 ** (m2 - 1) * % (p3 - 1) * p3 ** (m3 - 1) * ... % % Note that a ** b stands for the b'th power of a. % totient_phi_2(N,Phi) :- Phi is the value of Euler's totient function % for the argument N. % (integer,integer) (+,?) totient_phi_2(N,Phi) => prime_factors_mult(N,L), to_phi(L,Phi). to_phi([],Phi) => Phi=1. to_phi(F1L,Phi) ?=> F1L=[[F,1]|L], to_phi(L,Phi1), Phi = Phi1 * (F - 1). to_phi(FML,Phi) => FML=[[F,M]|L], M > 1, M1 = M - 1, to_phi([[F,M1]|L],Phi1), Phi = Phi1 * F. % P38 (*) Compare the two methods of calculating Euler's totient function. % Use the solutions of problems P34 and P37 to compare the algorithms. % Take the number of logical inferences as a measure for efficiency. totient_test(N) => printf("\n"), write('totient_phi (P34):'), time(totient_phi(N,Phi1)), write('result = '), write(Phi1), nl, write('totient_phi_2 (P37):'), time(totient_phi_2(N,Phi2)), write('result = '), write(Phi2), nl. % P39 (*) A list of prime numbers. % Given a range of integers by its lower and upper limit, construct a % list of all prime numbers in that range. % prime_list(A,B,L) :- L is the list of prime number P with A <= P <= B prime_list(A,B,L), A =< 2 => p_list(2,B,L). prime_list(A,B,L), A > 2 => A1 = (A // 2) * 2 + 1, p_list(A1,B,L). p_list(A,B,L) ?=> A > B, L = []. p_list(A,B,AL) ?=> AL=[A|L], is_prime(A), next(A,A1), p_list(A1,B,L). p_list(A,B,L) => next(A,A1), p_list(A1,B,L). next(2,N) => N = 3 . next(A,A1) => A1 = A + 2. % Using list comprehension is much easier, and faster prime_list2(A,B, L) => L = [ I : I in A..B, is_prime(I)]. % P40 (**) Goldbach's conjecture. % Goldbach's conjecture says that every positive even number greater % than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. % goldbach(N,L) :- L is the list of the two prime numbers that % sum up to the given N (which must be even). % (integer,integer) (+,-) goldbach(N,L), N mod 2 == 1 => L = []. goldbach(N,L), N < 2 => L = []. goldbach(4,L) => L = [2,2]. goldbach(N,L) => N mod 2 == 0, N > 4, goldbach(N,L,3). goldbach(N,PQ,P) ?=> PQ=[P,Q], Q = N - P, is_prime(Q). goldbach(N,L,P), P < N ?=> next_prime(P,P1), goldbach(N,L,P1). next_prime(P,P1) ?=> P1 = P + 2, is_prime(P1). next_prime(P,P1) => P2 = P + 2, next_prime(P2,P1). % another approach goldbach2(N,L) => L = [ [P1,P2] : P1 in 1..N//2, P2 in P1..N, prime(P1),prime(P2), P1+P2=N]. % P41 (*) A list of Goldbach compositions. % Given a range of integers by its lower and upper limit, % print a list of all even numbers and their Goldbach composition. % goldbach_list(A,B) :- print a list of the Goldbach composition % of all even numbers N in the range A <= N <= B % (integer,integer) (+,+) goldbach_list(A,B) => goldbach_list(A,B,2). % goldbach_list(A,B,L) => perform goldbach_list(A,B), but suppress % all output when the first prime number is less than the limit L. goldbach_list(A,B,L) => A =< 4, g_list(4,B,L). goldbach_list(A,B,L) => A1 = ((A+1) // 2) * 2, g_list(A1,B,L). g_list(A,B,_) ?=> A > B. g_list(A,B,L) => goldbach(A,[P,Q]), print_goldbach(A,P,Q,L), A2 = A + 2, g_list(A2,B,L). print_goldbach(A,P,Q,L) => P >= L, printf("%w = %w + %w",A,P,Q), nl. print_goldbach(_,_,_,_) => true. % P46 (**) Truth tables for logical expressions. % Define predicates and/2, or/2, nand/2, nor/2, xor/2, impl/2 % and equ/2 (for logical equivalence) which succeed or % fail according to the result of their respective operations; e.g. % and(A,B) will succeed, if and only if both A and B succeed. % Note that A and B can be Prolog goals (not only the constants % true and fail). % A logical expression in two variables can then be written in % prefix notation, as in the following example: and(or(A,B),nand(A,B)). % % Now, write a predicate table/3 which prints the truth table of a % given logical expression in two variables. % % Example: % ?- table(A,B,and(A,or(A,B))). % true true true % true fail true % fail true fail % fail fail fail % and(A,B) :- A, B. % or(A,_) :- A. % or(_,B) :- B. % equ(A,B) :- or(and(A,B), and(not(A),not(B))). % xor(A,B) :- not(equ(A,B)). % nor(A,B) :- not(or(A,B)). % nand(A,B) :- not(and(A,B)). % impl(A,B) :- or(not(A),B). % % bind(X) :- instantiate X to be true and false successively % bind(true). % bind(fail). % table(A,B,Expr) :- % bind(A), bind(B), % write('-----------------------------'),nl, % mydo(A,B,Expr), fail. % mydo(A,B,Expr):-write(A),write(' '),write(B),write(' '),writeValueOf(Expr),nl. % writeValueOf(Expr):-Expr,write(itsTrue),nl. % writeValueOf(Expr):-not(Expr),write(itsFalse),nl. % % hakank: Skipping some other problems.... % % P54: Write a predicate istree/1 which succeeds if and only if its argument % is a Prolog term representing a binary tree. % % istree(T) :- T is a term representing a binary tree (i), (o) istree(nil) => true. istree(T) => T = $t(_,L,R), istree(L), istree(R). % Test cases (can be used for other binary tree problems as well) p54_test => foreach(I in 1..4) p54_tree(I, Tree), if istree(Tree) then writeln([Tree, is_a_tree]) else writeln([Tree, not_a_tree]) end end, p54_tree(1, Tree), writeln(traverse_tree1=traverse_tree1(Tree)), writeln(traverse_tree2=traverse_tree2(Tree)), writeln(traverse_tree3=traverse_tree3(Tree)), nl. p54_tree(1,T) => T = $t(a,$t(b,$t(d,nil,nil),$t(e,nil,nil)),$t(c,nil,$t(f,$t(g,nil,nil),nil))). p54_tree(2,T) => T = $t(a,nil,nil). p54_tree(3,T) => T = nil. p54_tree(4,T) => T = $t(nil,$t(nil)). % is not a tree % % Traversing a $t/3 tree (as a function) % traverse_tree1(nil) = []. traverse_tree1(T) = L => T = $t(Val,Left,Right), L = [Val] ++ traverse_tree1(Left) ++ traverse_tree1(Right). traverse_tree2(nil) = []. traverse_tree2(T) = L => T = $t(Val,Left,Right), L = traverse_tree2(Left) ++ [Val] ++ traverse_tree2(Right). traverse_tree3(nil) = []. traverse_tree3(T) = L => T = $t(Val,Left,Right), L = traverse_tree3(Left) ++ traverse_tree3(Right)++ [Val].