Week 5: Notes

Most topics from this week are covered in the Bratko text. Note that constraint logic programming is covered in ch. 7 of the 4th edition, and in ch. 14 of the 3rd edition.

Here's a page with more information about logical purity in Prolog, a subject we also discussed.

Here are the solutions we saw in the tutorial to some of this week's exercises:

Bidirectional Factorial

factorial(0, 1).

factorial(N, F) :-
    N #> 0, N #=< F, N1 #= N - 1, factorial(N1, F1), F #= N * F1.

Beethoven's Wig

wig(W, G, Y, B, R) :-
    L = [W, G, Y, B, R],
    L ins 1..4,
    all_distinct([G, Y, B, R]),
    G in 3..4,
    W #< 4,
    W #> 1,
    Y #< W,
    B #> Y, B #< G,
    R = 1.

Three Coins

flip(h, t).
flip(t, h).

% flip1(L, M) is true if we can flip a single coin to get from L to M.
flip1(L, M) :- flip(X, Y), select(X, L, Y, M).

% path(S, T, L) is true if L is a sequence of flips that lead from S to T.
path(S, S, [S]).
path(S, T, [S | L]) :- flip(S, S1), path(S1, T, L).

% Generate all sequences of 3 flips that lead to a state where all coins
% look the same.  We need to specify length(L, 4), since both
% the start and end states are included in the list.
coins_a(L) :- length(L, 4), path([h, h, t], [X, X, X], L).

% Generate all sequences that lead to a desired state, in increasing
% order of length.
coins_b(L) :- length(L, _), path([h, h, t], [X, X, X], L).

Wolf, Goat, Cabbage

% n = north, s = south
opp(n, s).
opp(s, n).

% A state [F, W, G, C] holds the positions of the farmer, wolf,
% goat and cabbage.

% A state is dangerous if wolf eats goat or goat eats cabbage.
dangerous([F, W, G, C]) :- dif(F, G), (W = G; G = C).

% cross(S, T) is true if we can transition from state S to T.
cross([F | L], [F1 | L1]) :-
    opp(F, F1),                       % farmer moves to opposite bank
    (L1 = L ; select(F, L, F1, L1)),  % someone optionally comes with him
    \+ dangerous([F1 | L1]).          % nobody gets eaten

% seq(S, T, L) is true if L is a sequence of states leading from S to T.
seq(S, S, [S]).
seq(S, T, [S | L]) :- cross(S, S1), seq(S1, T, L).

% Use iterative deepening to search for a solution.
solve :-
    length(L, _),
    seq([s, s, s, s], [n, n, n, n], L),
    maplist(writeln, L).