Prolog Brain Teaser 
Author Message
 Prolog Brain Teaser

   With apologies to the many readers who will be familiar with
this little Prolog Puzzle which came to my notice some time ago.
I thought it was worth posting. It has  (to me at least) a pleasing but
non-obvious solution. Here goes!

You are given the standard definition of append/3

           append( [], L, L).
           append( [H|T], L, [H|T1]):- append( T, L, T1).

which can be used reversibly to append two lists and to generate sublists.

  The problem is this. Using this definition,  define append/4 which will
append 3 lists to form a 4th *AND* will work reversibly to generate all
sublist solutions without looping on backtracking.

  There are four obvious definitions but only one of them works. Try to
solve it first without testing on a Prolog system.

     Have fun.

     Duncan Lowes

P.S. Before I get flamed this is not my homework :-) :-)



Sun, 09 Aug 1992 02:27:06 GMT  
 Prolog Brain Teaser

Quote:

>  The problem is this. Using this definition,  define append/4 which will
>append 3 lists to form a 4th *AND* will work reversibly to generate all
>sublist solutions without looping on backtracking.

In Sepia one writes (in other Prologs with coroutining it is something similar)

delay append(A, _, C) if var(A), var(C).
append([], L, L).
append([X|L1], L2, [X|L3]) :-
        append(L1, L2, L3).

append(A, B, C, D) :-
        append(A, B, L1),
        append(L1, C, D).

I know you ment something else, but I just cannot resist :-)
The call to append/3 delays if both first and third arguments are
uninstantiated. I think it was Lee Naish who first mentioned this predicate.

It is interesting to note that this predicate does not run much slower
than the solution which does not use coroutining and defines
append/4 with several clauses. The reason is that the cost for
scheduling of suspended and woken append/3 calls in the former is balanced
by the list unifications in the head of append/4 in the latter.

--Micha Meier



Sun, 23 Aug 1992 16:29:31 GMT  
 Prolog Brain Teaser

Quote:

>append(A, B, C, D) :-
>    append(A, B, L1),
>    append(L1, C, D).

> I think it was Lee Naish who first mentioned this predicate.

Yes, to illustrate how easy it is to get reversible procedures when you
have a decent coroutining system.  As Ken Kahn (and others I'm sure) has
pointed out is actually rather more efficient to write it as follows,
so the elements of A are not scanned twice:

append3(A, B, C, D) :-
       append(B, C, BC),
       append(A, BC, D).

As Richard O'Keefe (I think, and others) has pointed out, we can now
reverse the two calls to append/3 to make it works forwards and
backwards without coroutines:

append3(A, B, C, D) :-
       append(A, BC, D),
       append(B, C, BC).

This is the best way to write it, but it does require a fair bit of
thought.  If you have coroutines you can be lazy and write it any way
you want - its got a very good chance of working in all modes which
result in a finite number of solutions.

        lee



Mon, 24 Aug 1992 09:24:18 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. squiral brain teaser

2. Another try at Homer's brain teaser

3. Another crack at Howard's brain teaser

4. APL brain teaser - generalising it

5. squiral brain teaser SPOILER:code

6. squiral brain teaser SPOILER:how it works

7. APL brain teaser

8. Brain Teaser

9. Brain Teaser

10. An off-topic brain teaser

11. brain teaser

12. Cobol Brain Teaser

 

 
Powered by phpBB® Forum Software