RabbitFarm

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

use strict;
use warnings;
use POSIX;
use boolean;

sub euclid {
    my($a, $b) = @_;
    return ($b) ? euclid($b, $a % $b) : $a;
}

sub two_friendly{
    my($m, $n) = @_;
    my $gcd = euclid($m, $n);
    my $p = log($gcd) / log(2);
    return boolean(ceil($p) == floor($p));
}

MAIN:{
    print two_friendly(8, 24). "\n";
    print two_friendly(26, 39). "\n";
    print two_friendly(4, 10). "\n";
}

Sample Run

$ perl perl/ch-1.pl
1
0
1

Notes

I've used this code for Euclid's GCD method before in Challenge 089. To determine if $p is an integer we check to see if the floor() and ceiling() are equal.

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

use strict;
use warnings;
use Data::PowerSet q/powerset/;

sub fibonacci_below_n{
    my($n, $fibonaccis) = @_;
    $fibonaccis = [1, 1] if !$fibonaccis;
    my $f = $fibonaccis->[@{$fibonaccis} - 2] + $fibonaccis->[@{$fibonaccis} - 1];
    if($f < $n){
        push @{$fibonaccis}, $f;
        fibonacci_below_n($n, $fibonaccis);
    }
    else{
        shift @{$fibonaccis};
        return $fibonaccis;
    }
}

sub fibonacci_sum{
    my($n) = @_;
    my $powerset = powerset(fibonacci_below_n($n));
    my @summands = grep {
        my $fibonaccis = $_;
        my $sum = 0;
        map{
            $sum += $_;
        } @{$fibonaccis};
        $sum == $n;
    } @{$powerset};
    return @summands;
}

MAIN:{
    for my $summands (fibonacci_sum($ARGV[0])){
        print "(" . join(" + ", @{$summands}) . ") = " . $ARGV[0] . "\n";
    }
}

Sample Run

$ perl perl/ch-2.pl 16
(3 + 13) = 16
(1 + 2 + 13) = 16
(3 + 5 + 8) = 16
(1 + 2 + 5 + 8) = 16

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.

The sequences are determined by examining the Power Set of all possible sequences and checking the sums.

References

Challenge 136

Power Set

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