# RabbitFarm

### 2022-10-30

#### The Weekly Challenge 188 (Prolog Solutions)

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

## Part 1

You are given list of integers @list of size \$n and divisor \$k. Write a script to find out count of pairs in the given list that satisfies a set of rules.

### Solution

``````
divisible_pair(Numbers, K, Pair):-
length(Numbers, NumbersLength),
between(1, NumbersLength, I),
succ(I, INext),
between(INext, NumbersLength, J),
nth(I, Numbers, Ith),
nth(J, Numbers, Jth),
IJModK is (Ith + Jth) mod K,
IJModK == 0,
Pair = [I, J].

divisible_pairs(Numbers, K, Pairs):-
findall(Pair, divisible_pair(Numbers, K, Pair), Pairs).
``````

### Sample Run

``````
\$ gprolog --consult-file prolog/ch-1.p
| ?- divisible_pairs([4, 5, 1, 6], 2, Pairs), length(Pairs, NumberPairs).

NumberPairs = 2
Pairs = [[1,4],[2,3]]

(1 ms) yes
| ?- divisible_pairs([1, 2, 3, 4], 2, Pairs), length(Pairs, NumberPairs).

NumberPairs = 2
Pairs = [[1,3],[2,4]]

(1 ms) yes
| ?- divisible_pairs([1, 3, 4, 5], 3, Pairs), length(Pairs, NumberPairs).

NumberPairs = 2
Pairs = [[1,4],[3,4]]

yes
| ?- divisible_pairs([5, 1, 2, 3], 4, Pairs), length(Pairs, NumberPairs).

NumberPairs = 2
Pairs = [[1,4],[2,4]]

yes
| ?- divisible_pairs([7, 2, 4, 5], 4, Pairs), length(Pairs, NumberPairs).

NumberPairs = 1
Pairs = [[1,4]]

yes

``````

### Notes

The rules, if not clear from the above code are : the pair (i, j) is eligible if and only if

• 0 <= i < j < len(list)

• list[i] + list[j] is divisible by k

There really is not too much here beyond translating the rules into Prolog. The first condition on i and j are handled by default using `between/3`. Once we define how to find one such pair we use `findall/3` to obtain them all.

## Part 2

You are given two positive integers \$x and \$y. Write a script to find out the number of operations needed to make both ZERO.

### Solution

``````
count_zero(X, Y, Count):-
count_zero(X, Y, 0, Count), !.
count_zero(0, 0, Count, Count).
count_zero(X, Y, CountAccum, Count):-
X > Y,
XNew is X - Y,
succ(CountAccum, CountAccumSucc),
count_zero(XNew, Y, CountAccumSucc, Count).
count_zero(X, Y, CountAccum, Count):-
Y > X,
YNew is Y - X,
succ(CountAccum, CountAccumSucc),
count_zero(X, YNew, CountAccumSucc, Count).
count_zero(X, Y, CountAccum, Count):-
X == Y,
XNew is X - Y,
YNew is Y - X,
succ(CountAccum, CountAccumSucc),
count_zero(XNew, YNew, CountAccumSucc, Count).
``````

### Sample Run

``````
\$ gprolog --consult-file prolog/ch-2.p
| ?- count_zero(5, 4, Count).

Count = 5

(1 ms) yes
| ?- count_zero(4, 6, Count).

Count = 3

yes
| ?- count_zero(2, 5, Count).

Count = 4

yes
| ?- count_zero(3, 1, Count).

Count = 3

yes
| ?- count_zero(7, 4, Count).

Count = 5

yes
``````

### Notes

The operations are dictated by these rules:

• `\$x = \$x - \$y if \$x >= \$y`

or

• `\$y = \$y - \$x if \$y >= \$x (using the original value of \$x)`

Be carefully examining the rules we can see that we can arrange `count_zero/4` predicates in a somewhat concise way. I find this preferable to Prolog's if/else syntax which absolutely could have been used here. I would argue that the slightly longer form here is worthwhile in that it is much more readable.

One thing I found especially convenient was that due to the immutable nature of Prolog variables we don;t have to do any extra accounting for the possibly changed value of `X` when computing an updated `Y`. The Perl solution to this requires a temporary variable, for example.

## References

Challenge 188

posted at: 18:55 by: Adam Russell | path: /prolog | permanent link to this entry