Week 4: Exercises

1. All Same

Using maplist(), write a predicate all_same(L) that is true if all elements of L are identical.

2. Matrices

We can represent a matrix as a list of lists of floating-point numbers.

Write the following predicates, all of which should work in any direction:

1. dims(M, I, J): true if M is a matrix with dimensions I x J

2. zero(M, I, J): true if M is the zero matrix of dimensions I x J

3. prod(X, M, N): N is the product of scalar X and matrix M

4. sum(M, N, P): P is the sum of matrices M and N

5. col(V, M): V (a vector) is the first column of matrix M

6. ident(K, M): M is the identity matrix of dimensions K x K

7. trans(M, N): N is the transpose of matrix M

3. Maplist

Implement the 3-argument predicate maplist(+P, ?L, ?M).

4. Combining Digits

Write a predicate to_int(L, N) that is true if L is a list of decimal digits in the number N. For example, to_int([3, 4, 5], 345) is true. Your predicate should work in both directions. Use an accumulator.

5. Reversing a List

Write a predicate rev(L, M) that is true if L is the reverse of M. Your predicate should work in both directions and should run in linear time. Hint: Use an accumulator.

6. Graph Edges

We may represent graphs in Prolog in adjacency-list representation. For example:

graph(G) :- G =
    [ a -> [b, e], b -> [c, f], c -> [a],
      d -> [], e -> [d, f], f -> [c],
      g -> [d, h], h -> [f] ].

Write a predicate edges(G, L) that succeeds if L is a list of all edges in the directed graph G, where an edge from V to W is represented as V -> W.

7. Undirected Check

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]]

8. Monkey and Bananas

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. States may be repeated in a solution.