ASSIGNMENT 2. Due January 24. ============================= 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. 5 points (a) Compute E\theta, where E=f(x,f(x,b,y),g(a,z)) and \theta= {x -> y, y -> g(a,z), z -> x\}. (b) Compute \theta\sigma, where \theta={x -> f(x), y -> z, z -> g(a,y,h(x))} and \sigma= {x -> y, z -> y, y -> h(y), w -> a}. (c) Compute \theta\theta, where \theta={x -> f(x), y -> z, z -> g(a,y,h(x))}. (d) Which of the following terms is more general than the others? f(g(x),g(y)), f(g(x),y), f(g(y),x), f(g(x),g(x)) Justify your answer by showing the corresponding substitutions. REMARK. A term t is more general than a term s if s is an instance of t, i.e., if there is a substitution \theta such that t\theta = s. ================================================================================ 2. 5 points Sketch the steps of the unification algorithm discussed in the class on the pairs of terms below: a) f(a,x,g(y)) and f(z,y,x) b) f(x,y,z,w) and f(f(u,u),f(x,x),f(y,y),f(z,z)) Here f,g,a,b,c,d are function symbols, x,y,z,u,w are variables. ================================================================================ 3. 6 points Implement the predicate occurs(Var, Term) that succeeds if the Prolog variable Var occurs in the Prolog term Term, and fails otherwise. Hint 1. You can use var(term) to check whether term is a Prolog variable. Hint 2. You can use var1 == var2 to check whether 'var1' and 'var2' are identical. Hint 3. You may want to use the univ predicate =.. to decompose a term into its functor and argument list to check for the occurrence of Var in the arguments. Sample runs: ?- occurs(X, f(X)). true. ?- occurs(X, f(Y)). false. ?- occurs(X, f(a,g(b,h(X,c),d))). true. ?- occurs(X, X). true. ?- occurs(x, f(x)). false. ?- occurs(x, x). false. ?- occurs(x, f(X)). false. ================================================================================ 4. 8 points (a) Write a DCG that generates the language consisting of all the strings of length 5 built from the letters a, b, and c. Give also the Prolog program that corresponds to this DCG. (b) Write a DCG that generates the language consisting of all the strings of the form a^nb^n, n>0, i.e., the language consisting of the string ab, aabb, aaabbb, aaaabbbb,.... Give also the Prolog program that corresponds to this DCG. (c) Write a DCG that defines a parametrised nonterminal star(X) such that, for any atom a, star(a) accepts the regular language consisting of all strings of the following form: the empty string, a, aa, aaa, aaaa, .... Give also the Prolog program that corresponds to this DCG. ================================================================================ 5. 8 points Assume that the following facts are given about 1980 European Football Championship. They indicate the games played by the team in the group phase, third place play off, and the final. Each team name is followed by the number of goals they scored in that game. Group(1) and group(2) indicate the group numbers in which teams were seeded. Penalties in the third place game indicate the outcome of penalty shootout after the game ended with the draw. group_game(czechoslovakia, 0, west_germany , 1, group(1)). group_game(netherlands , 1, greece , 0, group(1)). group_game(west_germany , 3, netherlands , 1, group(1)). group_game(greece , 1, czechoslovakia, 3, group(1)). group_game(netherlands , 1, czechoslovakia, 1, group(1)). group_game(greece , 0, west_germany , 0, group(1)). group_game(belgium, 1, england, 1, group(2)). group_game(spain , 0, italy , 0, group(2)). group_game(belgium, 2, spain , 1, group(2)). group_game(england, 0, italy , 1, group(2)). group_game(spain , 1, england, 2, group(2)). group_game(italy , 0, belgium, 0, group(2)). third_place_game(czechoslovakia, 1, italy, 1, penalties(9,8)). final_game(belgium, 1, west_germany, 2). Your task is to write predicates that return aggregate data as described below: ---- (a) all_games_by_team(Team, Games) should return the list of all Games by Team played in the tournament. For instance, ?- all_games_by_team(england, Games). Games = [game(england, 0, italy, 1, group(2)), game(england, 1, belgium, 1, group(2)), game(england, 2, spain, 1, group(2))]. ?- all_games_by_team(italy, Games). Games = [game(italy, 0, belgium, 0, group(2)), game(italy, 0, spain, 0, group(2)), game(italy, 1, england, 0, group(2)), game(italy, 1, czechoslovakia, 1, penalties(8, 9), third_place)]. ?- all_games_by_team(west_germany, Games). Games = [game(west_germany, 3, netherlands, 1, group(1)), game(west_germany, 1, czechoslovakia, 0, group(1)), game(west_germany, 0, greece, 0, group(1)), game(west_germany, 2, belgium, 1, final)]. What does your program return if you ask, e.g., ?- all_games_by_team(austria, Games). ? --- (b) all_games_by_group(Group, Games) should return the list of all Games played in Group. For instance: ?- all_games_by_group(1, Games). Games = [game(czechoslovakia, 0, west_germany, 1, group(1)), game(netherlands, 1, greece, 0, group(1)), game(west_germany, 3, netherlands, 1, group(1)), game(greece, 1, czechoslovakia, 3, group(1)), game(netherlands, 1, czechoslovakia, 1, group(1)), game(greece, 0, west_germany, 0, group(1))]. What does your program return if you ask, e.g., ?- all_games_by_group(3, Games). ? --- (c) all_games_by_team_result(Team, Result, Games) should return the list of all Games of Team that ended with Result, where Result can be either won, lost, or drawn. For instance: ?- all_games_by_team_result(czechoslovakia, won, Games). Games = [game(czechoslovakia, 3, greece, 1, group(1))] ?- all_games_by_team_result(czechoslovakia, drawn, Games). Games = [game(czechoslovakia, 1, netherlands, 1, group(1)), game(czechoslovakia, 1, italy, 1, penalties(9, 8), third_place)]. ?- all_games_by_team_result(czechoslovakia, lost, Games). Games = [game(czechoslovakia, 0, west_germany, 1, group(1))] --- (d) all_games(Games) should return the list of all games played in the tournament. --- (e) Optional. (Worth of bonus 4 points.) Print group tables. For instance: ? print_table(2). Team G W D L GDiff P ------------------------------- Belgium 3 1 2 0 3-2 4 Italy 3 1 2 0 1-0 4 England 3 1 1 1 3-3 3 Spain 3 0 1 2 2-4 1 ================================================================================ 6. 8 points In crypto-arithmetic problems digits are represented by letters. Different letters stand for different digits. Different occurrences of the same letter denote the same digit. The problem is then represented as an arithmetic operation between words of these letters. The task is to find out which letter stands for which digit, so that the result of the given arithmetic operation is true. An example of crypto-arithemtic problem is D O N A L D + G E R A L D -------------- R O B E R T We consider only the problems with addition. The task is to write a ternary predicate solve_ca_problem(L1, L2, L3) that succeeds if the elements of L1 and L2 form summands and the elements of L3 form the result of a crypto- arithemtic problem L1 + L1 = L3. Sample runs: ?- solve_ca_problem([D,O,N,A,L,D], [G,E,R,A,L,D], [R,O,B,E,R,T]). D = 5, O = 2, N = 6, A = 4, L = 8, G = 1, E = 9, R = 7, B = 3, T = 0 ; false. ?- solve_ca_problem([S,E,N,D], [M,O,R,E], [M,O,N,E,Y]). S = 9, E = 5, N = 6, D = 7, M = 1, O = 0, R = 8, Y = 2 ; false. ?- solve_ca_problem([S,E,V,E,N], [E,I,G,H,T], [T,V,E,L,V,E]). S = 7, E = 5, V = 3, N = 4, I = 9, G = 6, H = 8, T = 1, L = 0 ; S = 4, E = 8, V = 3, N = 7, I = 9, G = 6, H = 5, T = 1, L = 0 ; false. What does your program return to the following queries? ?- solve_ca_problem([W,R,O,N,G], [W,R,O,N,G], [R,I,G,H,T]). ?- solve_ca_problem([O,N,E], [O,N,E], [T,W,O]). ?- solve_ca_problem([A,B,C], [D,E,F], [G,H,I]). ?- solve_ca_problem([D,O], [R,E], [M,I]), solve_ca_problem([F,A], [S,I], [L,A]). ?- solve_ca_problem([O,N,E], [F,O,U,R], [F,I,V,E]).