Week 151: AWK solutions

2 files changed, 70 insertions, 0 deletions

diff --git a/challenge-151/abigail/awk/ch-1.awk b/challenge-151/abigail/awk/ch-1.awk
new file mode 100644
index 0000000000..314efa9a0a
--- /dev/null
+++ b/challenge-151/abigail/awk/ch-1.awk
@@ -0,0 +1,42 @@
+#!/usr/bin/awk
+
+#
+# See https://theweeklychallenge.org/blog/perl-weekly-challenge-151
+#
+
+#
+# Run as: awk -f ch-1.awk < input-file
+#
+
+{
+    #
+    # Read in tree
+    #
+    delete tree
+    D = 0
+    i = 0
+    for (k = 0; k < NF; k ++) {
+        if ($k == "|") {
+            D ++
+            i = 0
+        }
+        else {
+            tree [D, i ++] = $k == "*" ? 0 : 1
+        }
+    }
+
+    #
+    # Find first node without children
+    #
+    for (d = 0; d <= D; d ++) {
+        for (i = 0; i < 2 ^ d; i ++) {
+            if (tree [d, i] && !tree [d + 1, 2 * i] && 
+                               !tree [d + 1, 2 * i + 1]) {
+                print d + 1
+                next
+            }
+        }
+    }
+}
+
+
diff --git a/challenge-151/abigail/awk/ch-2.awk b/challenge-151/abigail/awk/ch-2.awk
new file mode 100644
index 0000000000..3eb76a8e05
--- /dev/null
+++ b/challenge-151/abigail/awk/ch-2.awk
@@ -0,0 +1,28 @@
+#!/usr/bin/awk
+
+#
+# See https://theweeklychallenge.org/blog/perl-weekly-challenge-151
+#
+
+#
+# Run as: awk -f ch-2.awk < input-file
+#
+
+function best (i, max, sum, k) {
+    if (!(i in cache)) {
+        max = 0
+        for (k = i + 2; k <= NF; k ++) {
+            sum = best(k)
+            if (sum > max) {
+                max = sum
+            }
+        }
+        cache [i] = $i + max
+    }
+    return cache [i]
+}
+
+{
+    delete cache
+    print best(1)
+}