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

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.



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  
 
 [ 3 post ] 

 Relevant Pages 

1. stream('file','c','seek ='x) problem

2. There is an 'U'|'X'|'W'|'Z'|'-' in an arithmetic operand

3. TIP #194: Procedures as Values via '''apply'''

4. ( 2.31.New operators: 'eq', 'ne', 'last', '..' ) ?

5. What means, e.g., ('';'/')"_

6. 'C'/'C++', ADA OPPORTUNITIES/Phoenix(Software Developer/Integration Test Engineer)

7. STRING 'make'/'remake'

8. kill '-SIGHUP', pgid -vs- kill 'SIGHUP', 0

9. question: 'A'..'k'

10. Z''''

11. 'with'ing and 'use'ing

 

 
Powered by phpBB® Forum Software