Integer constraints and difference of two lists

Question

I am trying to find a value score, which can be calculated imperatively from two equal length lists Xs, Ys as:

for i in len(Xs):
    if Xs[i] == Ys[i]:
        score++
    else:
        score--

So the idea is to basically check every element from left to right on both lists and increment score if those elements are the same, decrement score otherwise. For example:

score([1,2,3], [1,2,3]) == 3
score([1,2,3], [1,2,1]) == 1
score([1,2,3], [3,2,1]) == -1
score([1,2,3], [3,1,2]) == -3

I think I actually managed to write the program as:

score(Xs, Ys, C) ?=>
    Xs = [], Ys = [], C = 0.

score(Xs, Ys, C) =>
    Xs = [XH|XT],
    Ys = [YH|YT],
    if (XH #= YH) then
        C #= C1 + 1
    else
        C #= C1 - 1
    end,
    score(XT, YT, C1).

the code gives the correct results when I query the score:

score([1,2,3], [1,2,3], S).
    S = 3 ?;

score([1,2,3], [1,2,1], S).
    S = 1 ?;

score([1,2,3], [3,2,1], S).                                      
    S = -1 ?;

score([1,2,3], [3,1,2], S).                                      
    S = -3 ?;

However, when I try to generate the lists which produce the scores, the code only generates the identical list with score 3:

S :: -3..3, Ls = new_list(3), Ls :: 1..3, score([1,2,3], Ls, S), solve([Ls, S]).

S = 3
Ls = [1,2,3] ?;

no

I want to generate all the lists, corresponding to all the possible scores, I have a feeling that I have to modify the base case but I can't figure out how :)

EDIT: I also tried to do a tail-recursion type of solution, it again gives correct results when the scores are queried, but it can only generate the identical list.

score(Xs, Ys, C) ?=>
    score_helper(Xs, Ys, 0, C).

score_helper([], _, Cur, C) ?=>
    C = Cur.

score_helper(Xs, Ys, Cur, C) ?=>
    Xs = [XH|XT],
    Ys = [YH|YT],
    if (XH = YH) then
        score_helper(XT, YT, Cur+1, C)
    else
        score_helper(XT, YT, Cur-1, C)
    end.

Answer 1

If you are using constraint solver (such as cp, sat, etc) then simply using sum should do the job:

import cp. 

go ?=> 
  X=new_list(3),
  Y=new_list(3),
  X::1..3, 
  Y::1..3, 
  Z #= sum([cond(X[I] #= Y[I], 1,-1) : I in 1..3]),
  solve(X++Y),
  println([x=X,y=Y,z=Z]), 
  fail,
  nl.
go => true.

The main point is that one can use constraints (here X[I] #= Y[I]) inside the list comprehension.

Or is it a requirement that it should no use constraints?

Edit: Another CP approach is the following (using "Prolog" style which is supported by Picat v3. This use equivalence (#<=>) for the check:

go3 ?=>
  Y = [1,2,3],
  X = new_list(3),
  X :: 1..3,
  Score :: [-1,1],
  score3(X,Y,0,Score),
  solve(X ++ [Score]),
  println(x=X),
  println(score=Score),
  nl,
  fail,
  nl.
go3 => true.


score3([], [], Score,Score).
score3([XH|XT], [YH|YT], Score0, Score) :-
  (XH #= YH) #<=> (Score1 #= Score0 + 1),
  score3(XT, YT, Score1,Score).

One problem with your approach is the you mix constraint equality check (#=) with traditional equality (== and =) which might not give the expected results.

And here's yet another approach using the same principle but inside a foreach loop:

 go2 ?=>
   Y = [1,2,3],
   N = Y.len,
   X = new_list(N),
   X :: 1..max(Y),
   Scores = new_list(N),
   Scores :: [-1,1],
   foreach(I in 1..X.len)
      X[I] #= Y[I] #<=> Scores[I] #= 1
   end,
   Z #= sum(Scores),
   solve(X ++ Scores),
   println([x=X,y=Y,scores=Scores,z=Z]),
  fail,
  nl.
go2 => true.