Wanted: Hints'n'Tips'n'Bits'n'Bobs
Author Message Wanted: Hints'n'Tips'n'Bits'n'Bobs

I'm having big trouble with a PROLOG program and seeing as how USENET
was created for the sharing of problems, I thought I would see if
anyone out there can help.

Shortened version of spec:

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.

Well, that's pretty much it. Any hints, tips and other gems of wisdom
will be greatly appreciated.

TIA.

David L.

Sat, 19 Oct 1996 19:10:07 GMT  Wanted: Hints'n'Tips'n'Bits'n'Bobs

Quote:

>Shortened version of spec:
> 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:

Perhaps you shouldn't have shortened the spec., because I don't understand
you.  Here's what I think you mean:
D : natural = 5                 {number of Doors}
G : natural = 5                 {number of Guards}
L : [1..D] -> Boolean :=     {state of Locks}
(1..D := True)              {initially all locked}

for i from 1 to G do
for j from 1 to D do L[j] xor:= j mod i = 0 od
od

Quote:
> 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.

That's a rather {*filter*} representation.  I tell my students
"YOU WILL LOSE MARKS if you use a list where a record would have been
appropriate".  In this case, the obvious representation is just a list
of 'locked'/'unlocked' atoms.  For example, a trace:
1:      [unlocked,unlocked,unlocked,unlocked,unlocked]
2:      [unlocked,  locked,unlocked,  locked,unlocked]
...
5:      [unlocked,  locked,  locked,unlocked,  locked]

One thing I note is that we can turn the loop inside out:

for j from 1 to D do
Lj := True
for i from 1 to G do if j mod i = 0 then Lj := not Lj fi od
L[j] := Lj
od

Another way of saying this is that
L[j] = #{i: 1..G | i divides j} is even
Since i > j implies i does not divide j, we can improve that to
L[j] = #{i: 1..min(G,j) | i divides j} is even.

This suggests a nice simple predicate dealing with integers.

divisor_count(J, G, Count) :-
% Count = #{I: 1..min(G,J) | I divides J}
( G > J -> Limit = J; Limit = G ),
divisor_count(J, 0, Limit, 0, Count).

divisor_count(J, I0, Limit, Count0, Count) :-
I1 is 1+I0,
(   I1 > Limit -> Count = Count0
;   J mod I1 =:= 0 -> Count1 is 1+Count0,
divisor_count(J, I1, Limit, Count1, Count)
;/* J mod I1 =\= 0 */
divisor_count(J, I1, Limit, Count0, Count)
).

Now we just build the list:

gaol(D, G, Doors) :-
length(Doors, D),           % can be omitted but a nice check
gaol(Doors, G, 0, D).

gaol([], _, D, D).
gaol([Door|Doors], G, D0, D) :-
D1 is 1+D0,
divisor_count(D1, G, Divisors),
(   Divisors mod 2 =:= 0 -> Door = locked
;/* Divisors mod 2 =\= 0 */ Door = unlocked
),
gaol(Doors, G, D1, D).

test(Doors) :-
gaol(5, 5, Doors).

That means we can construct the list in one pass.

If this was really important, I'd start looking at the mathematics a bit
more to see if we can calculate the lock states directly.

--

"C is quirky, flawed, and an enormous success."  -- Dennis M. Ritchie.

Mon, 28 Oct 1996 15:59:37 GMT  Wanted: Hints'n'Tips'n'Bits'n'Bobs

This sounds an awful lot like a homework problem.

Check your old Scientific Americans--this problem
was treated in a Mathematical Games column.  The
answer is simple: numbers with an odd number of
factors (i.e., square numbers) will remain.  No
Prolog program is necessary.

Now that you know the answer, go and write the
Prolog program yourself!

----------------------------------------------------------------
Peter Van Roy                      DEC Paris Research Laboratory

Sat, 09 Nov 1996 23:26:13 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages