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

This fits your trace.

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.