AWK solution for week 136

3 files changed, 63 insertions, 0 deletions

diff --git a/challenge-136/abigail/README.md b/challenge-136/abigail/README.md
index aa835b7f1e..ef4c25705c 100644
--- a/challenge-136/abigail/README.md
+++ b/challenge-136/abigail/README.md
@@ -2,8 +2,10 @@
 
 ## Part 1
 
+* [GNU AWK](awk/ch-1.gawk)
 * [Perl](perl/ch-1.pl)
 
 ## Part 2
 
+* [AWK](awk/ch-2.awk)
 * [Perl](perl/ch-2.pl)
diff --git a/challenge-136/abigail/awk/ch-1.gawk b/challenge-136/abigail/awk/ch-1.gawk
new file mode 100644
index 0000000000..c40210446f
--- /dev/null
+++ b/challenge-136/abigail/awk/ch-1.gawk
@@ -0,0 +1,41 @@
+#!/opt/local/bin/gawk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: gawk -f ch-1.gawk < input-file
+#
+
+
+#
+# Find the GCD, using Stein's algorithm
+#    (https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
+#
+function gcd (u, v, u_odd, v_odd) {
+    u_odd = u % 2
+    v_odd = v % 2
+
+    return u == v || !v     ? u                                             \
+         :           !u     ? v                                             \
+         : !u_odd && !v_odd ? lshift (gcd(rshift (u, 1), rshift (v, 1)), 1) \
+         : !u_odd && !v_odd ?         gcd(rshift (u, 1), v)                 \
+         : !u_odd && !v_odd ?         gcd(u,             rshift (v, 1))     \
+         :  u     >   v     ?         gcd(u - v,         v)                 \
+         :                            gcd(v - u,         u)
+}
+
+#
+# Pre calculate powers of 2. We can do powers up to and including 2^52
+#
+BEGIN {
+    for (i = 1; i <= 52; i ++) {
+        power_of_2 [lshift (1, i)] = 1
+    }
+}
+
+
+{
+    print power_of_2 [gcd($1, $2)] || 0
+}
diff --git a/challenge-136/abigail/awk/ch-2.awk b/challenge-136/abigail/awk/ch-2.awk
new file mode 100644
index 0000000000..f950feb582
--- /dev/null
+++ b/challenge-136/abigail/awk/ch-2.awk
@@ -0,0 +1,20 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: awk -f ch-2.awk < input-file
+#
+
+function count (target, this_fib, prev_fib) {
+    return target <  this_fib ? 0                                    \
+         : target == this_fib ? 1                                    \
+         : count(target - this_fib, this_fib + prev_fib, this_fib) + \
+           count(target,            this_fib + prev_fib, this_fib)
+}
+
+{
+    print count($1, 1, 1)
+}