Re: [eclipse-clp-users] Interesting problem from Google Code Jam

Sergey Dymchenko wrote:
> Hi!
> 
> There is an interesting problem from Google Code Jam:
> https://code.google.com/codejam/contest/dashboard?c=1128486#s=p2&a=2
> Essence of the problem: find minimum integer X such that Low <= X <=
> High and for given list of integers L either L[i] divides X or X
> divides L[i].
> This is very hard problem because of the possible limits: 1 <= Low <=
> High <= 10^16, size of L <= 10^4, each element of L <= 10^16.
> 
> I'm novice in constraint programming and here is my very naive solution:
> 
> :- lib(ic).
> 
> model(L, H, Notes, X) :-
>     X #>= L,
>     X #=< H,
> 
>     (foreach(Y, Notes), param(X) do
>         max(X, Y) #= B * min(X, Y),
>         B #> 0).
> 
> solve(L, H, Notes, X) :-
>     model(L, H, Notes, X),
>     indomain(X),
>     writeln(X).
> 
> It will work fast for solve(8, 16, [1, 20, 5, 2], X), but 30 seconds
> for solve(2, 1000000, [4, 1187, 310559, 3, 739, 7, 23, 19], X) and
> till the end of time for solve(2, 10000000000000000, [4, 1187, 310559,
> 3, 739, 7, 23, 19], X).

It scales a bit better if you replace indomain(X) by indomain(X,min)
(the reason being that larger areas of the search space - where
X is greater than some number - can be excluded in one step).

?- solve(2, 1000000, [4, 1187, 310559, 3, 739, 7, 23, 19], X).
No (0.21s cpu)
?- solve(2, 10000000, [4, 1187, 310559, 3, 739, 7, 23, 19], X).
No (1.87s cpu)
?- solve(2, 100000000, [4, 1187, 310559, 3, 739, 7, 23, 19], X).
No (9.61s cpu)
?- solve(2, 1000000000, [4, 1187, 310559, 3, 739, 7, 23, 19], X).
No (17.21s cpu)
?- solve(2, 10000000000, [4, 1187, 310559, 3, 739, 7, 23, 19], X).
... still waiting :(

> 
> Explanation and imperative solution for the problem can be found at
> https://code.google.com/codejam/contest/dashboard?c=1128486#s=a&a=2
> 
> Is this a good problem for constrained programming paradigm?
> Is it possible to write a fast enough declarative solution (which runs
> seconds for solve(2, 10000000000000000, [4, 1187, 310559, 3, 739, 7,
> 23, 19], X)) without introducing too much hints to the system?

Well, I guess 10^16 is not exactly a finite-domain solver's typical
idea of finiteness (I suppose they chose 10^16 because it's close to
the maximum you can represent precisely with a double float).

You could probably scale up by having a better constraint dealing
specifically with divisibility, but it's unlikely that you would
be competitive with a purpose-written algorithm.  That said, one
strength of the constraint programming paradigm is that you can
then take such an algorithm (which may use some variant of the
sieve of Eratostehenes), package it in the form of a constraint,
such that it becomes usable in the context of other, bigger problems
where divisibility is just one of the issues.

-- Joachim