Re: [eclipse-clp-users] Floundering case

From: Joachim Schimpf <jschimpf_at_...311...>
Date: Sun, 05 Jul 2015 14:32:02 +0100
On 27/06/15 01:16, Edgaonkar, Shrirang wrote:
>
> Lets say we have a function in java
>
> mid(right(left(InputStr,8),5),2,2) = "AB"
>
> Find the possible value of InputStr.
>
> So mid(right(left(InputStr,8),5),2,2) = "AB" means STR1 could be "RAB"
>
> but right(left(InputStr,8),5) cannot be "RAB" but it has to be atleast "RABRA" keeping "AB" always at position 2,2.
>
> again left(InputStr,8) could be atleast "RABRARAN". So InputStr is  "RABRARAN".
>
> So if use the above expression on  "RABRARAN" I should get "AB" again.
>
> Here the alphabets except the original "AB" can be anything random.
>
> This is just the tip of the iceberg.I can get any search java expressions to solve.
 > I strongly believe Eclipse can solve this problem for me.


It seems you want to reason about strings and their length.
Because you want to be able to

   - represent strings of unknown length
   - represent strings whose characters are not all known
   - want to use Unicode

I recommend that you use character code lists (i.e. lists of integers
such as created by string_list/3) to represent your "strings".


If you do this, then a simple way to implement your relations would be

left(Xs,N,Ls) :- length(Ls,N), append(Ls,_,Xs).

right(Xs,N,Rs) :- length(Rs,N), append(_,Rs,Xs).

mid(Xs,P,N,Ms) :- P1 is P-1, length(Ls,P1), length(Ms,N),
                   append(Ls,Ms,LsMs), append(LsMs,_,Xs).


With those, you can already solve some queries, like

?- S1=[a,b,c,d,e,f,g,h,i], left(S1,8,S2), right(S2,5,S3), mid(S3,2,2,S4).
S1 = [a,b,c,d,e,f,g,h,i]
S2 = [a,b,c,d,e,f,g,h]
S3 = [d,e,f,g,h]
S4 = [e,f]
Yes (0.00s cpu, solution 1, maybe more)

and even more general(and differently ordered) ones such as:

?- mid(S3,2,2,S4), right(S2,5,S3), left(S1,8,S2).
S3 = [_631,_633,_635,_647,_649]
S4 = [_633,_635]
S2 = [_652,_656,_660,_631,_633,_635,_647,_649]
S1 = [_652,_656,_660,_631,_633,_635,_647,_649|_665]
Yes (0.00s cpu, solution 1, maybe more)


However, this is a plain Prolog solution.  There is no separation
between constraints and search (the left/right/mid predicates do both).
More complex queries may therefore run inefficiently, and not every
goal ordering will work.


For more flexibility, try the file list_constraints.ecl that I have
uploaded to http://eclipseclp.org/wiki/Examples/ConstraintsOnLists

It contains constraint versions of length/2 and append/3.  These
are real constraints, which delay instead of making choices,
propagate changes in the list skeletons, and work together with
lib(ic) integer variables for reasoning about list lengths.

Based on those, you can formulate more general conditions, e.g.

?- len(S1,N1), N1#=<9, mid(S3,P,2,S4), right(S2,N,S3), left(S1,8,S2).
S1 = [_1801,_1805,_2034,_2137,_2218,_2299,_2380,_2461|_2692]
N1 = N1{[8,9]}
S3 = [_1385,_1389|_1440]
P = P{1..1.0Inf}
S4 = [_1135,_1137]
S2 = [_1801,_1805,_2034,_2137,_2218,_2299,_2380,_2461]
N = N{2..8}
There are 11 delayed goals.
Yes (0.00s cpu)

[Note that this is not a concrete solution yet, because there
are still delayed goals!]

You would then follow these constraints with a search phase,
where you generate concrete instantiations for the lengths (using
labeling/1 for example) and the lists (using length/2 for example)
to find all valid solutions.


-- Joachim
Received on Sun Jul 05 2015 - 13:32:12 CEST

This archive was generated by hypermail 2.2.0 : Mon Jul 09 2018 - 02:05:30 CEST