Write a predicate select(X, L, Y, M)
that is true if L and M are identical except (possibly) for a single
element, which is X
in L and is Y in M.
We may represent a dictionary in Prolog using a list of pairs:
D = [ p(red, 10), p(green, 20), p(blue, 30), p(orange, 40) ].
Write a predicate lookup(D, K, V) that succeeds if D is
a dictionary and K and V are a key-value pair in the dictionary.
Suppose that Prolog did not have built-in integers or lists.
a) Invent a way to represent natural numbers using structures.
b) Write a predicate add(I, J, K)
that is true if I + J = K, where I, J, and K are structures
representing integers in your representation.
c) Write a predicate le(I, J) that is
true if I ≤ J.
d) If Prolog had lists but not structures, could you represent natural numbers in some other way?
Write a predicate permutation(L, M)
that is true if the list L is a permutation of M.
Write a predicate combination(L, N, M)
that is true if M is a combination
of N elements of L, i.e. a subset of size N that has its elements in
the same order as in L. Elements
in M should appear in the same order as in L.
A student
walking up the stairs at our faculty may go up 1, 2, or 3 stairs with
each step they take. Write a predicate stairs(N, L) that
succeeds if N is the total number of stairs, and L is a list of steps
that a student may take to walk up the stairs. (In other words, L is
a list of numbers in the range 1..3 that add up to N.) Your predicate
should be able to efficiently generate all possible lists L for any
given N.
Write a
predicate change(N, L) that succeeds if N is a price in
Czech crowns and L is a list of Czech coins that sum up to N. The
coins may appear in any order: for example, change(6, [1, 5])
and change(6, [5, 1]) will both succeed. Your predicate
should be able to efficiently generate all possible lists L for any
N.
Extending
the previous exercise, write a predicate change2(N, L)
that is like change(), but in which the coins in L always appear in
non-decreasing order.
In Prolog, we may use a structure p(X, Y)
to represent the point (X, Y), where X and Y are floating-point
numbers. Also, we may use a structure line(A, B, C) to
represent the line with equation Ax + By = C.
Write a predicate intersect(L, M, P)
that is true if the lines L and M intersect at the point P. For
example:
?- intersect(line(1, -1, 0), line(1, 0, 1), P). P = p(1.0,1.0). ?- intersect(line(1, -1, 0), line(1, -1, 10), P). false.
Let segment(P, Q) represent a line
segment from points P to Q, where points are represented as p(X,
Y).
Write a predicate on_segment(S, R)
that is true if point R lies on the line segment S. For example:
?- on_segment(segment(p(0, 0), p(5, 5)), p(3, 3)). true. ?- on_segment(segment(p(0, 0), p(5, 5)), p(3, 4)). false. ?- on_segment(segment(p(0, 0), p(5, 5)), p(6, 6)). false.
Continuing the previous exercise, write a
predicate intersect(S, T) that is true if the line
segments S and T intersect. For example:
?- intersect(segment(p(0, 0), p(5, 5)), segment(p(1, 1), p(6, 6))). true. ?- intersect(segment(p(0, 0), p(5, 5)), segment(p(1, 0), p(6, 5))). false.
Write a predicate colinear(L) if L is
a list of points that are colinear, where we represent a point as
p(X, Y).
We may represent a rectangle as rect(P, Q),
where P and Q are the upper-left and lower-right corners of the
rectangle, represented as points p(X, Y).
Write a predicate overlap(R, S, T)
that succeeds if the rectangles R and S overlap and their
intersection is the rectangle T.
We may represent a polynomial as a list of its coefficients. For example, the list [2.0, 3.0, 4.0] represents the polynomial 2x2 + 3x + 4.
Write a predicate eval(P, X, Y) that
succeeds if Y = P(X), where P is a polynomial represented as a list.
Continuing the previous exercise, we will
represent a point (X, Y) using a structure p(X, Y).
Write a predicate fit(P, N, L) that succeeds if P is a
polynomial of degree N that passes through all points in the list L.
Your predicate should be able to generate a polynomial of a given
degree that passes through a given set of points.
We may represent a dictionary in Prolog using a list of pairs:
D = [ p(red, 10), p(green, 20), p(blue, 30), p(orange, 40) ].
Write a predicate update(+D,
+K, +V, ?D1) that takes a dictionary D, a key K and a value V.
It should return a dictionary D1 that is like D, but in which the key
K has value V. If the key is not already present, it should be added.