/* * CS 60, Fall 2001, Assignment 10 * * Programming in Logic * * Due: Thur. Nov. 29 * */ /* * Part I. Complete the definitions of Prolog predicates that respond to * the following queries, made to the Prolog database in the following * ensure_loaded directive. This database defines the following * predicates: * * movie([Title, Year], Director, [... categories]) * * actress(Name, [Birth City, Birth State], Birthyear) * * actor(Name, [Birth City, Birth State], Birthyear) * * plays(Player, Role, [Title, Year]) * * Your predicate names must be exactly those given below, or your solutions * will not be able to pass the tests that will be applied in grading. * * Since the essence of the solutions is in your predicate definitions and * not the actual answers, we will provide the answers in test cases. * * In defining your predicates, remove the _ from the variables. These * are present for now so the compiler doesn't complain about singleton * variables, which are often the sign of an error, such as a spelling error. * */ /* * HOW TO RUN Prolog on Turing: * * Type * * prolog * * to the Unix prompt. Ignore the message about licensing. It has no effect. * * Consult your file for the first time with * * consult('a10.pl'). * * after the prolog prompt, which is :-. * * Note: The period is mandatory! * * After you consult the first time in one run, you can "reconsult" with * * the command * * rc. * * which is defined later for your convenience. */ :- ensure_loaded('/cs/cs60/assign/10/movies.pl'). /* * 1. directedBandits(Director) iff Director is the director of the movie * ['Bandits', 2001]. */ directedBandits(_Director) :- tbd. /* * 2. directedByBay(Movie) iff Movie is directed by 'Michael Bay'. */ directedByBay(_Movie) :- tbd. /* * 3. actressAfter1970(Actress) iff Actress was born after 1970. */ actressAfter1970(_Actress) :- tbd. /* * 4. player(Name, BirthPlace, Birthyear) iff either * actor(Name, BirthPlace, Birthyear) * or actress(Name, BirthPlace, Birthyear). */ player(_Name, _Birthplace, _Birthyear) :- tbd. /* * 5. bornInLondon(Player) iff Player was born in ['London', 'England']. */ bornInLondon(_Player) :- tbd. /* * 6. playerAndDirector(Player) iff Player is a player that directed * some movie. */ playerAndDirector(_Player) :- tbd. /* * 7. playedAndDirected(Player) iff Player is a player that directed a movie * in which he or she played. */ playedAndDirected(_Player) :- tbd. /* * 8. playedMultiple(Player) iff Player played in more than one movie. */ playedMultiple(_Player) :- tbd. /* * 9. playedInComedy(Player) iff Player played in a comedy. */ playedInComedy(_Player) :- tbd. /* * 10. playedNotDirected(Director) iff Director directed some movies, but * played in at least one movie he/she did not direct. */ playedNotDirected(_Director) :- tbd. /* * Part II. Use Prolog to provide a solver for a generalized version of * the game "Twenty-Four". In the original game, players view * a card with four numbers on it and try to make an arithmetic * combination of the numbers using the operators +, -, *, / * so that the result is 24. Each number must be used exactly * once. Each operator can be used any number of times. * * In our generalization of the game, the fixed number 24 is replaced * with a variable, the set of operators is specified in a list, and * the list of numbers can have any length, not just 4. (By definition, * no result can be made if the list is empty.) * * Define a 4-ary predicate solve such that * solve(Ops, Values, Result, Tree) * will solve for a syntax-tree Tree using operators Ops on the set Values * to give the value Result. For example, alluding to the original game * a dialog with Prolog would be: * * | ?- solve(['+', '*', '-'], [2, 3, 4, 5], 24, Tree). * * Tree = [*,[+,[-,3,2],5],4] * * meaning that we have found a solution Tree using operators +, *, and - on * that will combine with set of numbers [2, 3, 4, 5] to yield 24. * * Assume that the set of operators will always be a subset of * ['+', '*', '-', '/'] and that '/' denotes integer division. * * Below we provide some predicates that could be helpful in solving this * problem. Use recursion and back-tracking to do the work for you. */ solve(_Ops, _Values, _Result, _Tree) :- tbd. /* * member(X, L) is true iff X is a member of L. */ member(X, [X | _]). member(X, [_ | Y]) :- member(X, Y). /* * eval(Exp, Result) evaluates an expression tree Exp to produce result Result. */ eval(R, R) :- number(R). eval(['+', A, B], R) :- eval(A, AR), eval(B, BR), R is AR + BR. eval(['*', A, B], R) :- eval(A, AR), eval(B, BR), R is AR * BR. eval(['-', A, B], R) :- eval(A, AR), eval(B, BR), R is AR - BR. eval(['/', A, B], R) :- eval(A, AR), eval(B, BR), R is AR // BR. /* * Hint: Define split such that * * split(X, Y, Z) is true iff X is splittable into non-empty lists Y and Z. */ /* The following will be used for testing your answers. */ test(Name, Var, Query, Desired) :- setof(Var, Query, Ans), !, ( Ans == Desired -> write('*** test '), write(Name), write(' passed'), nl ; write('*** test '), write(Name), write(' failed'), nl, write(' desired was '), write(Desired), nl, write(' actual was '), write(Ans), nl ). test(Name, _Var, _Query, []) :- !, write('*** test '), write(Name), write(' passed'), nl. test(Name, _Var, _Query, _Desired) :- write('*** test '), write(Name), write(' failed'), nl, write(' no answer produced'), nl. test(1) :- test(1, D, directedBandits(D), ['Barry Levinson']). test(2) :- test(2, M, directedByBay(M), [['Armageddon',1998], ['Pearl Harbor',2001]]). test(3) :- test(3, A, actressAfter1970(A), ['Amanda Peet','Cameron Diaz','Drew Barrymore', 'Gwyneth Paltrow','Kate Beckinsale','Liv Tyler']). test(4) :- test(4, [N, B, Y], player(N, B, Y), [['Adam Garcia',['Wahroonga','New South Wales'],1973], ['Al Pacino',['South Bronx','New York'],1940], ['Alec Guinness',['London','England'],1914], ['Amanda Peet',['New York','New York'],1972], ['Ben Affleck',['Berkeley','California'],1972], ['Ben Stiller',['New York','New York'],1965], ['Billy Bob Thornton',['Hot Springs','Arkansas'],1955], ['Bruce Willis',['Idar-Oberstein','Germany'],1955], ['Cameron Diaz',['San Diego','California'],1972], ['Cate Blanchett',['Melbourne','Australia'],1969], ['David Arquette',['Winchester','Virginia'],1971], ['Drew Barrymore',['Culver City','California'],1975], ['Gary Oldman',['London','England'],1958], ['Glenn Close',['Greenwich','Connecticut'],1947], ['Gwyneth Paltrow',['Los Angeles','California'],1972], ['Harrison Ford',['Chicago','Illinois'],1942], ['Jack Black',['Hermosa Beach','California'],1969], ['Jason Alexander',['Newark','New Jersey'],1959], ['John Cusack',['Evanston','Illinois'],1966], ['John Leguizamo',['Bogota','Colombia'],1964], ['John Malkovich',['Christopher','Illinois'],1953], ['Jose Ferrer',['Santurce','Peurto Rico'],1909], ['Josh Hartnett',['San Francisco','California'],1978], ['Kate Beckinsale',['London','England'],1973], ['Kris Kristofferson',['Brownsville','Texas'],1936], ['Liv Tyler',['Portland','Maine'],1977], ['Martin Landau',['Brooklyn','NY'],1931], ['Matt Dillon',['New Rochelle','New York'],1964], ['Nicole Kidman',['Honolulu','Hiwaii'],1967], ['Sean Penn',['Santa Monica','California'],1960], ['Steve Zahn',['Marshall','Minnesota'],1968], ['Tom Everett Scott',['East Bridgewater','Massachussets'],1970], ['Tom Hanks',['Concord','California'],1956], ['Woody Allen',['Brooklyn','New York'],1935], ['Zsa Zsa Gabor',['Budapest','Hungary'],1916]]). test(5) :- test(5, L, bornInLondon(L), ['Alec Guinness','Gary Oldman','Kate Beckinsale']). test(6) :- test(6, P, playerAndDirector(P), ['Ben Stiller','Tom Hanks','Woody Allen']). test(7) :- test(7, P, playedAndDirected(P), ['Ben Stiller','Tom Hanks']). test(8) :- test(8, P, playedMultiple(P), ['Al Pacino','Ben Affleck','Ben Stiller','Billy Bob Thornton', 'Bruce Willis','Cameron Diaz','Cate Blanchett','Drew Barrymore', 'Gary Oldman','Glenn Close','Gwyneth Paltrow','Harrison Ford', 'Jack Black','John Cusack','Kate Beckinsale','Liv Tyler', 'Martin Landau','Matt Dillon','Nicole Kidman','Steve Zahn']). test(9) :- test(9, P, playedInComedy(P), ['Adam Garcia','Amanda Peet','Ben Stiller','Billy Bob Thornton', 'Bruce Willis','Cameron Diaz','Cate Blanchett','David Arquette', 'Drew Barrymore','Gary Oldman','Glenn Close','Gwyneth Paltrow', 'Jack Black','Jason Alexander','John Cusack','John Malkovich', 'Liv Tyler','Matt Dillon','Nicole Kidman','Sean Penn','Steve Zahn', 'Tom Everett Scott','Tom Hanks']). test(10) :- test(10, D, playedNotDirected(D), ['Ben Stiller']). test(11) :- test(11, Tree, solve(['+', '*', '-'], [2, 3, 4, 5], 24, Tree), [[*,2,[+,3,[+,4,5]]], [*,2,[+,3,[+,5,4]]], [*,2,[+,4,[+,3,5]]], [*,2,[+,4,[+,5,3]]], [*,2,[+,5,[+,3,4]]], [*,2,[+,5,[+,4,3]]], [*,2,[+,[+,3,4],5]], [*,2,[+,[+,3,5],4]], [*,2,[+,[+,4,3],5]], [*,2,[+,[+,4,5],3]], [*,2,[+,[+,5,3],4]], [*,2,[+,[+,5,4],3]], [*,4,[+,3,[-,5,2]]], [*,4,[+,5,[-,3,2]]], [*,4,[+,[-,3,2],5]], [*,4,[+,[-,5,2],3]], [*,4,[-,3,[-,2,5]]], [*,4,[-,5,[-,2,3]]], [*,4,[-,[+,3,5],2]], [*,4,[-,[+,5,3],2]], [*,[+,3,[+,4,5]],2], [*,[+,3,[+,5,4]],2], [*,[+,3,[-,5,2]],4], [*,[+,4,[+,3,5]],2], [*,[+,4,[+,5,3]],2], [*,[+,5,[+,3,4]],2], [*,[+,5,[+,4,3]],2], [*,[+,5,[-,3,2]],4], [*,[+,[+,3,4],5],2], [*,[+,[+,3,5],4],2], [*,[+,[+,4,3],5],2], [*,[+,[+,4,5],3],2], [*,[+,[+,5,3],4],2], [*,[+,[+,5,4],3],2], [*,[+,[-,3,2],5],4], [*,[+,[-,5,2],3],4], [*,[-,3,[-,2,5]],4], [*,[-,5,[-,2,3]],4], [*,[-,[+,3,5],2],4], [*,[-,[+,5,3],2],4]]). test(12) :- test(12, Tree, solve(['+'], [1, 1, 1, 1], 24, Tree), []). test(13) :- test(13, Tree, solve(['+', '*', '-'], [1, 2, 3, 4], 24, Tree), [[*,1,[*,2,[*,3,4]]], [*,1,[*,2,[*,4,3]]], [*,1,[*,3,[*,2,4]]], [*,1,[*,3,[*,4,2]]], [*,1,[*,4,[*,2,3]]], [*,1,[*,4,[*,3,2]]], [*,1,[*,[*,2,3],4]], [*,1,[*,[*,2,4],3]], [*,1,[*,[*,3,2],4]], [*,1,[*,[*,3,4],2]], [*,1,[*,[*,4,2],3]], [*,1,[*,[*,4,3],2]], [*,2,[*,1,[*,3,4]]], [*,2,[*,1,[*,4,3]]], [*,2,[*,3,[*,1,4]]], [*,2,[*,3,[*,4,1]]], [*,2,[*,4,[*,1,3]]], [*,2,[*,4,[*,3,1]]], [*,2,[*,[*,1,3],4]], [*,2,[*,[*,1,4],3]], [*,2,[*,[*,3,1],4]], [*,2,[*,[*,3,4],1]], [*,2,[*,[*,4,1],3]], [*,2,[*,[*,4,3],1]], [*,3,[*,1,[*,2,4]]], [*,3,[*,1,[*,4,2]]], [*,3,[*,2,[*,1,4]]], [*,3,[*,2,[*,4,1]]], [*,3,[*,4,[*,1,2]]], [*,3,[*,4,[*,2,1]]], [*,3,[*,[*,1,2],4]], [*,3,[*,[*,1,4],2]], [*,3,[*,[*,2,1],4]], [*,3,[*,[*,2,4],1]], [*,3,[*,[*,4,1],2]], [*,3,[*,[*,4,2],1]], [*,4,[*,1,[*,2,3]]], [*,4,[*,1,[*,3,2]]], [*,4,[*,2,[*,1,3]]], [*,4,[*,2,[*,3,1]]], [*,4,[*,3,[*,1,2]]], [*,4,[*,3,[*,2,1]]], [*,4,[*,[*,1,2],3]], [*,4,[*,[*,1,3],2]], [*,4,[*,[*,2,1],3]], [*,4,[*,[*,2,3],1]], [*,4,[*,[*,3,1],2]], [*,4,[*,[*,3,2],1]], [*,4,[+,1,[+,2,3]]], [*,4,[+,1,[+,3,2]]], [*,4,[+,2,[+,1,3]]], [*,4,[+,2,[+,3,1]]], [*,4,[+,3,[+,1,2]]], [*,4,[+,3,[+,2,1]]], [*,4,[+,[+,1,2],3]], [*,4,[+,[+,1,3],2]], [*,4,[+,[+,2,1],3]], [*,4,[+,[+,2,3],1]], [*,4,[+,[+,3,1],2]], [*,4,[+,[+,3,2],1]], [*,[*,1,2],[*,3,4]], [*,[*,1,2],[*,4,3]], [*,[*,1,3],[*,2,4]], [*,[*,1,3],[*,4,2]], [*,[*,1,4],[*,2,3]], [*,[*,1,4],[*,3,2]], [*,[*,1,[*,2,3]],4], [*,[*,1,[*,2,4]],3], [*,[*,1,[*,3,2]],4], [*,[*,1,[*,3,4]],2], [*,[*,1,[*,4,2]],3], [*,[*,1,[*,4,3]],2], [*,[*,2,1],[*,3,4]], [*,[*,2,1],[*,4,3]], [*,[*,2,3],[*,1,4]], [*,[*,2,3],[*,4,1]], [*,[*,2,4],[*,1,3]], [*,[*,2,4],[*,3,1]], [*,[*,2,[*,1,3]],4], [*,[*,2,[*,1,4]],3], [*,[*,2,[*,3,1]],4], [*,[*,2,[*,3,4]],1], [*,[*,2,[*,4,1]],3], [*,[*,2,[*,4,3]],1], [*,[*,3,1],[*,2,4]], [*,[*,3,1],[*,4,2]], [*,[*,3,2],[*,1,4]], [*,[*,3,2],[*,4,1]], [*,[*,3,4],[*,1,2]], [*,[*,3,4],[*,2,1]], [*,[*,3,[*,1,2]],4], [*,[*,3,[*,1,4]],2], [*,[*,3,[*,2,1]],4], [*,[*,3,[*,2,4]],1], [*,[*,3,[*,4,1]],2], [*,[*,3,[*,4,2]],1], [*,[*,4,1],[*,2,3]], [*,[*,4,1],[*,3,2]], [*,[*,4,2],[*,1,3]], [*,[*,4,2],[*,3,1]], [*,[*,4,3],[*,1,2]], [*,[*,4,3],[*,2,1]], [*,[*,4,[*,1,2]],3], [*,[*,4,[*,1,3]],2], [*,[*,4,[*,2,1]],3], [*,[*,4,[*,2,3]],1], [*,[*,4,[*,3,1]],2], [*,[*,4,[*,3,2]],1], [*,[*,[*,1,2],3],4], [*,[*,[*,1,2],4],3], [*,[*,[*,1,3],2],4], [*,[*,[*,1,3],4],2], [*,[*,[*,1,4],2],3], [*,[*,[*,1,4],3],2], [*,[*,[*,2,1],3],4], [*,[*,[*,2,1],4],3], [*,[*,[*,2,3],1],4], [*,[*,[*,2,3],4],1], [*,[*,[*,2,4],1],3], [*,[*,[*,2,4],3],1], [*,[*,[*,3,1],2],4], [*,[*,[*,3,1],4],2], [*,[*,[*,3,2],1],4], [*,[*,[*,3,2],4],1], [*,[*,[*,3,4],1],2], [*,[*,[*,3,4],2],1], [*,[*,[*,4,1],2],3], [*,[*,[*,4,1],3],2], [*,[*,[*,4,2],1],3], [*,[*,[*,4,2],3],1], [*,[*,[*,4,3],1],2], [*,[*,[*,4,3],2],1], [*,[+,1,3],[+,2,4]], [*,[+,1,3],[+,4,2]], [*,[+,1,[+,2,3]],4], [*,[+,1,[+,3,2]],4], [*,[+,2,4],[+,1,3]], [*,[+,2,4],[+,3,1]], [*,[+,2,[+,1,3]],4], [*,[+,2,[+,3,1]],4], [*,[+,3,1],[+,2,4]], [*,[+,3,1],[+,4,2]], [*,[+,3,[+,1,2]],4], [*,[+,3,[+,2,1]],4], [*,[+,4,2],[+,1,3]], [*,[+,4,2],[+,3,1]], [*,[+,[+,1,2],3],4], [*,[+,[+,1,3],2],4], [*,[+,[+,2,1],3],4], [*,[+,[+,2,3],1],4], [*,[+,[+,3,1],2],4], [*,[+,[+,3,2],1],4]]). tbd :- fail. /* test all solutions */ test :- test(_), fail; true. /* * Prolog Gotcha's to note: * * // is not a comment symbol. It means integer division. * * The two comment forms are: * * slash-star to star-slash * * percent to end-of-line * * Identifiers starting with upper-case are variables, unless they are in * single quotes '...' which may be treated as string quotes. * * Identifiers starting with lower-case are either constants or predicate * names. * * Do not use "...", which is a shorthand for the list of individual * characters inside the double quotes. * * Using arithmetic symbols such as +, *, -, / will not cause evaluation * unless within an expression the right-hand side of an 'is' expression. */ /* Use this to re-consult your answers, assuming they are in file a10.pl. */ rc :- consult('a10.pl').