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

From: Sergey Dymchenko <kit1980_at_gmail.com>
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