Perl solutions for week 135

3 files changed, 96 insertions, 22 deletions

diff --git a/challenge-136/abigail/README.md b/challenge-136/abigail/README.md
index 6178e463fe..aa835b7f1e 100644
--- a/challenge-136/abigail/README.md
+++ b/challenge-136/abigail/README.md
@@ -2,30 +2,8 @@
 
 ## Part 1
 
-* [AWK](awk/ch-1.awk)
-* [Bash](bash/ch-1.sh)
-* [C](c/ch-1.c)
-* [Go](go/ch-1.go)
-* [Java](java/ch-1.java)
-* [Lua](lua/ch-1.lua)
-* [Node.js](node/ch-1.js)
 * [Perl](perl/ch-1.pl)
-* [Python](python/ch-1.py)
-* [Ruby](ruby/ch-1.rb)
-* [Scheme](scheme/ch-1.scm)
-* [Tcl](tcl/ch-1.tcl)
 
 ## Part 2
 
-* [AWK](awk/ch-2.awk)
-* [Bash](bash/ch-2.sh)
-* [C](c/ch-2.c)
-* [Go](go/ch-2.go)
-* [Java](java/ch-2.java)
-* [Lua](lua/ch-2.lua)
-* [Node.js](node/ch-2.js)
 * [Perl](perl/ch-2.pl)
-* [Python](python/ch-2.py)
-* [Ruby](ruby/ch-2.rb)
-* [Scheme](scheme/ch-2.scm)
-* [Tcl](tcl/ch-2.tcl)
diff --git a/challenge-136/abigail/perl/ch-1.pl b/challenge-136/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..878aa3a81b
--- /dev/null
+++ b/challenge-136/abigail/perl/ch-1.pl
@@ -0,0 +1,50 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# See ../README.md
+#
+
+#
+# Run as: perl ch-1.pl < input-file
+#
+
+#
+# We need the GCD of two numbers. We did this in the past a few times,
+# for instance in week 82. So, we copy-and-pasted the code from that week.
+#
+# We could write some code to check whether a number is a power of 2.
+# But there are only 63 powers of 2 which fit in a 64 bit integer, one
+# of them being 1. So, we can just precalculate the ones we're interested in.
+#
+my %power_of_2 = map {1 << $_ => 1} 1 .. 62;
+
+#
+# Find the GCD, using Stein's algorithm
+#    (https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
+#
+sub gcd;
+sub gcd ($u, $v) {
+    return $u if $u == $v || !$v;
+    return $v if             !$u;
+    my $u_odd = $u % 2;
+    my $v_odd = $v % 2;
+    return gcd ($u >> 1, $v >> 1) << 1 if !$u_odd && !$v_odd;
+    return gcd ($u >> 1, $v)           if !$u_odd &&  $v_odd;
+    return gcd ($u,      $v >> 1)      if  $u_odd && !$v_odd;
+    return gcd ($u - $v, $v)           if  $u     >   $v;
+    return gcd ($v - $u, $u);
+}
+
+#
+# Main program
+#
+say $power_of_2 {gcd split} || 0 while <>;
diff --git a/challenge-136/abigail/perl/ch-2.pl b/challenge-136/abigail/perl/ch-2.pl
new file mode 100644
index 0000000000..d9a5e5ae13
--- /dev/null
+++ b/challenge-136/abigail/perl/ch-2.pl
@@ -0,0 +1,46 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# See ../README.md
+#
+
+#
+# Run as: perl ch-2.pl < input-file
+#
+
+#
+# We will use a simple recursive function.
+# The function takes three arguments:
+#    - The target number we like to sum to ($target)
+#    - The smallest Fibonnaci number we have not tried yet ($this_fib)
+#    - The Fibonacci number proceeding the one above. ($prev_fib)
+#
+# If $this_fib is larger than $target, we have to way to make the target
+# number, so we return 0. 
+# If $this_fib is equal to $target, we can only make the target in one way,
+# so we return 1.
+# Else, we recurse. First, we count the number of ways to make
+# $target - $this_fib with Fibonnaci numbers larger than $this_fib, then
+# we count the number of ways making $target with Fibonnaci numbers larger
+# than $this_fib. We return the sum of these counts.
+#
+
+sub count;
+sub count ($target, $this_fib = 1, $prev_fib = 1) {
+      $this_fib >  $target ? 0
+    : $this_fib == $target ? 1
+    : count ($target - $this_fib, $this_fib + $prev_fib, $this_fib) +
+      count ($target,             $this_fib + $prev_fib, $this_fib)
+}
+
+
+say count $_ while <>;