RabbitFarm

The examples used here are from the weekly challenge problem statement and demonstrate the working solution.

Part 1: Double Exist

You are given an array of integers, @ints. Write a script to find if there exist two indices $i and $j such that:

1. $i≠$j
2. 0 ≥ $i < size @ints and 0 ≥ $j < size @ints
3. $ints[$i] = 2 ∗ $ints[$j]

This is a nice problem for Constraint Logic Programming. The solution is contained in just a single predicate which uses GNU Prolog’s finite domain (FD) constraint solver.

The rest of the code just wraps this predicate into a file.

Sample Run

$ gprolog --consult-file prolog/ch-1.p 
| ?- double_exist([6, 2, 3, 3], I, J). 
 
I = 1 
J = 3 
 
yes 
| ?- double_exist([3, 1, 4, 13], I, J). 
 
no 
| ?- double_exist([2, 1, 4, 2], I, J). 
 
I = 1 
J = 2 ? 
 
(1 ms) yes 
| ?- double_exist([2, 1, 4, 2], I, J). 
 
I = 1 
J = 2 ? ; 
 
I = 3 
J = 1 
 
yes 
| ?-
    

Part 2: Luhn’s Algorithm

You are given a string $str containing digits (and possibly other characters which can be ignored). The last digit is the payload; consider it separately. Counting from the right, double the value of the first, third, etc. of the remaining digits. For each value now greater than 9, sum its digits. The correct check digit is that which, added to the sum of all values, would bring the total mod 10 to zero. Return true if and only if the payload is equal to the correct check digit.

This is essentially a list processing problem and is quite amenable to a DCG solution. Here I just use some ordinary predicates though.

For convenience we’ll have a predicate for summing the digits of numbers > 10.

Finally, let’s assemble our completed code into a single file.

Sample Run

$ gprolog prolog/ch-2.p 
| ?- luhn([1, 7, 8, 9, 3, 7, 2, 9, 9, 7, 4]). 
 
yes 
| ?- luhn([4, 1, 3, 7, 8, 9, 4, 7, 1, 1, 7, 5, 5, 9, 0, 4]). 
 
yes 
| ?- luhn([4, 1, 3, 7, 8, 9, 7, 4, 1, 1, 7, 5, 5, 9, 0, 4]). 
 
no 
| ?-
    

References

The Weekly Challenge 290
Generated Code