Week 2: Exercises

1. Second Last

Write a predicate second_last(X, L) that is true if X is the next-to-last element of L.

2. Next To

Write a predicate next_to(X, Y, L) that is true if elements X and Y appear in L, with Y immediately after X.

3. Even Length

Write a predicate even_length(L) that is true if the length of L is an even integer.

4. Same Length

Write a predicate same_length(L, M) that is true if L and M have the same length.

5. Longer

Write a predicate longer(L, M) that is true if L is longer than M.

6. Double Length

Write a predicate double_length(L, M) that is true if L is twice as long as M.

7. All Same

Write a predicate all_same(L) that is true if all elements of L are identical.

8. Reverse

Write a predicate reverse(L, M) that is true if L and M contain the same elements in reverse order.

9. Rotate

When we rotate a list one element to the right, the last element moves to the first position and all other elements shift rightward.

Write a predicate rotate(L, M) that is true if M is L rotated one element to the right (or, equivalently, L is M rotated one element to the left).

10. Select

Write a predicate select(X, L, M) that is true if X can be removed from L to make M. Equivalently, select(X, L, M) is true if X can be inserted anywhere in M to make L.

11. Select, Extended

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.

12. Acyclic Directed Graph

Consider this acyclic directed graph:

We can write a Prolog predicate representing adjacency between vertices:

edge(a, b).
edge(a, e).
edge(b, c).
edge(b, f).
edge(e, d).
edge(e, f).
edge(f, c).
edge(g, d).
edge(g, h).
edge(h, f).

Write a predicate path(V, W, L) that is true if L is a list of vertices along a path from V to W.

13. Edge-List Representation

Another way to represent a graph in Prolog is as a list of edges. For example, we can represent the graph above by this term:

G = [ [a, b], [a, e], [b, c], [b, f], [e, d],
      [e, f], [f, c], [g, d], [g, h], [h, f] ].

Write a predicate path(G, V, W, L) that is true if L is a list of vertices along a path from V to W in the graph G.

14. Cyclic Directed Graph

Let's modify the graph from the previous exercise by adding an edge from f back to a, so that the graph is now cyclic:

G = [ [a, b], [a, e], [b, c], [b, f], [e, d],
      [e, f], [f, c], [g, d], [g, h], [h, f],
      [f, a] ].

Write a predicate path(G, V, W, L) that is true if L is a list of vertices along a path from V to W in G, such that your predicate can always find all paths between given vertices V and W.