:- module(_, [guardians/3], [assertions, regtypes, nativeprops]).

%% guardians.pl --
%% AFSID           : $__Header$
%% Author          : Manuel Carro Li~nares
%% Created On      : Sun May  8 17:28:20 1994
%% Last Modified By: MCL
%% Last Modified On: Tue Jun  8 19:11:18 1999
%% Update Count    : 52
%% Status          : Correct

 %%  Prison guards are playing a game. The Nth guard turns the key in every
 %%  Nth cell door, either unlocking or locking the door. A simulated run
 %%  with five guards and five cells would appear thus:
 %%
 %%  1) Cells 1 2 3 4 5 unlocked
 %%  2) Cells 1 3 5 unlocked
 %%  3) Cells 1 5 unlocked
 %%  4) Cells 1 4 5 unlocked
 %%  5) Cells 1 4 unlocked
 %%  etc...
 %%
 %%  At the end of the 'game', the program must return a list of unlocked
 %%  Cells, given N Guards and M Cells.
 %%
 %%  The jail should be represented as a list of pairs, ordered by cell
 %%  number, in the form [State, Cell], where State is either locked or
 %%  unlocked. To construct an ordered list, Jail, of cells, the relation
 %%  make_cells(Cells,Start,State,Jail) should be used.

% ----------------------------------------------------------------------

:- entry guardians(A,B,C) : num * num * term.
:- pred guardians(A,B,C) : num * num * term.
guardians(NGuardians, NLocks, OpenCells):-
	guardians_(NGuardians, NLocks, OpenCells).

:- pred guardians_(A,B,C) : num * num * term => num * num * listnum.
guardians_(NGuardians, NLocks, OpenCells):-
        make_jail(1, NLocks, OpenJail),
        make_round(NGuardians, NLocks, OpenJail, Jail),
        extract(Jail, OpenCells).

:- pred make_round(A,B,C,D) : num * num * listcell * term => num * num * listcell * listcell.
make_round(0, _Locks, Jail, Jail).
make_round(Guardian, Locks, Jail, FinalJail):-
        Guardian > 0,
        cells_to_close(Guardian, Locks, To_Close),
        turn_key(To_Close, Jail, NewJail),
        NextGuardian is Guardian - 1,
        make_round(NextGuardian, Locks, NewJail, FinalJail).

:- pred make_jail(A,B,C) : num * num * term => num * num * listcell.
make_jail(Locks, Locks, [cell(Locks, closed)]).
make_jail(Current, Locks, [cell(Current, closed)|Cells]):-
        Current < Locks,
        NextCell is Current + 1,
        make_jail(NextCell, Locks, Cells).

:- pred turn_key(A, B, C) : listnum * listcell * term => listnum * listcell * listcell.
turn_key([], Jail, Jail).
turn_key([Curr|Turn], [cell(Curr, St)|Rest], [cell(Curr, NSt)|NewRest]):-
        change_state(St, NSt),
        turn_key(Turn, Rest, NewRest).
turn_key([Curr|Turn], [cell(Curr1, St)|Rest], [cell(Curr1, St)|NewRest]):-
        Curr \== Curr1,
        turn_key([Curr|Turn], Rest, NewRest).

change_state(open, closed).
change_state(closed, open).

:- pred cells_to_close(A,B,C) : num * num * term => num * num * listnum.
cells_to_close(Guardian, Locks, List):-
        cells_to_close_(Guardian, Guardian, Locks, List).

cells_to_close_(Current, _Guardian, Locks, []):- Current > Locks.
cells_to_close_(Current, Guardian, Locks, [Current|Rest]):-
        Current =< Locks,
        Next is Current + Guardian,
        cells_to_close_(Next, Guardian, Locks, Rest).

:- pred extract(A,B) : listcell * term => listcell * listnum.
extract([], []).
extract([cell(N, open)|Cells], [N|RestOpen]):-
        extract(Cells, RestOpen).
extract([cell(_N, closed)|Cells], RestOpen):-
        extract(Cells, RestOpen).

:- regtype cell/1.
cell(cell(N, St)) :- num(N), status(St).

:- regtype status/1.
status(open).
status(closed).

:- regtype listcell/1.
listcell([]).
listcell([X|Xs]) :- cell(X), listcell(Xs).

:- regtype listnum/1.
listnum([]).
listnum([X|Xs]) :- num(X), listnum(Xs).
