List exercise on prolog

Question

So my professor at campus asked us to solve this exercise but is kinda tough and I am trying for 2 days now. Anyway here it is:

I'm given a list for example [a,b,c,d,w,n,i,c,k,a,b,c,d,w] and on this list I have to find out if there is "suspect" sublist. The sublist is considered "suspect" if

1) the same sublist is in the beginning and at the end,

2) it contains "w",

3) its length is 5.

The list I give has a "suspect" sublist.

If there is a suspect sublist the program must return the sublist or if there is not the program must return [o,k].

Any ideas will be welcome, thanks a lot! (sorry if i posted something wrong)

EDIT

So after some help here is the asnwer:

 checkMessage1(L,SL):-
    suspiciousMessage1(L,SL).

checkMessage1(L,[o,k]):-
    not(suspiciousMessage1(L,SL)).

suspiciousMessage1(L,SL):-
    append(SL,Last,L),
    append(_,SL,Last),
    length(SL,5),
    member(w,SL).

`add(H,[H|T]). finderSuspect([H|T],Νumber,L1,L2,X):- Number>0 add(H,L1), Number1 is Number - 1, finderSuspect(T,Νumber1,L1,L2,X).` I try to "use" this to get the first five chars from the list... I know its **not** much — Nick Pampoukidis, Sep 02 '14 at 20:46

false · Answer 1 · 2014-09-02T21:13:04.647

2

This is a good example for using DCGs:

list_suspect(Xs, Ys) :-
   length(Ys, 5),
   phrase(( seq(Ys), ..., seq(Ys) ), Xs),
   phrase((...,"w",...), Ys).

... --> [] | [_], ... .

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

And here is a version using append/3 instead:

list_suspect(Xs, Ys) :-
    Ys = [_,_,_,_,_],
    append(Ys,Is, Xs),
    append(_, Ys, Is).
    append("w", _, W), % or: "w" = [C], W = [C|_]
    append(_, W, Ys).

Is it better readable? I think not.

The part with the [o,k] looks a bit unnatural to me, but it would be:

  list_ret(Xs, Ys) :-
     list_suspect(Xs, Ys).
  list_ret(Xs, Ys) :-
     \+ list_suspect(Xs,_),
     Ys = "ok".

edited Sep 02 '14 at 21:13

answered Sep 02 '14 at 20:28

false

10,264
13
101
209

bacause my level/experiense with prolog is terrible i dont really get the 1st code. Anyway on this code I try to get the first five chars but it give me an error. Here is the code: `add(H,[H|T]). finder([H|T],Νumber,L1):- Number>0, add(H,L1), Number1 is Number - 1, finder(T,Νumber1,L1).` Thanks a lot!! :) – Nick Pampoukidis Sep 02 '14 at 21:08
There are no numbers involved in this problem. It is just about lists. – false Sep 02 '14 at 21:16
See my 2nd version for a version without grammars. – false Sep 02 '14 at 21:17
So to get the first five letters what do i need to change? I use the "number" to give to this variable the number 5 in order to call the finder 5 times! – Nick Pampoukidis Sep 02 '14 at 21:17
There are too many misunderstandings here. Just look to the 2nd version above which does not use DCGs, but simply append – false Sep 02 '14 at 21:23

score 2 · Answer 2 · edited May 23 '17 at 12:25

2

one liner, using append/2

suspect(L, S) :-
    length(S, 5), append([S,_,S], L), memberchk(w, S) -> true ; S = [o,k].

edit as noted by false, the definition is buggy (lacks steadfastness ?): an amended rule

suspect(L, R) :-
    length(S, 5), append([S,_,S], L), memberchk(w, S) -> S = R ; R = [o,k].

edited May 23 '17 at 12:25

Community

1
1

answered Sep 02 '14 at 21:20

CapelliC

59,646
5
47
90

This method always gives true even when i dont put on my list the letter "w". Thanks :) – Nick Pampoukidis Sep 02 '14 at 21:45
@Nick: This definition succeeds for `suspect([a,b,c,d,w,n,i,c,k,a,b,c,d,w],[o,k])` ; but it should rather fail. – false Sep 03 '14 at 12:55

Nicholas Carey · Accepted Answer · 2014-09-08T20:25:50.233

Prolog is a declarative language: describe the solution in terms of constraints and let the engine do the work.

We can determine membership in a list thus:

contains( [X|Xs] , X ) :- ! .
contains( [_|Xs] , X ) :- contains(Xs,X) .

We can determine if a lists 1st element is identical to its last element using the built-in predicate append/3:

list_starts_and_ends_with_identical( [X|Xs] ) :-
  append( [X|_] , [X] , [X|Xs] )
  .

Or, if you'd rather roll your own:

list_starts_and_ends_with_identical( [A|Xs] ) :-
  list_ends_with( Xs , A )
  .

list_ends_with( [A]     , A ) .
list_ends_with( [B,C|D] , A ) :-
  list_ends_with( [C|D] , A )
  .

And we can enumerate sublists of the desired length like so:

sublist_of_length( Xs, L , Ys ) :- % to enumerate sublists of the desired length,
  integer(L) ,                     % - validate that the length is an integer, and
  L > 0 ,                          % - validate that the length is positive, and
  length(Ys,L) ,                   % - construct a list of unbound variables of the desired length, and
  sl(Ys,L)                         % - invoke the helper
  .                                %

sl( [X|Xs] , L ) :-                % to enumerate sublists,
  append( L , _ , [X|Xs] )         % - simply get the prefix of the desired length
  .                                %
sl( [_|Xs] , L ) :-                % on backtracking,
  sl( Xs , L )                     % - just recurse down on the tail of the list, discarding the first element.
  .

Then, all we have to do is assemble the parts:

suspect_sublist( Xs , L ) :-                 % the source list Xs contains a suspect sublist L, IF...
  sublist_of_length( Xs , 5 , L ) ,         % - L is a sublist of Xs having length 5, and
  contains( L , w ) ,                        % - L contains the atom 'w', and
  list_starts_and_ends_with_identical( L ) , % - the first element of L is identical to the last.
  .                                          % Easy!

List exercise on prolog

3 Answers3