Homework #4

CS 152 | Fall 2008 | Due Date: 2008-11-19 23:59

Part 1.

Implement a Prolog predicate 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. For example, 

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] ;

10 points

Part 2.

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.

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.

10 points

Part 3.

Write a Prolog program that solves the following puzzle.

A lawyer (1), a programmer (2), and a project manager (3) arrive at Transsylvania Station, and a hearse is ready to drive them to the castle of Baron von Frankenstein. Unfortunately, the hearse can only hold one passenger at a time. The lawyer and programmer cannot be left alone with each other, or the lawyer will sue the programmer. The programmer and the project manager cannot be left alone with each other, or the project manager will annoy the programmer. Your program should come up with a trip plan that brings everyone to the castle. 

Your trip plan should be a list of positions. A position is a list of three lists: the people at the station, the hearse, and the castle. (The hearse is chauffered by a headless creature that doesn't count as a person.) Adjacent positions should be compatible, i.e. obtained by either entering or leaving the hearse. Here is a part of a sample trip plan:

[[[1,2,3],[],[]], 
 [[1,3],[2],[]],
 [[1,3],[],[2]],
 ...
 [[],[],[1,2,3]]]

Note that multiple people can enter and leave the hearse at the same time. For example, [[1],[2],[3]] and [[1],[3],[2]] are compatible (and avoid the invalid position [[1],[],[2,3]]).

Implement a predicate tripplan(X) that yields the valid trip plans.

5 points extra credit if you can enumerate the solutions where the hearse can transport up to two people (who, of course, must get along.)

Tell the grader with a comment in your solution if you are doing that.

15 points

Part 4. (Do this or Part 5.)

Describe (a) one problem that you encountered when implementing part 2 and what you did to overcome it, (b) one problem that you encountered when implementing part 3 and what you did to overcome it.

5 points

Part 5. (Optional alternative to Part 4.)

Attend the talk CK-12 and Flexbooks and write a paragraph or two how the students and faculty in the CS department can help with this effort.

15 points

Submission Instructions

Make a zip file with name hw4_lastname_firstname.zip, substituting your own names (duh). The extension must be in lowercase. The file must contain files hw41.pl, hw42.pl, hw43.pl, hw44.txt/hw45.txt, with no subdirectories after unzipping. My grading script