From 79a6d39fc08f0d3227e2fcfec823b95251493e21 Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.freedom.nl>
Date: Mon, 24 Jan 2022 17:43:56 +0100
Subject: Week 149, part 1. Improve Perl and AWK solutions.

We don't have to generate Fibonacci numbers up to some arbitrary
limit. Instead, we just generate as many as needed.
---
 challenge-149/abigail/awk/ch-1.awk | 32 ++++++++++++++----------
 challenge-149/abigail/perl/ch-1.pl | 50 ++++++++++++++++++++------------------
 2 files changed, 45 insertions(+), 37 deletions(-)

diff --git a/challenge-149/abigail/awk/ch-1.awk b/challenge-149/abigail/awk/ch-1.awk
index 392a9bd88a..db6182ff4f 100644
--- a/challenge-149/abigail/awk/ch-1.awk
+++ b/challenge-149/abigail/awk/ch-1.awk
@@ -17,23 +17,29 @@ function digit_sum (number, sum) {
     return sum
 }
 
-{
-    max_fib = 9 * (1 + length ($1))
-    f = 0
-    g = 1
+function is_fib (n, t) {
+    while (g < n) {
+        t = g
+        g = f + g
+        f = t
+        fib [g] = 1
+    }
+    return n in fib
+}
+
+BEGIN {
+    f       = 0
+    g       = 1
     fib [f] = 1
     fib [g] = 1
-    while (g < max_fib) {
-        t = f + g
-        fib [t] = 1
-        f = g
-        g = t
-    }
+}
 
-    for (c = k = 0; c < $1; k ++) {
-        if (digit_sum(k) in fib) {
+{
+    N = $1
+    for (k = 0; N > 0; k ++) {
+        if (is_fib(digit_sum(k))) {
             printf ("%d ", k)
-            c ++
+            N --
         }
     }
 
diff --git a/challenge-149/abigail/perl/ch-1.pl b/challenge-149/abigail/perl/ch-1.pl
index d1a1f7edb5..ca72dbefbf 100644
--- a/challenge-149/abigail/perl/ch-1.pl
+++ b/challenge-149/abigail/perl/ch-1.pl
@@ -21,39 +21,41 @@ use experimental 'lexical_subs';
 # This is sequence A028840 of the OEIS. The first 10,000 entries can
 # be found at https://oeis.org/A028840/b028840.txt
 #
-# We will make use of the following conjecture: the Nth number is <= 10 * N.
-# This holds for the first 10,000 numbers.
-#
-# Consider that we are asked to generate all the first N numbers (and not
-# the Nth number), I doubt we'll be feeding numbers exceeding 10,000 to
-# this program.
-#
 # For the sum of digits, we hark back to challenge 133, part 2.
 #
 
 use List::Util qw [sum];
+
+#
+# Return the sum of the digits of its argument
+#
 sub digitsum ($n) {sum $n =~ /\d/ag}
 
-while (<>) {
-    my $N = 0 + $_;
-    #
-    # Get an upper bound on the sum of the digits.
-    #
-    my $max_fib = 9 * (1 + length $N);
-    #
-    # Generate all the Fibonacci numbers up to $max_fib.
-    #
-    my %fib = (0 => 1, 1 => 1);
-    my ($f, $g) = (0, 1);
-    while ($g < $max_fib) {
-        ($f, $g) = ($g, $f + $g);
-        $fib {$g} = 1;
+#
+# Return whether the argument is a Fibonacci number. We do this by
+# keeping a hash with Fibonacci numbers, and keeping track of the
+# last 2 Fibonacci numbers produced. If the argument is larger than
+# the last Fibonacci number produced, we keep generating new 
+# Fibonacci numbers, until we have exceeded the argument. 
+#
+# Then it's a simple lookup.
+#
+sub is_fib ($n) {
+    state $fib = {0 => 1, 1 => 1};
+    state $f   = 0;
+    state $g   = 1;
+    while ($g < $n) {
+        ($f, $g)   = ($g, $f + $g);
+        $$fib {$g} = 1;
     }
+    $$fib {$n}
+}
 
-    for (my ($c, $k) = (0, 0); $c < $N; $k ++) {
-        if ($fib {digitsum $k}) {
+while (<>) {
+    for (my ($k, $N) = (0, 0 + $_); $N > 0; $k ++) {
+        if (is_fib (digitsum $k)) {
             print "$k ";
-            $c ++;
+            $N --;
         }
     }
     print "\n";
-- 
cgit