Session 11: Difference Lists, Search Problems and left overs
My pen is at the bottom of a page,
Which, being finished, here the story ends;
'Tis to be wished it had been sooner done,
But stories somehow lengthen when begun.
Lord Byron
Difference lists
Roughly speaking, a difference list is a pair of open ended lists were the second list is the tail of the first list: e.g. [a,b,c|T]-T.
Like this we have immediate access to the tail of a list. This often improves efficiency of
predicates for list-processing (for instance for appending lists).
- Consider a predicate flatten(List,FlatList) where List can contain lists, and lists of lists,
and so on, and FlatList is a list containing all the atomic members, except the empty list,
of those lists.
E.g. ?- flatten([[1,2,3],[4,5,[6,7],8],[9]],FlatList). gives
FlatList=[1,2,3,4,5,6,7,8,9].
The 'normal'
version of this predicate looks as follows:
flatten([], []).
flatten(X, [X]) :-
atomic(X), X \== [].
flatten([H|T], L3) :-
flatten(H, L1), flatten(T, L2), append(L1, L2, L3).
This version is inefficient because of the many calls to append! Give a more efficient version with difference lists!
- In session 7 we discussed trees. Remember that a tree with root X, left-subtree L and right-subtree R was represented as a term t(L,X,R) (e.g. the term t(t(nil,a,nil),b,t(nil,c,nil)) represents a tree with elements a, b and c). In session 7 we also discussed a predicate to 'linearize' a tree, i.e. to collect all elements of a tree in a list (in the right order). We defined this predicate as follows:
lin(nil,[]).
lin(t(Left,Root,Right),Res) :-
lin(Left,L),
lin(Right,R),
conc(L,[Root|R],Res).
Now try to do this using difference lists.
Search problems
Missionaries and Canibals
3 missionaries and 3 cannibals are walking together through the
forest. They arrive at a river they have to cross, but there is only
one boat, and that boat can carry at most 2 people. Of course the boat
requires at least one person to cross the river. The main problem is
that if there are more cannibals than missionaries at any place, they
will eat the missionaries. - Write a program that finds a
strategy for the six people to cross the river without a missionary
being eaten.
- As usual it is important to think about a good
representation for the problem. In the end of session 9, we have
decided to use the following representation for a state:
t(M,C,B) where M (resp B) stands for the number of
missionaries (resp cannibals) on the start-shore and B stands for the
shore where the boat is (-1 for start-shore, 1 for
end-shore).
Water jugs
You need to get 8 liters of water from a river. You only have a 15
liters jug and a 16 liters jug. How can you obtain 8 liters using only
these two jugs (possible operations are: emptying a jug entirely,
filling a jug entirely and emptying one jug in the other)?
- Write a
Prolog program to solve this problem. Try to make sure that you always
find the shortest solution.
The knight's tour problem
The Knight's Tour is a chess-related problem that was first proposed by Euler. How can a knight move around an empty chessboard and touch each of the squares exactly once?
- Write a predicate apply_move(Pos,Size,NewPos) that takes as input a current position (=square) Pos and the size of the board and returns a possible new position. Take into account that a knight can only make L-shaped moves: one move consists of moving one square horizontally and two squares vertically or vice versa. For instance, for an 8x8 board and from a position K near the middle of the board, the knight can go to eight different new positions: 0 through 7 in the following figure:
- Write a predicate solve(Size,Solution) that takes the size of the board as input and finds a solution for the problem (you can restrict yourself to finding solutions that start at the top-left corner).
For a board of size 8 (= 8x8 board), a naive generate-and-test solution is already too slow. In such a naive generate-and-test solution, when deciding which new position to go to from a certain position, you probably select randomly one position from all possible new positions. However, there is a smart way to find a more efficient solution. To do so you have to follow a particular strategy when selecting the new position instead of selecting it randomly. Concretely, calculate for each possible new position the number of positions that it can reach and that have not been visited yet. Then select the new position for which this number is the smallest.
- First write a predicate nb_unvisited(CurrentPos,Size,Visited,N) which takes as input a position CurrentPos, the size of the board, a list with all positions already visited and outputs the number (N) of positions that can be reached from CurrentPos and that have not been visited yet.
- Finally, adapt the naive generate-and-test strategy such that it uses the above strategy for selecting the new position: always first select the new position for which the number N is smallest.
CLP(FD) problem : Organizing a party
You are organizing a large party. There will be N tables in
the room, with M chairs around each table. Guests are assigned numbers from
1 to MN. You need to assign each guest a table so that two conditions
are satisfied. First, some guests like each other and want to sit together:
you are given a set Likes of pairs of guests and for
every pair (i,j) in Likes,
guests i and j should be assigned the same table.
Second, some guests dislike each other and want to sit at different tables:
you are given a set DisLikes of pairs of
guests and for every pair (i,j) in DisLikes,
guests i and j should be assigned different tables.
Write a CLP-program that (if possible) finds such a seating arrangement.
You can use the predicate exactly/3, often very handy when
solving CLP-problems. This predicate checks (using CLP) whether an
integer occurs in a list of integers exactly N times.
exactly(_El, [], 0).
exactly(El, [H|List], N) :-
El #= H #<=> B,
N #= M+B,
exactly(El, List, M).
Some left over exercices
Session 4: sets
Lists are often used as a representation for sets. In this exercise we want to make a data abstraction for a set, using a
list as internal representation. Remark that in a list
an element could occur more than once, in a normal set this is not the case.
- Define the following predicates for a set:
empty_set(Set)
% returns an empty set, or check if the set is empty
% when the argument is instantiated.
add_to_set(Element, Set, NewSet) % add an element to a set
member_of_set(Element, Set) % true if the element is a member
delete_from_set(Element, Set, NewSet)
% delete the element from the set if it occurs, otherwise
% the new set is unchanged
- Test the code above with some queries and little programs. Example:
test_set(Set):-
empty_set(Empty_set),
add_to_set(a, Empty_set, Set1),
add_to_set(b, Set1, Set2),
delete_from_set(a, Set2, Set).
- Now define the following predicates:
union_set(Set1, Set2, Union)
intersect_sets(Set1, Set2, Intersection)
union_list_of_sets(Sets, Union)
% The first argument contains a list of sets
% of which the union has to be computed.
difference_set(Set1, Set2, Difference)
% Difference contains all elements from Set1 not a member of Set2.
Session 6: Accumulators
In session2, we have written a predicate for computing fibonacci-numbers
(the predicate fibo/2 takes as a first argument an integer N
and returns as a second argument the Nth fibonacci-number). Remember
that the first two fibonacci numbers are both 1 and that the Nth
fibonacci-number is the sum of the N-1th and the N-2th
fibonacci-numbers. Also remember that the version of fibo/2
as given in the solution of session2 is very slow.
fibo(1,1).
fibo(2,1).
fibo(N,FibN):-
N>2,
Prev is N - 1,
Prev2 is N - 2,
fibo(Prev,FibPrev),
fibo(Prev2,FibPrev2),
FibN is FibPrev + FibPrev2.
Try to write a
faster version using accumulating parameters.