From: Joachim Schimpf <joachim.schimpf_at_monash.edu>

Date: Tue, 31 May 2011 12:26:40 +1000

Date: Tue, 31 May 2011 12:26:40 +1000

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. -- JoachimReceived on Tue May 31 2011 - 02:26:56 CEST

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*