Assignment 2. Due December 16.
----------------------------------------------------------
1. (6 points)
Write a ternary predicate integer_sequence(Name, N, Number) that
succeeds iff Number is the Nth number in the integer sequence named
after Name.
?- integer_sequence(fibonacci, 6, X).
X = 8.
?- integer_sequence(padovan, 4, X).
X = 2.
?- integer_sequence(perrin, 1000, X).
X = 132868931340606743531841660195968328786671571417270282290475384294333707916597496057995813009306073093686467272648435293125.
Implement predicates that compute Fibonacci, Perrin, Padovan, and
Sylvester numbers. Use accumulators.
If the query contains a name whose sequence is not implemented, your
program should print the corresponding text. For instance:
?- integer_sequence(mayr, 5, X).
Sorry, there is no mayr sequence implemented.
true.
Definitions of the Fibonacci, Perrin, Padovan, and Sylvester sequences:
Fibonacci:
Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2) for n>1.
Perrin:
Per(0) = 3
Per(1) = 0
Per(2) = 2
Per(n) = Per(n-2) + P(n-3) for n>2.
Padovan:
Pad(0) = 1
Pad(1) = 1
Pad(2) = 1
Pad(n) = Pad(n-2) + Pad(n-3) for n>2
Sylvester:
Syl(0) = 2
Syl(n) = Syl(n-1)(Syl(n-1)-1)+1 for n>0
-----------------------------
2. (4 points)
Write a 4-ary predicate substitute_in_term(X, Y, T1, T2) that is true if the
term T2 is the result of substituting Y for all occurrences of X in the term T1.
Hint: You may want to use =.. (the built-in univ predicate).
Sample runs:
?- substitute_in_term(a, 1, f(a,b,g(a,h(a))), X).
X = f(1,b,g(1,h(1)))
?- substitute_in_term(a, 1, [a,b,c,a,d,a,e], X).
X = [1,b,c,1,d,1,e]
?- substitute_in_term(a, 1, X, f(1,b,g(1,h(1)))).
X = f(a,b,g(a,h(a)))
-----------------------------
3. (5 points)
Using difference lists, write a predicate flatten_list that flattens nested
occurrences of lists.
Sample runs:
?- flatten_list([a,b,[1,2,3,[z]]], X).
X = [a,b,1,2,3,z]
?- flatten_list([a,b,c], X).
X =[a,b,c]
-----------------------------
4. (5 points)
Write a Prolog program that solves the followng logic puzzle (from logic-puzzles.org).
Figure out the time, first name, pet and cookie for each person using the clues given.
Below are all categories and options used in this puzzle.
Times: 7:30, 8:30, 13:30, 19:30
First Names: Amya, Annika, Chloe, Grace
Pets: cat, dog, frog, pot-bellied pig
Cookies: almond, black_and_white, chocolate_chip, oatmeal_raisin
Clues:
1. The baker who made almond cookies is not Amya.
2. The baker who made chocolate chip cookies doesn't own the pot-bellied pig.
3. The baker who made oatmeal raisin cookies arrived later than the pot-bellied pig owner.
4. The person who arrived at 19:30 is not Chloe.
5. Of the baker who made oatmeal raisin cookies and Grace, one arrived at 8:30 and the other arrived at 19:30.
6. The dog owner is not Annika.
7. The baker who made chocolate chip cookies is Annika.
8. The frog owner is Grace.
9. The dog owner arrived earlier than the frog owner.
10. Either the baker who made black and white cookies or the baker who made chocolate chip cookies owns the frog.
-----------------------------------------------------------------
5. (5 points)
Given the program below, draw the complete derivation trees for
the goals p(5, Y), p(4.5, Y), and p(-1, Y). Mark the part(s) of
the trees that the cut predicate cuts.
p(X, Y) :-
X >= 0,
!,
integer(X),
q(X, Y).
p(X, Y) :-
Z is -X-1,
p(Z, U),
Y is -U.
q(X, Y):-
1 is X mod 2,
!,
Y is X // 2 + 1.
q(X, Y):-
Y is X // 2.
-----------------------------------------------------------------
6. (4 points)
In Assignment 1 you had to define the relation shift(List1, List2) so that
List2 is List1 "shifted rotationally" by one element to the left. Now implement
the version of same predicate for difference lists, called shift_dl.
Sample runs:
?- shift_dl([1,2,3,4|H]-H, Shifted_dl).
H = [1|_G1068],
Shifted_dl = [2, 3, 4, 1|_G1068]-_G1068.
?- shift_dl([1,2,3,4|H]-H, Diff_l), shift_dl(Diff_l, Open_l-[]).
H = [1, 2],
Diff_l = [2, 3, 4, 1, 2]-[2],
Open_l = [3, 4, 1, 2].
-------------------------------------------------------------------
7. (2 points)
Write a ternary predicate delete_all(item,list,result) that is true if result is
obtained from 'list' by deleting all occurrences of 'item'. Use cut to prevent
backtracking.
Sample run:
?-delete_all(a,[a,b,c,a,d,a],X).
X=[b,c,d];
false
?-delete_all(a,[b,c,d],X).
X=[b,c,d];
false
--------------------------------------------------------------------
8. (3 points)
Write a ternary predicate delete_nth that deletes every N'th element from a list.
Sample runs:
?- delete_nth([a,b,c,d,e,f],2,L).
L = [a, c, e] ;
false
?- delete_nth([a,b,c,d,e,f],1,L).
L = [] ;
false
?- delete_nth([a,b,c,d,e,f],0,L).
false
?- delete_nth([a,b,c,d,e,f],10,L).
L = [a, b, c, d, e, f] ;
false
---------------------------------------------------------------------
9. (3 points)
Explain in words what the following program does:
rep.
rep :- rep.
run :-
rep,
write('Try to guess the secret number'),
nl,
read(42),
write("Congrats!"),
nl,
write('Sorry, wanted to say: Congrats!').
----------------------------------------------------------------------
10. (3 points)
The program below is supposed to compute prime factorization of a given positive
integer. Its code is badly formatted. Read Coding Guidelines for Prolog
(http://arxiv.org/pdf/0911.2899) and reformat the program, including the comments,
according to them.
% Prime factorization of a given positive integer number. prime_factors(N, L) succeeds if the L is the list of prime factors of N.
prime_factors(N,L):- N >0,prime_factors(N,2,L).
% prime_factors(N,F,L) succeeds if L is the list of prime factors of N such that N does not have a prime factor less than K.
prime_factors(1,F,[]) :- !.
prime_factors(N,F,[F|L]) :- % N is multiple of F
R is N // F, N =:= R * F, !,
prime_factors(R,F,L).
prime_factors(N,F,L) :-
next_factor( N,F,NF),
prime_factors(N,NF,L). % N is not multiple of F
% next_factor(N,F,NF) succeeds if F does not divide N and NF is the next larger candidate to be a factor of N.
next_factor(N,2,3):- !.
next_factor(N,F,NF) :-F *F < N,!,
NF is F + 2. next_factor(N,_,N). % F > sqrt(N)