# RabbitFarm

### 2021-10-31

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

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

## Part 1

You are given 2 positive numbers, \$m and \$n. Write a script to find out if the given two numbers are Two Friendly.

### Solution

``````
:-initialization(main).

two_friendly(M, N):-
current_prolog_flag(max_integer, MAX_INTEGER),
between(1, MAX_INTEGER, M),
between(1, MAX_INTEGER, N),
GCD is gcd(M, N),
P is log(2, GCD),
P0 is ceiling(P),
P1 is floor(P),
P0 == P1.

main:-
(two_friendly(8, 24), format("1~n", _); format("0~n", _)),
(two_friendly(26, 39), format("1~n", _); format("0~n", _)),
(two_friendly(4, 10), format("1~n", _); format("0~n", _)),
halt.
``````

### Sample Run

``````
\$ gplc prolog/ch-1.p
\$ prolog/ch-1
1
0
1
``````

### Notes

Evn after years of writing Prolog I still get quite a kick out of its inherent power. Here the `two_friendly/2` predicate not only verifies for any `M` and `N` but also is multi-modal and can generate pairs for any `M` and `N` as well!

## Part 2

You are given a positive number \$n. Write a script to find how many different sequences you can create using Fibonacci numbers where the sum of unique numbers in each sequence are the same as the given number.

### Solution

``````
fibonaccis_below_n(N, Fibonaccis):-
fibonaccis_below_n(N, Fibonaccis, 0, [1, 1]).
fibonaccis_below_n(-1, Fibonaccis, _, Fibonaccis):- !.
fibonaccis_below_n(N, Fibonaccis, Sum, PartialFibonaccis):-
[H0, H1 | _] = PartialFibonaccis,
F is H0 + H1,
F < N,
fibonaccis_below_n(N, Fibonaccis, Sum, [F|PartialFibonaccis]).
fibonaccis_below_n(N, Fibonaccis, Sum, PartialFibonaccis):-
[H0, H1 | _] = PartialFibonaccis,
F is H0 + H1,
F > N,
fibonaccis_below_n(-1, Fibonaccis, Sum, PartialFibonaccis).

sum_x([], 0).
sum_x([X|Xs], X+Xse):-
sum_x(Xs, Xse).

sum_lists(X, N, Xsub):-
sublist(Xsub, X),
sum_x(Xsub, Xe),
N #= Xe.

fibonacci_sum_clp(N, Summands):-
fibonaccis_below_n(N, Fibonaccis),
sum_lists(Fibonaccis, N, Summands).
``````

### Sample Run

``````
\$ gprolog --consult-file prolog/ch-2.p
| ?- setof(Summands, fibonacci_sum_clp(16, Summands), S).

S = [[8,5,2,1],[8,5,3],[13,2,1],[13,3]]

(1 ms) yes
``````

### Notes

Instead of using a pre-computed list of Fibonacci numbers we generate them as needed. No particular reason other than it's a little more fun, and also it allows us to flexibly allow for virtually any value for `N`.

I just realized as I am looking at the code that I may have slightly misnamed the `fibonacci_sum_clp/2` predicate! I was experimenting with different approaches including a clpfd one. This is clearly not really using clpfd though! Instead `sublist/2` is used to generate and test all possible sublists of the Fibonacci subsequence with values less than `N`.

## References

Challenge 136

posted at: 20:09 by: Adam Russell | path: /prolog | permanent link to this entry