(click your browser's refresh button to ensure that you have the most recent version)
University rules on integrity of scholarship will be strictly enforced. By completing this assignment, you implicitly agree to abide by the UCSD Policy on Integrity of Scholarship described beginning on page 62 of the Academic Regulations section (PDF) of the 2002-2003 General Catalog, in particular, "all academic work will be done by the student to whom it is assigned, without unauthorized aid of any kind."
You are expected to do your own work on this assignment; there are no group projects in this course. You may (and are encouraged to) engage in general discussions with your classmates regarding the assignment, but specific details of a solution, including the solution itself, must always be your own work. Incidents which violate the University's rules on integrity of scholarship will be taken seriously.
In addition to receiving a zero (0) on the assignment, students may also face other penalties, up to and including, expulsion from the University. Should you have any doubt about the moral and/or ethical implications of an activity associated with the completion of this assignment, please see the instructors.
Code for all programming assignments should be well documented. A working program with no comments will receive only partial credit. Documentation entails writing a description of each predicate as well as comments throughout the code to explain the program logic. Comments in Prolog begin with a percent sign (%) and are terminated by a newline/carriage return. It is understood that some of the exercises in this programming assignment require extremely little code and will not require extensive comments. Nevertheless, comments describing recursions and helper predicates are required.
While few programming assignments pretend to mimic the "real" world, they may, nevertheless, contain some of the ambiguity that exists outside the classroom. If, for example, an assignment is amenable to differing interpretations, such that more than one algorithm may implement a correct solution to the assignment, it is incumbent upon the programmer to document not only the functionality of the algorithm (and more broadly his/her interpretation of the program requirements), but to articulate clearly the reasoning behind a particular choice of solution.
The overall objective of this assignment is for you to gain some hands-on experience with problem solving using Prolog, using simple facts and rules, recursion, and database handling capabilities of the language.
The instructions for submission of your assignment may be found at the bottom of this page of this document. It is a good idea to start this assignment early; Prolog programming, while not inherently difficult, often seem somewhat foreign at first, particularly when it comes to recursion and list manipulation.
So as not to make the code overly long, it is not required that you deal with user errors: you can assume that the user always types valid commands (e.g., if a predicate is supposed to take an atom as argument, you do not have to check whether the argument is instead a list and throw an error). Note that the Prolog interpreter catches a good number of user errors anyway.
parent(john,ann).Note that some things are not specified in the database above (e.g., male(john)).
parent(jim,john).
parent(jim,keith).
parent(mary,ann).
parent(mary,sylvia).
parent(brian,sylvia).
male(keith).
male(jim).
female(sylvia).
female(ann).
male(brian).
Write a Prolog predicate uncle(X,Y) that is true if X is Y's uncle. Note that we are not considering uncles "by marriage", meaning that for X to be Y's uncle the two must be related by blood. For instance (user input is in red):
?- uncle(keith,ann).
Yes
?- uncle(ann,mary).
No
?- uncle(keith,X).
X = ann ;
No
?- uncle(john,ann).
No
?- uncle(X,Y).
X = keith
Y = ann ;
No
Write a Prolog predicate halfsister(X,Y) that is true if X is Y's half-sister. For instance (user input is in red):
?- halfsister(ann,sylvia).
Yes
?- halfsister(X,sylvia).
X=ann ;
No
?- halfsister(X,Y).
X=ann
X=sylvia ;
X=sylvia
X=ann ;
No
Write a Prolog predicate sublist(X,Y) that is true if list X is a sublist of list Y. A sublist is defined as the original list, in the same order, but in which some elements may have been removed. For instance (user input is in red):
?- sublist([a,b],[a,e,b,d,s,e]).
Yes
?- sublist([a,b],[a,e,e,f]).
No
?- sublist([a,b],[b,a]).
No
?- sublist([],[a,e,e,f]).
Yes
?- sublist([a],[]).
No
?- sublist(X,[a,b,c]).
X = [] ;
X = [a] ;
X = [a, b] ;
X = [a, b, c] ;
X = [a, c] ;
X = [b] ;
X = [b, c] ;
X = [c] ;
No
Write a Prolog predicate has_duplicates(X) that is true if list X contains duplicated elements (that is at least 2 copies of an element). For instance (user input is in red):
?- has_duplicates([a,e,b,d,s,e]).
Yes
?- has_duplicates([a,b,d,s,e]).
No
?- has_duplicates([]).
No
Hints:
Write a Prolog predicate has_triplicate(X) that is true if list X contains triplicated elements (that is at least 3 copies of an element). For instance (user input is in red):
?- has_triplicates([a,e,e,d,s,e]).
Yes
?- has_triplicates([a,a,b,e,b,s,s,e]).
No
?- has_triplicates([]).
No
Hints:
Write a Prolog predicate remove_third(X,Y) that is true if list Y is just list X with its third element removed. If X has no third element, then the predicate should fail. For instance (user input is in red):
?- remove_third([a,e,e,d,s,e],L).
L = [a,e,d,s,e] ;
No
?- remove_third([a,b],L).
No
Write a Prolog predicate remove_nth(N,X,Y) that is true if list Y is just list X with its Nth element removed. If X does not have an Nth element then the predicate should fail. You can assume that N is strictly greater than 0. For instance (user input is in red):
?- remove_nth(4,[a,e,e,d,s,e],L).
L = [a,e,e,s,e] ;
No
?- remove_nth(6,[a,b],L).
No
Write a Prolog predicate remove_every_other(X,Y) that is true if list Y is just list X with every other element removed (the two lists should have the same first element). For instance (user input is in red):
?- remove_every_other([a,e,e,d,s,e],L).
L = [a,e,s] ;
No
?- remove_every_other([a,e,e,d,s],L).
L = [a,e,s] ;
No
?- remove_every_other([],L).
L = [] ;
No
store(best_smoothies, [alan,john,mary],
[ smoothie(berry, [orange, blueberry, strawberry], 2),
smoothie(tropical, [orange, banana, mango, guava], 3),
smoothie(blue, [banana, blueberry], 3) ]).
store(all_smoothies, [keith,mary],
[ smoothie(pinacolada, [orange, pineapple, coconut], 2),
smoothie(green, [orange, banana, kiwi], 5),
smoothie(purple, [orange, blueberry, strawberry], 2),
smoothie(smooth, [orange, banana, mango],1) ]).
store(smoothies_galore, [heath,john,michelle],
[ smoothie(combo1, [strawberry, orange, banana], 2),
smoothie(combo2, [banana, orange], 5),
smoothie(combo3, [orange, peach, banana], 2),
smoothie(combo4, [guava, mango, papaya, orange],1),
smoothie(combo5, [grapefruit, banana, pear],1) ]).
The first store has three employees and sells three different smoothies, the second store has two employees and sells four different smoothies, and the third store has three employees and sells five different smoothies. You can assume that there are no duplicates (pineapple is not listed twice in any ingredient list, mary is not listed twice in any employee list, the same smoothie specification is not listed twice in any store menu, etc.). Given a database of smoothie store facts, the questions below have you write predicates that implement queries to the database.
Write a Prolog predicate more_than_four(X) that is true if store X has four or more smoothies on its menu. For instance:
?- more_than_four(best_smoothies).
No
?- more_than_four(X).
X = all_smoothies ;
X = smoothies_galore ;
No
Write a Prolog predicate exists(X) that is true if there is a store that sells a smoothie named X. For instance:
?- exists(combo1).
Yes
?- exists(slimy).
No
?- exists(X).
X = berry ;
X = tropical <enter>
Yes
Write a Prolog predicate ratio(X,R) that is true if there is a store named X, and if R is the ratio of the store's number of employees to the store's number of smoothies on the menu. For instance:
Hint?- ratio(all_smoothies,R).
R = 0.5 ;
No
?- ratio(Store,R).
Store = best_smoothies
R = 1 ;
Store = all_smoothies
R = 0.5 ;
Store = smoothies_galore
R = 0.6 ;
No
Write a Prolog predicate average(X,A) that is true if there is a store named X, and if A is the average price of the smoothies on the store's menu. For instance:
Hint?- average(best_smoothies,A).
A = 2.66667 ;
No
Write a Prolog predicate smoothies_in_store(X,L) that is true if there is a store named X, and if L is the list of smoothie names on the store's menu. For instance:
Hint?- smoothies_in_store(all_smoothies,L).
L = [pinacolada, green, purple, smooth] ;
No
?- smoothies_in_store(Store,L).
Store = best_smoothies
L = [berry, tropical, blue] ;
Store = all_smoothies
L = [pinacolada, green, purple, smooth] ;
Store = smoothies_galore
L = [combo1, combo2, combo3, combo4, combo5] ;
No
Write a Prolog predicate fruit_in_all_smoothies(X,F) that is true if there is a fruit F that is an ingredient of all smoothies on the menu of store X. For instance:
Hint?- fruit_in_all_smoothies(Store,orange).
Store = all_smoothies ;
No
?- find_smoothies(L,[banana,orange],[blueberry,mango]).
L = [all_smoothies, green, smoothies_galore, combo1, smoothies_galore, combo2, smoothies_galore, combo3] ;
No
The smoothie "green" sold in the "all_smoothies" store, and the smoothies "combo1" and "combo2" sold in the "smoothies_galore" store, are the only smoothies with both banana and orange and without any blueberries or mango, hence the result to the above query.
Note that the query should give the same results for all possible orders of fruits in lists D and U:
?- find_smoothies(L,[orange,banana],[mango,blueberry]).
L = [all_smoothies, green, smoothies_galore, combo1, smoothies_galore, combo2, smoothies_galore, combo3] ;
No
To ask for all smoothies that have mango, one can just type:
?- find_smoothies(L,[mango],[]).
L = [best_smoothies, tropical, all_smoothies, smooth, smoothies_galore, combo4] ;
No
To ask for all smoothies that have no banana:
?- find_smoothies(L,[],[banana]).
L = [best_smoothies, berry, all_smoothies, pinacolada, all_smoothies, purple, smoothies_galore, combo4] ;
No
Hints
Your functions/programs must compile and/or run on a UNIX ACS machine, as this is where the verification of your solutions will occur. While you may develop your code on any system, ensure that your code runs as expected on an ACS machine prior to submission. Code which does not compile and/or produce the desired results on the testing machine will receive little or no credit. You should test your code in the directories from which the tar file (see below) will be created, as this will approximate the environment used for grading the assignment.
Your answers to this assignment will be stored in separate files under a directory called <username>_cse130_pa2/. For instance, I would create a directory caller casanova_cse130_pa2. The directory hierarchy should appear as follows:
<username>_cse130_pa2/
problem1.prolog
problem2.prolog
problem3.prolog
problem4.prolog
For example, as indicated above, in the <username>_cse130_pa2 directory, you should have a file named problem1.prolog, which will contain the documented Prolog source code to implement the functions specified in Problem #1 of this assignment, a file named problem2.prolog, which will contain the documented Prolog source code to implement the functions specified in Problem #2, and so on.Assuming the directory hierarchy above, populated with the problem solutions as described, you should create a tar file called <username>_cse130_pa2.tar by running the tar command in the directory where the <username>_cse130_pa2 directory resides. If you don't know anything about tar, I strongly suggest you learn about it as it is very useful (the man page is rather lengthy, but you can find a more gentle introduction there). For example, in the directory containing the above directory, I would run the command
tar -cvf casanova_cse130_pa2.tar casanova_cse130_pa2
which would create the desired tar file (in this case, named casanova_cse130_pa2.tar) from the directory named casanova_cse130_pa2.
Once you've created the tar file containing all of your answers to the assignment questions, you will use the turnin program to submit this file for grading. Using the turnin program is straightforward. Assuming I am in the directory where I've created the casanova_cse130_pa2.tar file, I would simply run the turnin command as follows:
turnin -c cs130s -p pa2 casanova_cse130_pa2.tar
The turnin program will provide you with a confirmation of the submission process; make sure that the size of the file indicated by turnin matches the size of your tar file. See the ACS web page on turnin for more information on the operation of the program.