Perl Weekly Challenge 136.
My solutions (task 1, and task 2 ) to the The Weekly Challenge - 136.
Task 1: Two Friendly
Submitted by: Mohammad S Anwar
You are given 2 positive numbers, $m and $n.
Write a script to find out if the given two numbers are Two
Friendly.
Two positive numbers, m and n are two friendly when gcd(m, n)
= 2 ^ p where p > 0. The greatest common divisor (gcd) of a
set of numbers is the largest positive number that divides all
the numbers in the set without remainder.
Example 1
Input: $m = 8, $n = 24
Output: 1
Reason: gcd(8,24) = 8 => 2 ^ 3
Example 2
Input: $m = 26, $n = 39
Output: 0
Reason: gcd(26,39) = 13
Example 3
Input: $m = 4, $n = 10
Output: 1
Reason: gcd(4,10) = 2 => 2 ^ 1
Euclid’s algorithm may be used to get the greatest common divisor recursively: gcd(x,y) is gcd(y, r) where r is the residue of x divided by y, until y becomes 0, in which case, the result is x. The result is a (positive) power of two if its binary representation consists of one 1 followed by one or more 0’s, as can be checked by a regex. This allows an almost oneliner:
perl -E '$d=sprintf("%b",gcd(@ARGV[0],@ARGV[1]));
say join " ", "Inputs: ", @ARGV, "Output: ",$d=~/^10+/||0;
sub gcd{($x,$y)=@_;$y==0?$x:gcd($y,$x%$y)}'\
8 24
perl -E '$d=sprintf("%b",gcd(@ARGV[0],@ARGV[1]));
say join " ", "Inputs: ", @ARGV, "Output: ",$d=~/^10+/||0;
sub gcd{($x,$y)=@_;$y==0?$x:gcd($y,$x%$y)}'\
26 39
perl -E '$d=sprintf("%b",gcd(@ARGV[0],@ARGV[1]));
say join " ", "Inputs: ", @ARGV, "Output: ",$d=~/^10+/||0;
sub gcd{($x,$y)=@_;$y==0?$x:gcd($y,$x%$y)}'\
4 10
Results:
Inputs: 8 24 Output: 1
Inputs: 26 39 Output: 0
Inputs: 4 10 Output: 1
A full version would be the following
# Perl weekly challenge 136
# Task 1: Two friendly
#
# See https://wlmb.github.io/2021/10/25/PWC136/#task-1-two-friendly
use v5.12;
while(defined(my $x=shift @ARGV) and defined(my $y=shift @ARGV)){
my $d=gcd($x, $y);
my $b=sprintf "%b", $d;
my $output=$b=~/^1(0+)$/||0;
my $power=length($1);
say "Inputs: $x, $y\nOutput: $output\nSince gcd($x,$y)=$d",
$power?"=2**$power":"";
}
sub gcd {
my ($x,$y)=@_;
$y==0?$x:gcd($y,$x%$y);
}
./ch-1.pl 8 24 26 39 4 10
Task 2: Fibonacci Sequence
Submitted by: Mohammad S Anwar
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.
Fibonacci Numbers: 1,2,3,5,8,13,21,34,55,89, …
Example 1
Input: $n = 16
Output: 4
Reason: There are 4 possible sequences that can be created
using Fibonacci numbers, i.e. (3 + 13), (1 + 2 + 13), (3 +
5 + 8) and (1 + 2 + 5 + 8).
Example 2
Input: $n = 9
Output: 2
Reason: There are 2 possible sequences that can be created
using Fibonacci numbers
i.e. (1 + 3 + 5) and (1 + 8).
Example 3
Input: $n = 15
Output: 2
Reason: There are 2 possible sequences that can be created
using Fibonacci numbers
i.e. (2 + 5 + 8) and (2 + 13).
Clearly, N is a number that can be written as the sum of a Fibonacci number F and other larger Fibonacci numbers iff N-F may be written as a sum of larger Fibonacci numbers. This suggest a recursive solution to the problem. If we can define a function f that takes a Fibonacci number F and a number N and returns how many ways of writting N as a sum of non-repeating Fibonacci numbers equal or larger than F, then the sought solution would be f(n,1). However, f(n,1) is equal to f(n,2), the number of ways to write n as a sum of Fibonacci numbers excluding 1, and f(n-1,2), as you can reach n starting from 1 if you can reach n-1 starting from 2. More generally, f(N,F)=f(N,G)+f(N-F,G), where G is the Fibonacci number that follows F, i.e., G=F+E, where E is the Fibonacci number that comes before F. Thus, I add a third argument to f which is the previous Fibonacci number. That way, I can generate the required Fibonacci numbers on the fly. The boundary cases are F>N (no more ways) and F=N (one way). The solution is simple enough to fit in a couple of lines.
perl -E 'say fib($_,1,1) for @ARGV; sub fib{my ($n, $c, $p)=@_;
$c>$n?0:$c==$n?1:fib($n-$c,$p+$c,$c)+fib($n,$p+$c,$c)}' 16 9 15
Results:
4
2
2
A full solution can also generate and print the sequences.
# Perl weekly challenge 136
# Task 1: Fibonacci sequence
#
# See https://wlmb.github.io/2021/10/25/PWC136/#task-2-fibonacci-sequence
use v5.12;
foreach(@ARGV){
my $count=my @sequences=fib($_,1,1);
say "Input: $_\nOutput: $count",
$count?join "\n =", "\nAs $_", map {join "+", @$_} @sequences
:"";
}
sub fib {
my ($number, $current, $previous)=@_;
return
$current>$number? ()
:$current==$number? ([$current])
:(
fib($number,$current+$previous, $current),
map {unshift @$_, $current; $_}
(fib($number-$current,$current+$previous, $current))
);
}
Examples:
./ch-2.pl 16 9 15
Results:
Input: 16
Output: 4
As 16
=3+13
=3+5+8
=1+2+13
=1+2+5+8
Input: 9
Output: 2
As 9
=1+8
=1+3+5
Input: 15
Output: 2
As 15
=2+13
=2+5+8
Other examples:
./ch-2.pl 100 1000
Results:
Input: 100
Output: 9
As 100
=3+8+89
=3+8+34+55
=3+8+13+21+55
=1+2+8+89
=1+2+8+34+55
=1+2+8+13+21+55
=1+2+3+5+89
=1+2+3+5+34+55
=1+2+3+5+13+21+55
Input: 1000
Output: 15
As 1000
=13+987
=13+377+610
=13+144+233+610
=13+55+89+233+610
=13+21+34+89+233+610
=5+8+987
=5+8+377+610
=5+8+144+233+610
=5+8+55+89+233+610
=5+8+21+34+89+233+610
=2+3+8+987
=2+3+8+377+610
=2+3+8+144+233+610
=2+3+8+55+89+233+610
=2+3+8+21+34+89+233+610