CODEWITHSUNDEEP
listprolog
Nick Pampoukidis
Nick Pampoukidis

Reputation: 742

List exercise on prolog

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).

Upvotes: 3

Views: 624

Answers (3)

Nicholas Carey
Nicholas Carey

Reputation: 74267

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!

Upvotes: 2

CapelliC
CapelliC

Reputation: 60014

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].

Upvotes: 2

false
false

Reputation: 10102

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".

Upvotes: 2

Related Questions