Merge pull request #5139 from Util/branch-for-challenge-136

Add Raku and Perl solutions for #135 by Bruce Gray

4 files changed, 148 insertions, 0 deletions

diff --git a/challenge-136/bruce-gray/perl/ch-1.pl b/challenge-136/bruce-gray/perl/ch-1.pl
new file mode 100644
index 0000000000..201ae62f88
--- /dev/null
+++ b/challenge-136/bruce-gray/perl/ch-1.pl
@@ -0,0 +1,35 @@
+use 5.24.0;
+use warnings;
+use experimental qw<signatures>;
+use Test::More;
+
+sub gcd ( $x, $y ) {
+    # From https://xlinux.nist.gov/dads/HTML/euclidalgo.html
+    return $y == 0 ? $x : gcd($y, $x % $y);
+}
+
+sub is_power_of_two ( $x ) {
+    # From http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
+    return ( $x & ($x - 1) ) == 0;
+}
+
+sub are_two_friendly ( $m, $n ) {
+    my $g = gcd($m, $n);
+    return 0 + ( $g > 1 && is_power_of_two($g) );
+}
+
+my @tests = (
+    [ [ 8, 24], 1 ],
+    [ [26, 39], 0 ],
+    [ [ 4, 10], 1 ],
+    
+    [ [40, 48], 1 ],
+    [ [ 8, 64], 1 ],
+    [ [ 8,  1], 0 ],
+
+);
+plan tests => 0+@tests;
+for (@tests) {
+    my ( $input_aref, $expected ) = @{$_};
+    is are_two_friendly(@{$input_aref}), $expected;
+}
diff --git a/challenge-136/bruce-gray/perl/ch-2.pl b/challenge-136/bruce-gray/perl/ch-2.pl
new file mode 100644
index 0000000000..d9654c8a5c
--- /dev/null
+++ b/challenge-136/bruce-gray/perl/ch-2.pl
@@ -0,0 +1,40 @@
+use 5.24.0;
+use warnings;
+use experimental qw<signatures>;
+use Test::More;
+
+# From https://oeis.org/A000119 :
+#   a(n) = f(n,1,1) with f(x,y,z) = if x<y then 0^x else f(x-y,y+z,y)+f(x,y+z,y).
+# XXX Cached version gives huge speed-up.
+sub f ( $x, $y, $z ) {
+    return 0 ** $x if $x < $y;
+
+    return f( $x - $y, $y + $z, $y )
+         + f( $x     , $y + $z, $y );
+}
+sub Fibonacci_partitions ( $n ) { return f($n, 1, 1) }
+
+use Test::More;
+my @tests = (
+    [ 16, 4],
+    [  9, 2],
+    [ 15, 2],
+);
+# From https://oeis.org/A000119/list :
+my @A000119_list = (
+    1,1,1,2,1,2,2,1,3,2,2,3,1,3,3,2,4,2,3,3,1,4,3,3,
+    5,2,4,4,2,5,3,3,4,1,4,4,3,6,3,5,5,2,6,4,4,6,2,5,5,
+    3,6,3,4,4,1,5,4,4,7,3,6,6,3,8,5,5,7,2,6,6,4,8,4,6,
+    6,2,7,5,5,8,3,6,6,3,7,4,4,5,1,5,5,4,8,4,7,7,3,9,6,
+    6,9,3,8,8,5
+);
+plan tests => @tests + 1;
+for (@tests) {
+    my ($input, $expected) = @{$_};
+    is Fibonacci_partitions($input), $expected,
+      "Fibonacci_partitions($input)==$expected";
+}
+
+is_deeply [map {Fibonacci_partitions($_)} keys @A000119_list],
+          \@A000119_list,
+          'Whole A000119 list matches';
diff --git a/challenge-136/bruce-gray/raku/ch-1.raku b/challenge-136/bruce-gray/raku/ch-1.raku
new file mode 100644
index 0000000000..43c4bb6ae7
--- /dev/null
+++ b/challenge-136/bruce-gray/raku/ch-1.raku
@@ -0,0 +1,24 @@
+# From http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
+sub is-power-of-two ( UInt $x --> Bool ) { return ( $x +& ($x - 1) ) == 0 }
+
+sub are-two-friendly ( UInt $m, UInt $n --> Bool ) {
+    my $g = $m gcd $n;
+    return $g > 1 && is-power-of-two($g);
+}
+
+use Test;
+my @tests = 
+    ( 8, 24) => True,
+    (26, 39) => False,
+    ( 4, 10) => True,
+
+    (40, 48) => True,
+    ( 8, 64) => True,
+    ( 8,  1) => False,
+    ( 6, 18) => False,
+;
+plan +@tests;
+for @tests -> ( :key(@input), :value($expected) ) {
+    is are-two-friendly(|@input), $expected,
+        "are-two-friendly {@input.fmt('%2d')} == $expected";
+}
diff --git a/challenge-136/bruce-gray/raku/ch-2.raku b/challenge-136/bruce-gray/raku/ch-2.raku
new file mode 100644
index 0000000000..a715fd5720
--- /dev/null
+++ b/challenge-136/bruce-gray/raku/ch-2.raku
@@ -0,0 +1,49 @@
+# From https://oeis.org/A000119 :
+#   a(n) = f(n,1,1) with f(x,y,z) = if x<y then 0^x else f(x-y,y+z,y)+f(x,y+z,y).
+# XXX Cached version gives huge speed-up.
+sub Fibonacci_partitions ( UInt $n --> UInt ) {
+    my sub f ( \x, \y, \z ) {
+        return 0 ** x if x < y;
+
+        return f( x - y, y + z, y )
+             + f( x    , y + z, y );
+    }
+
+    return f($n, 1, 1);
+}
+
+# Alternate take: Pre-calculate *all* the answers to 0..F_sub_n, then just look them up as needed.
+# sub Fibonacci_partitions ( UInt $n --> UInt ) {
+#     constant @Fibonacci_11 = 1, 1, *+* ... *;
+#     constant @Fibonacci_12 = @Fibonacci_11.skip(1);
+#     constant $max_index = 19;
+#     constant $max = @Fibonacci_12[$max_index-1];
+#
+#     state Bag $all_combos = @Fibonacci_12.head($max_index).combinations».sum.Bag;
+#     die "$n exceeds current maximum $max" if $n >= $max;
+#     return $all_combos{$n};
+# }
+
+use Test;
+constant @tests =
+    16 => 4,
+     9 => 2,
+    15 => 2,
+;
+# From https://oeis.org/A000119/list :
+constant @A000119_list =
+    1,1,1,2,1,2,2,1,3,2,2,3,1,3,3,2,4,2,3,3,1,4,3,3,
+    5,2,4,4,2,5,3,3,4,1,4,4,3,6,3,5,5,2,6,4,4,6,2,5,5,
+    3,6,3,4,4,1,5,4,4,7,3,6,6,3,8,5,5,7,2,6,6,4,8,4,6,
+    6,2,7,5,5,8,3,6,6,3,7,4,4,5,1,5,5,4,8,4,7,7,3,9,6,
+    6,9,3,8,8,5
+;
+plan @tests + 1;
+for @tests -> ( :key($input), :value($expected) ) {
+    is Fibonacci_partitions($input), $expected,
+      "Fibonacci_partitions($input)==$expected";
+}
+
+is-deeply @A000119_list.keys.map(&Fibonacci_partitions),
+          @A000119_list,
+          'Whole A000119 list matches';