RabbitFarm
2021-10-31
Friendly Fibonacci Summands
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
posted at: 20:09 by: Adam Russell | path: /perl | permanent link to this entry
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