Session 9: Sorting and Searching

Merge sort

write a predicate merge/3 that takes as first two arguments two lists where the elements are already sorted, and instantiates the third argument by merging the two lists in one, sorted list.
?-merge([3,5,8],[1,3,4,6,7,12,28],L).
L = [1,3,3,4,5,6,7,8,12,28]
write a predicate split/3 that takes as first argument a list, and split this list in two lists of equal length (if possible: if the length is odd, the second argument is one element longer than the third).
?-split([1,17,5,3,9],L,R).
L = [1, 5, 9]
R = [17, 3]
write a predicate mergesort/2 that takes as first argument a list and sort this list by splitting the list in two, sorting these two lists (with mergesort/2) and merging them back in one sorted list.
?- mergesort([23,2,1,3,1],L).
L = [1,1,2,3,23]
change your mergesort/2 predicate in a mergesortunique/2 predicate where all doubles occuring in the list are removed during the merging phase (you may assume that the two lists supplied as input-arguments do not contain doubles themselves).
?- mergesortunique([23,2,1,3,1],L).
L = [1,2,3,23]
Imagine that we are writing game playing software (e.g. for chess). Suppose that we already have a component that can determine all possible moves we can make for a given board position and what the result will be of each move (e.g. how many of our own pieces will be left and how many of the opponent). Suppose this information is represented as a list with elements of the form move(M,N1,N2). Here M is a certain move, N1 is the number of pieces left for us and N2 is the number left for our opponent.

Our task is to define a predicate evalsort/2 that takes as a first argument such a list and that returns as a second argument the sorted list. Sort the moves according to descending number of pieces for ourself (if the number of pieces for ourself is equal for some moves, then sort these moves according to ascending number of pieces for the opponent).
E.g. ?- evalsort([move(h2h4,5,6), move(c2d3,5,5), move(a6f6,6,6)],L).
results in L = [move(a6f6,6,6),move(c2d3,5,5),move(h2h4,5,6)]
Use mergesort as sorting procedure.

Searching: warm-up exercise

Recall the cube stacking problem. Remember that in session 5 we have written a predicate generate_and_test/2 that given a list with 4 cubes, returns a list of orientations giving a 'correct' stack.
generate_and_test([Cube1,Cube2,Cube3,Cube4],[O1,O2,O3,O4]) :- % generate a stack with the cubes in some orientation: basic_orientation(O1), % 3 possibilities for cube1 valid_orientation(O2), % 24 possibilities for cube2 valid_orientation(O3), % 24 possibilities for cube3 valid_orientation(O4), % 24 possibilities for cube4 % test the stack: test_stack([Cube1,Cube2,Cube3,Cube4],[O1,O2,O3,O4]). Given this generate_and_test/2 predicate, write a program to find 4 cubes that have only 2 different correct stacks. With "finding a cube" we mean finding figures for all six sides of the cube (as before you can use four possible figures: star, circle, rectangle and triangle).

Searching: missionaries and cannibals

For many problems we have a starting situation, a desired end situation and a set of rules that define which 'actions' we can perform in a given situation (remember the cube problem from session 5). We then have to find the sequence of actions that brings us from the starting situation to the end situation. Prolog makes it easy to write this kind of programs because backtracking (an essential part of searching) is hardwired into prolog. The general schema for such problems is as follows:

search(CurrentState,_Trace):-
     endstate(CurrentState), !,
     write_solution.

search(CurrentState,Trace):-
     generate_action(Action),
     valid_action(CurrentState,Action), 
     apply_action(Trace,CurrentState,Action,NewTrace,NewState),
     no_loops(NewState,Trace),
     search(NewState,NewTrace).

If we found the end state we stop searching and print the result. If we did not yet find a solution, we generate an action that is allowed and does not create a loop in the solution. We apply this action and then continue searching. Of course, if necessary we can backtrack over this action if we do not find a solution.

Now try to use this general idea in the following "Missionaries and cannibals" exercise:

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. You can choose the representation for the input and output of the problem yourself, but make sure that it is clear how to solve the problem given the output of your program.