Week 3: copied solutions from week 123.

Week 123 has exactly the same challenge. Since I prefer that solution,
I copied those results. Tests adjusted accordingly.

1 files changed, 39 insertions, 16 deletions

diff --git a/challenge-003/abigail/perl/ch-1.pl b/challenge-003/abigail/perl/ch-1.pl
index 352466e41c..2b9787b3c9 100644
--- a/challenge-003/abigail/perl/ch-1.pl
+++ b/challenge-003/abigail/perl/ch-1.pl
@@ -10,32 +10,55 @@ use experimental 'signatures';
 use experimental 'lexical_subs';
 
 #
-# See ../README.md
+# See https://theweeklychallenge.org/blog/perl-weekly-challenge-003
 #
 
 #
 # Run as: perl ch-1.pl < input-file
 #
 
-#
-# Read the maximum number from STDIN
-#
-chomp (my $MAX = <>);
+use List::Util qw [min];
+my @ugly   = (1);
+my $next_2 =  0;
+my $next_3 =  0;
+my $next_5 =  0;
 
 #
-# Generate the 5-smooth numbers up to $MAX.
-# This does *NOT* generate the numbers is order. It does, however,
-# generate all of them, and no other numbers.
+# We will maintain the following invariants:
 #
+#     2 * $ugly [$next_2 - 1] <= $ugly [-1] < 2 * $ugly [$next_2]
+#     3 * $ugly [$next_3 - 1] <= $ugly [-1] < 3 * $ugly [$next_2]
+#     5 * $ugly [$next_5 - 1] <= $ugly [-1] < 5 * $ugly [$next_2]
 #
-# $base2 is of the form 2^i;              i       >= 0
-# $base3 if of the form 2^i * 3^j;        i, j    >= 0
-# $base5 is of the form 2^i * 3^j * 5^k;  i, j, k >= 0
+# And since every ugly number (except the first) is either twice an
+# ugly number, three times an ugly number, or five times an ugly
+# number, the next ugly number will be the minimum of 
+# (2 * $ugly [$next_2], 3 * $ugly [$next_3], 5 * $ugly [$next_5]).
 #
-for (my $base2 = 1; $base2 <= $MAX; $base2 *= 2) {
-    for (my $base3 = $base2; $base3 <= $MAX; $base3 *= 3) {
-        for (my $base5 = $base3; $base5 <= $MAX; $base5 *= 5) {
-            say $base5;
-        }
+# We will spend O(1) time per generated ugly number, so our
+# program will run in O(N) time, using O(N) memory.
+#
+
+while (my $n = <>) {
+    while (@ugly < $n) {
+        #
+        # Calculate the next ugly number.
+        #
+        push @ugly => min 2 * $ugly [$next_2],
+                          3 * $ugly [$next_3],
+                          5 * $ugly [$next_5];
+
+        #
+        # Update pointers. It could be that more than one pointer needs
+        # updating. (This happens if the ugly number generated is
+        # divisible by 6, 10, 15, or 30). No pointer ever needs updating twice.
+        #
+        $next_2 ++ if 2 * $ugly [$next_2] <= $ugly [-1];
+        $next_3 ++ if 3 * $ugly [$next_3] <= $ugly [-1];
+        $next_5 ++ if 5 * $ugly [$next_5] <= $ugly [-1];
     }
+    say $ugly [-1];
 }
+
+
+__END__