Merge pull request #5404 from PerlMonk-Athanasius/branch-for-challenge-144

Perl & Raku solutions to Tasks 1 & 2 of the Perl Weekly Challenge #144

4 files changed, 576 insertions, 0 deletions

diff --git a/challenge-144/athanasius/perl/ch-1.pl b/challenge-144/athanasius/perl/ch-1.pl
new file mode 100644
index 0000000000..de8f7b79a4
--- /dev/null
+++ b/challenge-144/athanasius/perl/ch-1.pl
@@ -0,0 +1,155 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 144
+=========================
+
+TASK #1
+-------
+*Semiprime*
+
+Submitted by: Mohammad S Anwar
+
+Write a script to generate all Semiprime number <= 100.
+
+For more information about Semiprime, please checkout the
+[ https://en.wikipedia.org/wiki/Semiprime |wikipedia page].
+
+    In mathematics, a semiprime is a natural number that is the product of
+    exactly two prime numbers. The two primes in the product may equal each
+    other, so the semiprimes include the squares of prime numbers.
+
+Example
+
+ 10 is Semiprime as 10 = 2 x 5
+ 15 is Semiprime as 15 = 3 x 5
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Algorithm
+---------
+(1) Primes are generated via a Sieve of Eratosthenes. But how many primes are
+    needed? Consider: each semiprime is the product of 2 primes, and the small-
+    est prime is 2. If a given prime p is such that 2p is greater than 100,
+    then 3p will also be greater than 100, as will 5p, and so on, so p cannot
+    contribute to the semiprimes less than or equal to 100. And the same logic
+    holds for any prime number greater than p. So the primes needed are 2, 3,
+    5, ..., q, where q is the largest prime for which 2q is less than or equal
+    to 100.
+
+(2) For each prime p, semiprimes are generated by multiplying p by each of the
+    primes q between 2 and p, inclusive. But as soon as the product is greater
+    than 100, the result is discarded and the remaining values of q can also be
+    skipped, since they will all generate semiprimes greater than 100.
+
+(3) The resulting list is guaranteed to include all semiprimes less than or
+    equal to 100, and only those. But in some cases semiprimes are generated
+    out of order. For example, 5 x 3 = 15 is generated before 7 x 2 = 14. It is
+    therefore necessary to sort the semiprimes (in ascending numerical order)
+    before they are displayed.
+
+(4) The resulting list of semiprimes contains 34 elements as follows:
+
+         4,  6,  9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49,
+        51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95
+
+    -- which agrees with the entry for Semiprimes in the Online Encyclopedia of
+    Integer Sequences, https://oeis.org/A001358
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+
+const my $MAX   =>  100;
+const my $USAGE => "Usage:\n  perl $0\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+    $| = 1;
+    print "\nChallenge 144, Task #1: Semiprime (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+    my $args = scalar @ARGV;
+       $args == 0 or error( "Expected 0 command line arguments, found $args" );
+
+    print "The semiprimes <= $MAX are:\n\n";
+
+    my $primes = find_primes();
+    my @semiprimes;
+
+    L_OUTER:
+    for my $i (0 .. $#$primes)
+    {
+        my $prime1 = $primes->[ $i ];
+
+        for my $j (0 .. $i)
+        {
+            my $prime2  = $primes->[ $j ];
+            my $product = $prime1 * $prime2;
+
+            next L_OUTER if $product > $MAX;
+
+            push @semiprimes, $product;
+        }
+    }
+
+    @semiprimes = sort { $a <=> $b } @semiprimes;
+
+    printf "%s\n", join ', ', @semiprimes;
+}
+
+#------------------------------------------------------------------------------
+sub find_primes
+#------------------------------------------------------------------------------
+{
+    use enum qw( NOT_PRIME PRIME );
+
+    my $max   = int( $MAX / 2 );
+    my @sieve = ((NOT_PRIME) x 2, (PRIME) x ($max - 1));
+    my @primes;
+
+    for my $i (2 .. $max)
+    {
+        if ($sieve[ $i ] == PRIME)
+        {
+            push @primes, $i;
+
+            for (my $j = 2 * $i; $j <= $max; $j += $i)
+            {
+                $sieve[ $j ] = NOT_PRIME;
+            }
+        }
+    }
+
+    return \@primes;
+}
+
+#------------------------------------------------------------------------------
+sub error
+#------------------------------------------------------------------------------
+{
+    my ($message) = @_;
+
+    die "ERROR: $message\n$USAGE";
+}
+
+###############################################################################
diff --git a/challenge-144/athanasius/perl/ch-2.pl b/challenge-144/athanasius/perl/ch-2.pl
new file mode 100644
index 0000000000..66380da332
--- /dev/null
+++ b/challenge-144/athanasius/perl/ch-2.pl
@@ -0,0 +1,169 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 144
+=========================
+
+TASK #2
+-------
+*Ulam Sequence*
+
+Submitted by: Mohammad S Anwar
+
+You are given two positive numbers, $u and $v.
+
+Write a script to generate Ulam Sequence having at least 10 Ulam numbers where
+$u and $v are the first 2 Ulam numbers.
+
+For more information about Ulam Sequence, please checkout the
+[ https://en.wikipedia.org/wiki/Ulam_number |website].
+
+    The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 = 1
+    and U2 = 2. Then for n > 2, Un is defined to be the smallest integer that
+    is the sum of two distinct earlier terms in exactly one way and larger than
+    all earlier terms.
+
+Example 1
+
+ Input: $u = 1, $v = 2
+ Output: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18
+
+Example 2
+
+ Input: $u = 2, $v = 3
+ Output: 2, 3, 5, 7, 8, 9, 13, 14, 18, 19
+
+Example 3
+
+ Input: $u = 2, $v = 5
+ Output: 2, 5, 7, 9, 11, 12, 13, 15, 19, 23
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Algorithm
+---------
+@ulams is an array containing Ulam numbers in the order of their discovery.
+%sums  is a hash matching each sum of two distinct Ulam numbers to a count of
+       the number of different ways in which that sum can be produced.
+
+The main loop generates one new Ulam number per iteration, as follows:
+    - New sums are generated by adding the latest (i.e. last found) Ulam number
+      $last to each of the previously-known Ulam numbers.
+    - The next Ulam number is the smallest key in %sums which (1) is greater
+      than $last and (2) has a count of 1.
+
+Note that %sums is pruned on each iteration of the main loop by deleting all
+the sums less than or equal to $last. This is not strictly necessary (a
+different logic could be used), but has two advantages:
+    1. It simplifies the logic, as the smallest candidate Ulam number is
+       guaranteed to be greater than $last.
+    2. It prevents %sums from becoming unnecessarily large in memory. (This is
+       not a consideration when $TARGET = 10, but could become significant for
+       large values of $TARGET.)
+
+Performance
+-----------
+On my machine, the first 10,000 Ulam numbers for $u = 1, $v = 2 (see
+https://oeis.org/A002858/b002858.txt) are generated in around 15 min 33 sec.
+
+Note that each Ulam number is displayed as it is found. This allows the user to
+monitor progress when using large values of $TARGET.
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+use List::Util     qw( min );
+use Regexp::Common qw( number );
+use constant TIMER =>  0;               # Compile-time constant
+
+const my $TARGET   => 10;               # Run-time constants
+const my $USAGE    =>
+"Usage:
+  perl $0 <u> <v>
+
+    <u>    A positive integer
+    <v>    A positive integer > u\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+    $| = 1;
+    print "\nChallenge 144, Task #2: Ulam Sequence (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+    use if TIMER, 'Time::HiRes' => qw( gettimeofday tv_interval );
+
+    my $t0    = [gettimeofday] if TIMER;
+    my @ulams = parse_command_line();
+    my $last  = $ulams[ 1 ];
+    my %sums;
+
+    printf "Input:  \$u = %d, \$v = %d\nOutput: %d, %d", @ulams, @ulams;
+
+    while (scalar @ulams < $TARGET)
+    {
+        ++$sums{ $_ + $last } for @ulams[ 0 .. $#ulams - 1 ];
+
+        $last = min grep { $sums{ $_ } == 1 } keys %sums;
+
+        push @ulams, $last;
+        print ", $last";
+
+        $_ <= $last && delete $sums{ $_ } for keys %sums;
+    }
+
+    print "\n";
+    my $t = tv_interval( $t0 ) if TIMER;
+    print "\n$t seconds\n"     if TIMER;
+}
+
+#------------------------------------------------------------------------------
+sub parse_command_line
+#------------------------------------------------------------------------------
+{
+    my $args = scalar @ARGV;
+       $args == 2 or error( "Expected 2 command line arguments, found $args" );
+
+    for (@ARGV)
+    {
+        / ^ $RE{num}{int} $ /x
+                  or error( qq["$_" is not a valid integer] );
+
+        $_ > 0    or error( "$_ is not positive" );
+    }
+
+    my ($u, $v) = @ARGV;
+
+    $v > $u       or error( "$v is not greater than $u" );
+
+    return ($u, $v);
+}
+
+#------------------------------------------------------------------------------
+sub error
+#------------------------------------------------------------------------------
+{
+    my ($message) = @_;
+
+    die "ERROR: $message\n$USAGE";
+}
+
+###############################################################################
diff --git a/challenge-144/athanasius/raku/ch-1.raku b/challenge-144/athanasius/raku/ch-1.raku
new file mode 100644
index 0000000000..6b5cc8b077
--- /dev/null
+++ b/challenge-144/athanasius/raku/ch-1.raku
@@ -0,0 +1,122 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 144
+=========================
+
+TASK #1
+-------
+*Semiprime*
+
+Submitted by: Mohammad S Anwar
+
+Write a script to generate all Semiprime number <= 100.
+
+For more information about Semiprime, please checkout the
+[ https://en.wikipedia.org/wiki/Semiprime |wikipedia page].
+
+    In mathematics, a semiprime is a natural number that is the product of
+    exactly two prime numbers. The two primes in the product may equal each
+    other, so the semiprimes include the squares of prime numbers.
+
+Example
+
+ 10 is Semiprime as 10 = 2 x 5
+ 15 is Semiprime as 15 = 3 x 5
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Algorithm
+---------
+(1) Primes are generated using Raku's built-in is-prime() method. But how many
+    primes are needed? Consider: each semiprime is the product of 2 primes, and
+    the smallest prime is 2. If a given prime p is such that 2p is greater than
+    100, then 3p will also be greater than 100, as will 5p, and so on, so p
+    cannot contribute to the semiprimes less than or equal to 100. And the same
+    logic holds for any prime number greater than p. So the primes needed are
+    2, 3, 5, ..., q, where q is the largest prime for which 2q is less than or
+    equal to 100.
+
+(2) For each prime p, semiprimes are generated by multiplying p by each of the
+    primes q between 2 and p, inclusive. But as soon as the product is greater
+    than 100, the result is discarded and the remaining values of q can also be
+    skipped, since they will all generate semiprimes greater than 100.
+
+(3) The resulting list is guaranteed to include all semiprimes less than or
+    equal to 100, and only those. But in some cases semiprimes are generated
+    out of order. For example, 5 x 3 = 15 is generated before 7 x 2 = 14. It is
+    therefore necessary to sort the semiprimes (in ascending numerical order)
+    before they are displayed.
+
+(4) The resulting list of semiprimes contains 34 elements as follows:
+
+         4,  6,  9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49,
+        51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95
+
+    -- which agrees with the entry for Semiprimes in the Online Encyclopedia of
+    Integer Sequences, https://oeis.org/A001358
+
+=end comment
+#==============================================================================
+
+my UInt constant $MAX = 100;
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+    "\nChallenge 144, Task #1: Semiprime (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN()
+#==============================================================================
+{
+    "The semiprimes <= $MAX are:\n".put;
+
+    my UInt @primes = (2 .. ($MAX / 2).floor).grep: { .is-prime };
+    my UInt @semiprimes;
+
+    L-OUTER:
+    for 0 .. @primes.end -> UInt $i
+    {
+        my UInt $prime1 = @primes[ $i ];
+
+        for 0 .. $i -> UInt $j
+        {
+            my UInt $prime2  = @primes[ $j ];
+            my UInt $product = $prime1 * $prime2;
+
+            next L-OUTER if $product > $MAX;
+
+            @semiprimes.push: $product;
+        }
+    }
+
+    @semiprimes.=sort;
+
+    "%s\n".printf: @semiprimes.join: ', ';
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+    my Str $usage = $*USAGE;
+
+    $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+
+    $usage.put;
+}
+
+##############################################################################
diff --git a/challenge-144/athanasius/raku/ch-2.raku b/challenge-144/athanasius/raku/ch-2.raku
new file mode 100644
index 0000000000..2a9c6e1950
--- /dev/null
+++ b/challenge-144/athanasius/raku/ch-2.raku
@@ -0,0 +1,130 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 144
+=========================
+
+TASK #2
+-------
+*Ulam Sequence*
+
+Submitted by: Mohammad S Anwar
+
+You are given two positive numbers, $u and $v.
+
+Write a script to generate Ulam Sequence having at least 10 Ulam numbers where
+$u and $v are the first 2 Ulam numbers.
+
+For more information about Ulam Sequence, please checkout the
+[ https://en.wikipedia.org/wiki/Ulam_number |website].
+
+    The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 = 1
+    and U2 = 2. Then for n > 2, Un is defined to be the smallest integer that
+    is the sum of two distinct earlier terms in exactly one way and larger than
+    all earlier terms.
+
+Example 1
+
+ Input: $u = 1, $v = 2
+ Output: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18
+
+Example 2
+
+ Input: $u = 2, $v = 3
+ Output: 2, 3, 5, 7, 8, 9, 13, 14, 18, 19
+
+Example 3
+
+ Input: $u = 2, $v = 5
+ Output: 2, 5, 7, 9, 11, 12, 13, 15, 19, 23
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Algorithm
+---------
+@ulams is an array containing Ulam numbers in the order of their discovery.
+%sums  is a hash matching each sum of two distinct Ulam numbers to a count of
+       the number of different ways in which that sum can be produced.
+
+The main loop generates one new Ulam number per iteration, as follows:
+    - New sums are generated by adding the latest (i.e. last found) Ulam number
+      $last to each of the previously-known Ulam numbers.
+    - The next Ulam number is the smallest key in %sums which (1) is greater
+      than $last and (2) has a count of 1.
+
+Note that %sums is pruned on each iteration of the main loop by deleting all
+the sums less than or equal to $last. This is not strictly necessary (a
+different logic could be used), but has two advantages:
+    1. It simplifies the logic, as the smallest candidate Ulam number is
+       guaranteed to be greater than $last.
+    2. It prevents %sums from becoming unnecessarily large in memory. (This is
+       not a consideration when $TARGET = 10, but could become significant for
+       large values of $TARGET.)
+
+Each Ulam number is displayed as it is found. This allows the user to monitor
+progress when using large values of $TARGET.
+
+=end comment
+#==============================================================================
+
+subset Pos of Int where * > 0;
+
+my Pos constant $TARGET = 10;
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+    "\nChallenge 144, Task #2: Ulam Sequence (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN
+(
+    Pos:D $u,                             #= A positive integer
+    Pos:D $v where { $v > $u }            #= A positive integer > u
+)
+#==============================================================================
+{
+    "Input:  \$u = $u, \$v = $v\nOutput: $u, $v".print;
+
+    my Pos @ulams = $u, $v;
+    my Pos $last  = $v;
+    my Pos %sums;
+
+    while @ulams.elems < $TARGET
+    {
+        ++%sums{ $_ + $last } for @ulams[ 0 .. @ulams.end - 1 ];
+
+        $last = %sums.keys.grep( { %sums{ $_ } == 1 } ).map( { .Int } ).min;
+
+        @ulams.push: $last;
+        ", $last".print;
+
+        $_ <= $last && (%sums{ $_ }:delete) for %sums.keys;
+    }
+
+    put();
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+    my Str $usage = $*USAGE;
+
+    $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+    $usage.put;
+}
+
+##############################################################################