Subsequence with a limit

Question

This is my problem:

Write a procedure distance(List, Nemptylist, SubList)/3 that checks if Sublist is a sublist of List with a distance of not more than N between items constraint (N is implemented as Nemptylist – a list of N anonymous variables). Assume that List is fully instantiated. Duplicate answers are allowed, as long as their number is finite.

For example, for N = 2 :

?- distance( [a,t,d,r,a,n,c,b,c] , [_,_], [a,b,c] ).
true

?- distance( [m,a,t,d,r,b,c,t] , [_,_] , [a,b,c] ).
false

?- distance([a, t, d, r, a, n, c, b], [_, _], [a, b, c]).
false

?- distance([c, c, c, a, c, c, c], [_, _], [a]).
true.

I've been sitting for hours, trying to solve this problem and eventually the examples above worked, but then i ran some tests and they failed.

My solution for now is as follows:

distance( L1 , L2 , [X]   ) :-
  member(X,L1) .
distance( L1 , L2 , [H|T] ) :-
  distance(L1,L2,T) ,
  append(Y,Z,L2) ,
  T=[Hs|Ts] ,
  append([H],Y,W) ,
  append(W,[Hs],R) ,
  sublist(R,L1) .

prefix(X,L) :- append(X, _, L).

suffix(X,L) :- append(_, X, L).

sublist(X,L) :- suffix(S,L) , prefix(X,S) .

when i try to run this test:

distance( [r,a,n,c,b,c],[],X) .

it fails due to run-time exceeded error.

I debugged it for hours and I'm really exhausted. Please help me finish this horrible assignment.

Answer 1

I see two major problems with your implementation:

1. You are unifying elements from NEmptyList with elements from List in the sublist(R, L1) goal. Future sublist goals might fail as NEmptyList will not unify with any N consecutive elements from List. If you want to use append (which is ok), you should build a new list of length at most N every time (see below).

2. You might validate different sequences from SubList with the same unique sequence from List. To demonstrate this, try this with your solution:

   ?- distance([a,a],[],[a,a,a,a,a,a]).
   true ;
   true ;
   false.
   

Here is a solution:

distance(_, _, []).
distance(List, NEmpty, Sublist):-
    append(_, Right, List),   % The first element can be anywhere in the list
    distance2(Right, NEmpty, Sublist).

distance2([X|_], _, [X]).
distance2(List, NEmpty, [X|Sublist]):-
    length(NEmpty, N),
    between(0, N, N1),
    length(AtMostNEmpty, N1), % Make a different list each time of length <N
    append([X|AtMostNEmpty], Right, List),
    distance2(Right, NEmpty, Sublist).