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.



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. 

    (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", _)),

Sample Run

$ gplc prolog/ch-1.p 
$ prolog/ch-1   


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.


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


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.


Challenge 136

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