ASSIGNMENT 2. Due December 28. ============================= Total points: 40 Grading with respect to points P: 35 < P: 1 very good 29 < P =< 35: 2 good 23 < P =< 29: 3 satisfactory 19 < P =< 23: 4 adequate P =< 19: 5 not adequate -------------------------------------------------------------------------------- 1. 6 points. Write a predicate that starts interaction with the user, asking her to input a number, then another number, and then the operation (addition or multiplication). After that, the program performs the operation on the numbers and writes the result in a file. The process repeats until the user types 'finish'. All the results should be written in one file. If the user makes a wrong input (it is not a number, or it is neither addition nor multiplication), the program should repeat the question, indicating that what has been typed in is not a number, or is a wrong operation. IO predicates can be found in the Section 5 of the book. Check also the Prolog manual. You can use the built-in 'number' predicate to check whether the argument is a Prolog number or not. ================================================================================ 2. 5 points. Write a predicate union(L1,L2,L3) that is true if L3 is equal to the list containing the union of the elements in L1 and L2 without any duplicates. That means, the elements of L3 are those that occur in either L1 or in L2. In case L1 or L2 contain duplicates, they must be also filtered out. The relative order of the elements should be preserved. Sample runs: ?- union([1,2,3,4],[1,3,5,6],[1,2,3,4,5,6]). true. ?- union([1,2,3,4,3,2],[1,3,5,6,5],[1,2,3,4,5,6]). true. ?- union([1,2,3,4],[1,3,5,6],X). X = [1,2,3,4,5,6]. ?- union([1,2,3,4,3,2],[1,3,5,6,5],X). X = [1,2,3,4,5,6]. ?- union([1,2,3],[4,3],[1,2,3]). false. ================================================================================ 3. 5 points. 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. ================================================================================ 4. 5 points. The Perrin numbers are defined by the recurrence relation P(0) = 3, P(1) = 0, P(2) = 2, and P(n) = P(n − 2) + P(n − 3) for n > 2. The sequence of Perrin numbers starts with 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 Implement in Prolog this recurrence relation. Use accumulators. Sample run: ?- perrin(7, P). P = 7. ?- perrin(10, P). P = 17. ?- perrin(1000, X). X = 132868931340606743531841660195968328786671571417270282290475384294333707916597496057995813009306073093686467272648435293125. ================================================================================ 5. 4 points. Define the predicate maximum(list, integer) which succeeds if 'integer' is the maximal element of the list of integers List. ?- maximum([1,2,3,4,2,-1,4],Max). Max=4 ; false ?- maximum([],Max). false ================================================================================ 6. 4 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 the 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 ================================================================================ 7. 6 points. In a binary tree, all keys are assumed to be positive integers. Write a predicate which collects all even keys the tree, using difference lists. You can represent binary tree as a structure tree(left,key,right) or tree(left,key), where left and right are binary trees and key is the key. Leaves of the tree are just keys. Sample runs: ?- collect_even_keys(tree(tree(tree(1,2,3),4),5,tree(4,3,tree(2,1,0))),L). L = [4, 2, 4, 2, 0] ; false. ?- collect_even_keys(tree(tree(tree(1,2),3),4,tree(5,4,tree(3,2,1))),L). L = [2, 4, 4, 2] ; false. ?- collect_even_keys(tree(tree(tree(1,3,5),7),9,tree(11,13,tree(15,17,19))),L). L = [] ; false. ?- collect_even_keys(tree(tree(tree(4,6,tree(7,7,8)),9),10,tree(tree(tree(11,11),12,13),14,tree(15,16,18))),L). L = [4, 6, 8, 10, 12, 14, 16, 18] ; false. ================================================================================ 8. 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. The predicate 'integer' is a Prolog built-in predicate. 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.