Write a predicate digits(L, B, N) that is true if L is a list of digits in base B whose value is N. For example, digits([3, 4, 5], 10, 345) is true. Use a left fold.
Write a predicate foldr(+P, ?L, ?A, ?R) that performs a right fold over the values in L. For example, foldl(P, [x, y, z], A, R) will apply
P(z, A, A1), P(y, A1, A2), P(x, A2, R).
Write a predicate dot(V, W, X) that is true if X is the dot product of vectors V and W, which must have the same dimension. Use a fold.
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.
Consider binary trees represented as nil (the empty tree) or as t(L, X, R), where L and R are left and right subtrees. Write a predicate height(?T, ?H) that is true if H is the height of the binary tree T. Recall that the height of a tree is defined as the maximal distance from the root to any leaf. Your predicate should be able to generate all possible trees of any height.
Write a predicate flatten(?T, ?L) that flattens a tree, producing a list of values in the tree. For any node t(L, X, R), the values in L should appear before X in the list, and the values in R should appear after X. What is the best-case and worst-case running time for your predicate for a tree with N nodes?
Write a predicate foldr_tree(+P, ?T, ?A, ?R) that performs a right fold of a predicate over all values in a tree.
Write a predicate insert(X, T, T1) that inserts a value X into a binary search tree T, producing a tree T1. If the value X is already in the tree T, then T1 should equal T.
Is it possible to delete values from a tree by running insert() backwards? Why or why not?
In this cryptarithmetic puzzle, every letter stands for a different digit:
A P P L E + G R A P E + P L U M =========== B A N A N A
Write a Prolog program that can find a solution to the puzzle.
A magic square is a square of size N x N that contains all integers from 1 .. N2 and in which every row, column and diagonal adds to the same value.
Write a Prolog predicate that can test whether a square is magical. When run backward, it should also be able to generate magic squares of a given size.
Write a predicate hamiltonian(+G, ?P) that takes an undirected graph in adjacency list representation and succeeds if P is a Hamiltonian path in G, i.e. a path that visits all vertices exactly once.
You could test your predicate on this graph:
graph(G) :- G = [ a -> [c, e], b -> [d, e], c -> [a, d, f],
d -> [b, c, e, f], e -> [b, d, f], f -> [c, d, e, g],
g -> [f] ]Write a predicate colorable(+G, +N) that takes an undirected graph in adjacency list representation and a positive integer N. The predicate should succeed if the graph is N-colorable, i.e. it is possible to assign one of N colors to each vertex in such a way that no adjacent vertices have the same color.
Write a predicate isomorphic(+G, +H) that takes two graphs in adjacency list representation and succeeds if the graphs are isomorphic.
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.
A monkey is standing in a room at position pos_a. There is a box at position pos_b. A bunch of bananas are hanging from the ceiling at position pos_c.
The monkey may take the following actions:
• go(P) – go to position P
• 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.
Write a higher-order predicate solve(+Move, +Start, +Goal) that can find the shortest path from a start state to an end state in any state space. Move(+S, ?T) should be a predicate that succeds if it's possible to move from state S to state T. Goal(+S) should be a predicate that's true if state S is a goal state.
Three missionaries and three cannibals wish to cross a river using a boat that can carry only two people. At no time may the cannibals outnumber the missionaries on either river bank, since then they would eat the missionaries. How can they cross? Write a Prolog program that can find the shortest solution.
A farmer is on the south bank of a river with a wolf, a goat, and a cabbage. He has a boat that can hold him plus any one of these three items. If the wolf and goat are left alone without the farmer, the wolf will eat the goat. If the goat and cabbage are left alone without the farmer, the goat will eat the cabbage. The wolf does not like cabbage.
How can the farmer cross with all of these possessions to the north bank? Write a Prolog program that can determine the shortest solution.
Three jugs have capacity 8, 5 and 3 liters. Initially the first jug is full of water, and the others are empty.
We can pour water between the jugs, but they have no markings of any sort, so we can pour between two jars only until one of them becomes full or empty.
What sequence of moves can we make so that the jugs will hold 4, 4, and 0 liters of water, respectively?
Write a Prolog program to find the shortest possible solution.
Four people wish to cross a river using a narrow bridge, which can hold only two people at a time. They have one torch and, because it's night, the bridge crossers must take the torch.
Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes, and D in 8 minutes. When two people cross the bridge together, they must move at the slower person's pace. Can they all get across the bridge if the torch lasts only 15 minutes? Write a Prolog program that can determine the answer.