Homework 9

Problem 1. Prolog Predicates

Implement the following Prolog predicates:

1. last(E, L) is true if E is the last element of the list L.

   ?- last(X, [1, 2, 3]).
   X = 3 ;
   false.

2. notlast(S, L) is true if S is the list of all elements of the list L except for the last one (in the same order).

   notlast(X, [1, 2, 3]).
   X = [1, 2] ;
   false.
   

3. subseq(S, L) is true if S is a subsequence of adjacent elements of the list L.

   ?- subseq(X, [1, 2, 3]).
   X = [] ;
   X = [1] ;
   X = [1, 2] ;
   X = [2] ;
   X = [1, 2, 3] ;
   X = [2, 3] ;
   X = [3] ;
   false.
   

4. sublist(S, L) is true if S contains some subset of the elements of L, in the same order as in L.

   ?- sublist(X, [1, 2, 3]).
   X = [] ;
   X = [1] ;
   X = [1, 2] ;
   X = [1, 2, 3] ;
   X = [1, 3] ;
   X = [2] ;
   X = [2, 3] ;
   X = [3] ;
   false.
   

5. without(L, E, S) is true if S is L with E removed.

   ?- without([1, 2, 3], 2, X).
   X = [1, 3] ;
   false.
   
   ?- without(X, 2, [1, 3]).
   X = [2, 1, 3] ;
   X = [1, 2, 3] ;
   X = [1, 3, 2] ;
   false.
   
   ?- without([1, 2, 3], X, [1, 3]).
   X = 2 ;
   false.
   

6. permutation(L, M) is true if the list M is a permutation of the list L.

   permutation([1, 2, 3], X).
   X = [1, 2, 3] ;
   X = [2, 1, 3] ;
   X = [2, 3, 1] ;
   X = [1, 3, 2] ;
   X = [3, 1, 2] ;
   X = [3, 2, 1] ;
   false.
   

7. split(L, P, Q) that is true if the list L is split into the lists P and Q, keeping the order of the elements.

   ?- split([1,2,3,4], X, Y).
   X = [1, 2, 3, 4],
   Y = [] ;
   X = [1, 2, 3],
   Y = [4] ;
   X = [1, 2, 4],
   Y = [3] ;
   X = [1, 2],
   Y = [3, 4] ;
   X = [1, 3, 4],
   Y = [2] ;
   X = [1, 3],
   Y = [2, 4] ;
   X = [1, 4],
   Y = [2, 3] ;
   X = [1],
   Y = [2, 3, 4] ;
   X = [2, 3, 4],
   Y = [1] ;
   X = [2, 3],
   Y = [1, 4] ;
   X = [2, 4],
   Y = [1, 3] ;
   X = [2],
   Y = [1, 3, 4] ;
   X = [3, 4],
   Y = [1, 2] ;
   X = [3],
   Y = [1, 2, 4] ;
   X = [4],
   Y = [1, 2, 3] ;
   X = [],
   Y = [1, 2, 3, 4] ;
   false.
   
   split(X, [1, 2], [3, 4]).
   X = [1, 2, 3, 4] ;
   X = [1, 3, 2, 4] ;
   X = [1, 3, 4, 2] ;
   X = [3, 1, 2, 4] ;
   X = [3, 1, 4, 2] ;
   X = [3, 4, 1, 2] ;
   false.
   

You don't have to report the solutions in the same order as shown here. Report each solution only once!

If a query isn't shown here, you don't need to support it. For example, permutations(X, [1, 2, 3]) doesn't have to work.

Problem 2. Nim with Numbers

In the game of Nim, two players alternately remove marbles from a pile of marbles. In each turn, a player must remove at least one marble, and at most half the marbles. The following predicate tests whether it a move from X marbles to Y marbles is a legal move:

move(X,Y) :- X > Y, X =< 2 * Y.

A position consisting of two marbles is a winning position:

win(X) :- X=:=2.

Note that here we use integers, not lists of o, as we did in the lab.

We should be able to test whether any position is a winning position by adding the following clause:

win(X) :- move(X,Y), not(win(Y)).

However, that doesn't work.

?- win(4).
ERROR: Arguments are not sufficiently instantiated

Your job is to fix this, by a better implementation of move.

Submission Instructions

Submit two files, predicates.prolog and numbernim.prolog.

The grader will run queries such as

echo "set_prolog_flag(toplevel_print_options,  [quoted(true), portray(true)]). setof([X, Y], split([a,b,c,d,e], X, Y), S), length(S, N)." | swipl -q -s predicates.prolog 
echo "win(7)." | swipl -q -s numbernim.prolog