3 ms·

This Python code does a full search and finds the unique solution instantly: p = 711 q = 711000000 for a in range(1, 1 + p // 4): if q % a ==

This Python code does a full search and finds the unique solution instantly: p = 711 q = 711000000 for a in range(1, 1 + p // 4): if q % a == 0: for b in range(a, 1 + (p - a) // 3): if q % (a * b) == 0: for c in range(b, 1 + (p - a - b) // 2): d = p - a - b - c if a * b * c * d == q: print (a, b, c, d) Does Prolog do the same pruning? Alternatively, it could be dumber (omit some of the pruning that my code does) or smarter (start by factoring 711000000 or something).

doublec 8y ago
You could write the same solution in prolog. The difference between yours and the original solution is the latter follows the original program specification and is easier to compare to it. That is, it defines what the problem is, not how to solve it.
tom_mellior 8y ago
Prolog doesn't do that automatically, but you can write the same thing in Prolog too: xkcd_ugly(A, B, C, D) :- P = 711, Q = 711000000, Max_A is 1 + P // 4, between(1, Max_A, A), Q mod A =:= 0, Max_B is 1 + (P - A) // 3, between(A, Max_B, B), Q mod (A * B) =:= 0, Max_C is 1 + (P - A - B) // 2, between(B, Max_C, C), D is P - A - B - C, A * B * C * D =:= Q. In SWI-Prolog, I get the following timings: ?- time(xkcd_ugly(A, B, C, D)). % 383,992 inferences, 0.056 CPU in 0.056 seconds (100% CPU, 6825328 Lips) A = 120, B = 125, C = 150, D = 316 ; % 3,274 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 1229464 Lips) false. That is to say, it found the first solution in 0.056 seconds CPU time, then took an additional 0.003 seconds to prove that there are no further solutions. (This is the minimum of a handful of runs, there is quite a bit of variation.) Quick and very dirty benchmarks on the same machine run your Python code in about 0.02 seconds. The CLP(FD) code above takes about 0.1 seconds but it's a lot clearer.
- cousin_it 8y ago
  Thank you! That makes sense.

doublec 8y ago

You could write the same solution in prolog. The difference between yours and the original solution is the latter follows the original program specification and is easier to compare to it. That is, it defines what the problem is, not how to solve it.

tom_mellior 8y ago

Prolog doesn't do that automatically, but you can write the same thing in Prolog too: xkcd_ugly(A, B, C, D) :- P = 711, Q = 711000000, Max_A is 1 + P // 4, between(1, Max_A, A), Q mod A =:= 0, Max_B is 1 + (P - A) // 3, between(A, Max_B, B), Q mod (A * B) =:= 0, Max_C is 1 + (P - A - B) // 2, between(B, Max_C, C), D is P - A - B - C, A * B * C * D =:= Q. In SWI-Prolog, I get the following timings: ?- time(xkcd_ugly(A, B, C, D)). % 383,992 inferences, 0.056 CPU in 0.056 seconds (100% CPU, 6825328 Lips) A = 120, B = 125, C = 150, D = 316 ; % 3,274 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 1229464 Lips) false. That is to say, it found the first solution in 0.056 seconds CPU time, then took an additional 0.003 seconds to prove that there are no further solutions. (This is the minimum of a handful of runs, there is quite a bit of variation.) Quick and very dirty benchmarks on the same machine run your Python code in about 0.02 seconds. The CLP(FD) code above takes about 0.1 seconds but it's a lot clearer.

cousin_it 8y ago
Thank you! That makes sense.