Re: [eclipse-clp-users] How to expand domain of a variable

Hello!

I've just managed to solve my problem about finding if a given number
belongs to any of given intervals (not sure about query effectiveness
yet, but at the very list it merges overlapping intervals).

To get rid of expand the domain I track not what belongs to intervals,
but instead of what not belongs to intervals, and then revert the
result.
My program with example query:

:- lib(ic).

model(Intervals, Domain) :-
    MIN is 1, MAX is 100,
    InvN :: MIN..MAX,
    ( foreach([L, R], Intervals), param(InvN) do ::(InvN, L..R, 0) ),
    N :: MIN..MAX,
    get_domain(InvN, InvDomain),
    ::(N, InvDomain, 0),
    get_domain(N, Domain).

query(Domain, N, Result) :-
    (
        ::(N, Domain, 1),
        Result = "Yes", !
    ) ; (
            Result = "No"
        ).


[eclipse 1]: model([[10, 20], [15, 30], [40, 50]], Domain),
query(Domain, 1, A1), query(Domain, 10, A2), query(Domain, 35, A3).

Domain = [10 .. 30, 40 .. 50]
A1 = "No"
A2 = "Yes"
A3 = "No"
Yes (0.00s cpu)

Sergey.

On Sat, Nov 5, 2011 at 1:30 AM, Sergey Dymchenko <kit1980_at_gmail.com> wrote:
> Yes, I know how to solve the problem procedurally (and I saw solutions
> in different languages).
> It's not the task I need to do for purpose, I'm just wondering if
> implementing it in ECLiPSe can be easier than a in C++, for example.
> For instance, I was thinking that built-in constraint reasoning can
> help to merge overlapping intervals. But now I see that even
> A::1..10 or A::1..20.
> leaves several delayed goals and doesn't not just simplify to 1..20.
>
> And after having domain I was thinking using simply ECLiPSe constraint
> satisfaction
>
> But now I see that probably all this wasn't a good idea.
>
> Sergey.
>
>
> On Sat, Nov 5, 2011 at 1:01 AM, Matthew Skala <mskala_at_cs.utoronto.ca> wrote:
>> On Sat, 5 Nov 2011, Sergey Dymchenko wrote:
>>> interval - the task is just to say Yes or No. An answer to a query
>>> must be fast (definitely faster than just checking all intervals one
>>> by one).
>>>
>>> Can this problem be solved effectively in ECLiPSe, or it doesn't look
>>> as a good problem for CLP paradigm?
>>
>> If you're expanding the domains of variables other than by backtracking,
>> then what you're doing isn't the CLP paradigm but something else.  I'm not
>> even sure how expanding domains would be useful in solving this problem;
>> what was the algorithm you were hoping to implement that made use of that
>> operation?
>>
>> This problem could be solved by a standard interval-query data structure
>> like the "interval tree."  Wikipedia has a rather confusing article by
>> that name with references to standard textbooks; the texts would be a good
>> place to start.  It amounts to building a binary tree on the intervals and
>> then searching it - fairly standard intro data-structures stuff.  You
>> could certainly implement the data structure in ECLiPSe, but I think you'd
>> want to do that by basically procedural code written in ECLiPSe; I don't
>> think trying to express it as a constraint satisfaction problem per se
>> would be very convenient, though we can argue from theoretical principles
>> that it necessarily must be *possible*.
>> --
>> Matthew Skala
>> Postdoctoral Fellow, University of Manitoba
>> mskala_at_cs.umanitoba.ca
>>
>