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