From: Sergey Dymchenko <kit1980_at_gmail.com>

Date: Tue, 31 May 2011 00:00:33 +0300

Date: Tue, 31 May 2011 00:00:33 +0300

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). 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?Received on Mon May 30 2011 - 21:00:39 CEST

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