Write a predicate merge_sort(L, S) that sorts a list L of integers. Use a merge sort.
Write a predicate quicksort(L, S) that sorts a list L of integers. Use a quicksort. Use the first element of L as the pivot element.
Suppose that we represent natural numbers using structures: 0 = z, 1 = s(z), 2 = s(s(z)) and so on.
Write a predicate mul(?I, ?J, ?K) that is true if I · J = K, where I, J, and K have this numeric representation.
Using maplist(), write a predicate all_same(L) that is true if all elements of L are identical.
We can represent a matrix as a list of lists of floating-point numbers.
Write a predicate that tests whether a matrix has dimensions N x N, for a given N. Also write predicates that can calculate the following:
the zero matrix of a given size
the sum of two matrices
the first column of a matrix (a vector)
the identity matrix of a given size
the transpose of a matrix
the product of two matrices
All predicates should work in any direction.
Write a predicate digits(?L, ?N) that converts a list of digits (e.g. [3, 4, 5]) to an integer (e.g. 345).Use foldl().
Write predicate rev(?L, ?R) that is true if L is the reverse of R. Your predicate should run in linear time. Use foldl().
Write a predicate undirected(+G) that takes a graph G in adjacency list representation, and succeeds if G is undirected, i.e. for every edge from V to W there is a corresponding edge from W to V. For example, this graph is undirected:
G = [a -> [b, c], b -> [a], c -> [a]]
There are three coins on a table. Initially the first two coins are heads up, and the third is tails up:
H H T
We would like to make three coin flips and end up in a state where the three coins are either all heads up or all tails up.
Write a Prolog program that can determine all possible solutions.
A monkey is standing in a room at position A. There is a box at position B. A bunch of bananas are hanging from the ceiling at position C.
The monkey may take the following actions:
go(P) – go to position P (where P is one of the atoms a, b, or c)
push(P) – push the box (which must be at the monkey's current position) to position P
climb_on – climb onto the box (which must be at the monkey's current position)
climb_off – climb off the box (only if the monkey is currently on the box)
grab – grab the bananas (only if the monkey is on the box under the bananas)
The monkey would like to eat the bananas. Write a Prolog program that can generate all possible solutions, in increasing order of length. A solution is a list of actions to reach the goal.
11. Rectangles
Suppose that we have a set of rectangles, each with a given width and height. We want to know whether they can be packed into a rectangle R with a given width and height and depth. The rectangles may not be rotated.
We will represent a rectangle
as a structure rect(Width,
Height).
Write a predicate pack(L,
R,
Positions) that is true if the
rectangles
in list L can be packed into the rectangle R at the given list of
positions. A rectangle's position pos(X, Y) is
the position of its upper-left corner relative to the upper-left
corner of rectangle R.
Modify
your solution to the previous exercise so that the rectangles
in list L may be rotated by 90 degrees as they are packed into R. Now
each position should have the form pos(X, Y, R),
where R
= rot if
the rectangle has been rotated by 90 degrees, otherwise R
= not.