CODEWITHSUNDEEP
prologclpfd
vasily
vasily

Reputation: 2920

Solving Euler 4 with CLP

I've got this very slow solution to Project Euler 4,

:- use_module(library(clpfd)).

euler_004(P) :-
  A in 1..9,
  B in 0..9,
  C in 0..9,
  P #= A * 100001 + B * 10010 + C * 1100,
  D in 100..999,
  E in 100..999,
  E #>= D,
  P #= D * E,
  labeling([max(P)], [P]).

Is there a way to speed it up?

Upvotes: 0

Views: 105

Answers (2)

jnmonette
jnmonette

Reputation: 1794

Here is an alternative search strategy that cuts down the time tremendously.

...
labeling([max(P),down], [A,B,C]).

The rationale is that:

  1. Searching on A, B, and C instead of P potentially reduces the size of the search space from the order of 10^6 to only 10^3.
  2. In order to maximize P, it is interesting to try larger values of A, B, and C first (especially A), which is achieved by using the search option down.

In SWISH, this reduced the time from ~63 seconds to around 0.2 second.

Upvotes: 4

hakank
hakank

Reputation: 6854

Your original model takes 32.8s on my machine using SWI-Prolog. This version, using ff,bisect as search strategies, takes 3.1s:

euler4c(P) :-
  A in 1..9,
  B in 0..9,
  C in 0..9,
  D in 100..999,
  E in 100..999,
  E #>= D,
  P #= D * E,
  P #= A * 100001 + B * 10010 + C * 1100,  
  labeling([max(P),ff,bisect], [P]). % 3.1s

Also, SWI Prolog's CLP solver is generally not the fastest CLP solver, so other Prolog's might be faster.

Also, see my non-CLP SWI Prolog approaches to this problem: http://hakank.org/swi_prolog/euler4.pl (solving the problem in about 0.2s).

Upvotes: 2

Related Questions