If there is an overlap with starting position S
, we expect a conjunction of constraints so that all overlapping positions are covered. For example:
:- use_module(library(clpfd)).
overlap_at(As, Bs, S, ABs) :-
length(As, L),
L1 #= L - 1,
S in 0..L1,
overlap_at_(As, Bs, S, 0, ABs).
overlap_at_([], _, _, _, []).
overlap_at_([A|As], Bs, S, N0, [AB|ABs]) :-
overlap_here(Bs, [A|As], [AB|ABs], Conj),
S #= N0 #==> Conj,
S #> N0 #==> AB #= A,
N1 #= N0 + 1,
overlap_at_(As, Bs, S, N1, ABs).
overlap_here(_, [], _, 1) :- !.
overlap_here([], _, _, 1).
overlap_here([B|Bs], [A|As], [AB|ABs], (AB #= A + B #/\ Rest)) :-
overlap_here(Bs, As, ABs, Rest).
Notice how I describe a conjunction in overlap_here/4
.
Sample query:
?- overlap_at([0,1,1,1,1,0,1,1,1], [1,2,2], 3, ABs).
ABs = [0, 1, 1, 2, 3, 2, _G909, _G912, _G915],
_G909 in inf..sup,
_G912 in inf..sup,
_G915 in inf..sup.
This gives you a good chunk of the solution: All elements up to and including the overlap are instantiated as desired. The third argument can of course also be a variable: Try for example
?- overlap_at([0,1,1,1,1,0,1,1,1], [1,2,2], S, ABs),
indomain(S), writeln(ABs), false.
Which yields something like:
[1,3,3,_,_,_,_,_,_]
[0,2,3,3,_,_,_,_,_]
[0,1,2,3,3,_,_,_,_]
[0,1,1,2,3,2,_,_,_]
[0,1,1,1,2,2,3,_,_]
[0,1,1,1,1,1,3,3,_]
[0,1,1,1,1,0,2,3,3]
[0,1,1,1,1,0,1,2,3]
[0,1,1,1,1,0,1,1,2]
I leave the rest as an exercise: Trailing positions that are not affected by the overlap need to be made equal to elements of A
. Also, you may want to further restrict the possible positions of the overlap, which I have kept rather general.