# 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

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