aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-133/athanasius/perl/ch-1.pl150
-rw-r--r--challenge-133/athanasius/perl/ch-2.pl123
-rw-r--r--challenge-133/athanasius/raku/ch-1.raku120
-rw-r--r--challenge-133/athanasius/raku/ch-2.raku124
4 files changed, 517 insertions, 0 deletions
diff --git a/challenge-133/athanasius/perl/ch-1.pl b/challenge-133/athanasius/perl/ch-1.pl
new file mode 100644
index 0000000000..38eb659b0b
--- /dev/null
+++ b/challenge-133/athanasius/perl/ch-1.pl
@@ -0,0 +1,150 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 133
+=========================
+
+TASK #1
+-------
+*Integer Square Root*
+
+Submitted by: Mohammad S Anwar
+
+You are given a positive integer $N.
+
+Write a script to calculate the integer square root of the given number.
+
+Please avoid using built-in function. Find out more about it
+[ https://en.wikipedia.org/wiki/Integer_square_root |here].
+
+Examples
+
+ Input: $N = 10
+ Output: 3
+
+ Input: $N = 27
+ Output: 5
+
+ Input: $N = 85
+ Output: 9
+
+ Input: $N = 101
+ Output: 10
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Algorithm
+---------
+The solution is found using both Newton's method (aka Heron's method) and the
+digit-by-digit algorithm (recursive version) described in the Wikipedia article
+cited in the Task Description.
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+use Regexp::Common qw( number );
+
+const my $DBL_LOG_2 => 1.386_294_361_119_890_618_834_464_242_916_4;
+const my $USAGE =>
+"Usage:
+ perl $0 <N>
+
+ <N> A positive integer\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ $| = 1;
+ print "\nChallenge 133, Task #1: Integer Square Root (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+ my $N = parse_command_line();
+
+ print "Input: \$N = $N\n";
+ printf "Output: %d (Newton's method)\n", int_sqrt_newton( $N );
+ printf " %d (digit-by-digit algorithm)\n", int_sqrt_digit ( $N );
+}
+
+#------------------------------------------------------------------------------
+sub int_sqrt_newton
+#------------------------------------------------------------------------------
+{
+ my ($n) = @_;
+
+ # x0 = 2^(⎣log2(n) / 2⎦ + 1) gives a good starting value for x0 (see
+ # https://en.wikipedia.org/wiki/Integer_square_root#Numerical_example); but
+ # x0 = ($n / 2) + 1 is an acceptable (and simpler) alternative :-)
+
+ my $x0 = 2 ** (int( log($n) / $DBL_LOG_2) + 1);
+ my $x1 = ($x0 + ($n / $x0)) / 2;
+
+ while ($x1 < $x0)
+ {
+ $x0 = $x1;
+ $x1 = ($x0 + ($n / $x0)) / 2;
+ }
+
+ return $x0;
+}
+
+#------------------------------------------------------------------------------
+sub int_sqrt_digit # Recursive function
+#------------------------------------------------------------------------------
+{
+ my ($n) = @_;
+
+ return $n if $n < 2;
+
+ my $small_cand = 2 * int_sqrt_digit( int( $n / 4 ) );
+ my $large_cand = $small_cand + 1;
+
+ return ($large_cand * $large_cand > $n) ? $small_cand : $large_cand;
+}
+
+#------------------------------------------------------------------------------
+sub parse_command_line
+#------------------------------------------------------------------------------
+{
+ my $args = scalar @ARGV;
+ $args == 1
+ or error( "Expected 1 command line argument, found $args" );
+
+ my $N = $ARGV[ 0 ];
+
+ $N =~ / ^ $RE{num}{int} $ /x
+ or error( qq["$N" is not a valid integer] );
+
+ $N > 0
+ or error( qq["$N" is not a positive integer] );
+
+ return $N;
+}
+
+#------------------------------------------------------------------------------
+sub error
+#------------------------------------------------------------------------------
+{
+ my ($message) = @_;
+
+ die "ERROR: $message\n$USAGE";
+}
+
+###############################################################################
diff --git a/challenge-133/athanasius/perl/ch-2.pl b/challenge-133/athanasius/perl/ch-2.pl
new file mode 100644
index 0000000000..4b2e4d5495
--- /dev/null
+++ b/challenge-133/athanasius/perl/ch-2.pl
@@ -0,0 +1,123 @@
+#!perl
+
+###############################################################################
+=comment
+
+Perl Weekly Challenge 133
+=========================
+
+TASK #2
+-------
+*Smith Numbers*
+
+Submitted by: Mohammad S Anwar
+
+Write a script to generate first 10 Smith Numbers in base 10.
+
+According to [ https://en.wikipedia.org/wiki/Smith_number |Wikipedia]:
+
+ In number theory, a Smith number is a composite number for which, in a
+ given number base, the sum of its digits is equal to the sum of the digits
+ in its prime factorization in the given number base.
+
+=cut
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=comment
+
+Algorithm
+---------
+Prime factors are found via a simple, brute-force search. This is inefficient,
+but quite fast enough for the given task.
+
+=cut
+#==============================================================================
+
+use strict;
+use warnings;
+use Const::Fast;
+
+const my $TARGET => 10;
+const my $USAGE => "Usage:\n perl $0\n";
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ $| = 1;
+ print "\nChallenge 133, Task #2: Smith Numbers (Perl)\n\n";
+}
+
+#==============================================================================
+MAIN:
+#==============================================================================
+{
+ my $args = scalar @ARGV;
+ $args == 0 or die 'ERROR: Expected 0 command line arguments, found ' .
+ "$args\n$USAGE";
+
+ my @smith;
+
+ for (my ($count, $n) = (0, 4); $count < $TARGET; ++$n)
+ {
+ if (is_smith( $n ))
+ {
+ push @smith, $n;
+ ++$count;
+ }
+ }
+
+ printf "The first %d Smith numbers: %s\n", $TARGET, join ', ', @smith;
+}
+
+#------------------------------------------------------------------------------
+sub is_smith
+#------------------------------------------------------------------------------
+{
+ my ($n) = @_;
+
+ my @prime_factors = prime_factors( $n );
+
+ return 0 unless scalar @prime_factors > 1; # Smith numbers are composite
+
+ my $factor_digit_sum = 0;
+
+ for (@prime_factors) # Sum the digits of the prime factors of $n
+ {
+ $factor_digit_sum += $_ for split //;
+ }
+
+ my $n_digit_sum = 0;
+ $n_digit_sum += $_ for split //, $n; # Sum the digits of $n
+
+ return $n_digit_sum == $factor_digit_sum;
+}
+
+#------------------------------------------------------------------------------
+sub prime_factors
+#------------------------------------------------------------------------------
+{
+ my ($n) = @_;
+ my $max_f = int sqrt $n;
+ my @prime_factors;
+
+ for (my $f = 2; $f <= $max_f && $n > 1; ++$f)
+ {
+ while ($n % $f == 0)
+ {
+ push @prime_factors, $f;
+ $n /= $f;
+ }
+ }
+
+ push @prime_factors, $n if $n > 1;
+
+ return @prime_factors;
+}
+
+###############################################################################
diff --git a/challenge-133/athanasius/raku/ch-1.raku b/challenge-133/athanasius/raku/ch-1.raku
new file mode 100644
index 0000000000..e11e1fe682
--- /dev/null
+++ b/challenge-133/athanasius/raku/ch-1.raku
@@ -0,0 +1,120 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 133
+=========================
+
+TASK #1
+-------
+*Integer Square Root*
+
+Submitted by: Mohammad S Anwar
+
+You are given a positive integer $N.
+
+Write a script to calculate the integer square root of the given number.
+
+Please avoid using built-in function. Find out more about it
+[ https://en.wikipedia.org/wiki/Integer_square_root |here].
+
+Examples
+
+ Input: $N = 10
+ Output: 3
+
+ Input: $N = 27
+ Output: 5
+
+ Input: $N = 85
+ Output: 9
+
+ Input: $N = 101
+ Output: 10
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Algorithm
+---------
+The solution is found using both Newton's method (aka Heron's method) and the
+digit-by-digit algorithm (recursive version) described in the Wikipedia article
+cited in the Task Description.
+
+=end comment
+#==============================================================================
+
+subset Positive of Int where * > 0;
+
+my Real constant $DBL-LOG2 = 1.386_294_361_119_890_618_834_464_242_916_4;
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ "\nChallenge 133, Task #1: Integer Square Root (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN
+(
+ Positive:D $N #= A positive integer
+)
+#==============================================================================
+{
+ "Input: \$N = $N".put;
+ "Output: %d (Newton's method)\n"\ .printf: int-sqrt-newton( $N );
+ " %d (digit-by-digit algorithm)\n".printf: int-sqrt-digit\( $N );
+}
+
+#------------------------------------------------------------------------------
+sub int-sqrt-newton( Positive:D $n --> Positive:D )
+#------------------------------------------------------------------------------
+{
+ # x0 = 2^(⎣log2(n) / 2⎦ + 1) gives a good starting value for x0 (see
+ # https://en.wikipedia.org/wiki/Integer_square_root#Numerical_example); but
+ # x0 = ($n / 2) + 1 is an acceptable (and simpler) alternative :-)
+
+ my Rat $x0 = (2 ** (floor( $n.log / $DBL-LOG2 ) + 1)).Rat;
+ my Rat $x1 = ($x0 + ($n / $x0)) / 2;
+
+ while $x1 < $x0
+ {
+ $x0 = $x1;
+ $x1 = (($x0 + ($n / $x0)) / 2).Rat;
+ }
+
+ return $x0.Int;
+}
+
+#------------------------------------------------------------------------------
+sub int-sqrt-digit( UInt:D $n --> UInt:D ) # Recursive function
+#------------------------------------------------------------------------------
+{
+ return $n if $n < 2;
+
+ my Positive $cand = (int-sqrt-digit( floor( $n / 4 ) ) * 2) + 1;
+
+ return ($cand * $cand > $n) ?? $cand - 1 !! $cand;
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+ my Str $usage = $*USAGE;
+
+ $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+
+ $usage.put;
+}
+
+##############################################################################
diff --git a/challenge-133/athanasius/raku/ch-2.raku b/challenge-133/athanasius/raku/ch-2.raku
new file mode 100644
index 0000000000..7dca0ffd64
--- /dev/null
+++ b/challenge-133/athanasius/raku/ch-2.raku
@@ -0,0 +1,124 @@
+use v6d;
+
+###############################################################################
+=begin comment
+
+Perl Weekly Challenge 133
+=========================
+
+TASK #2
+-------
+*Smith Numbers*
+
+Submitted by: Mohammad S Anwar
+
+Write a script to generate first 10 Smith Numbers in base 10.
+
+According to [ https://en.wikipedia.org/wiki/Smith_number |Wikipedia]:
+
+ In number theory, a Smith number is a composite number for which, in a
+ given number base, the sum of its digits is equal to the sum of the digits
+ in its prime factorization in the given number base.
+
+=end comment
+###############################################################################
+
+#--------------------------------------#
+# Copyright © 2021 PerlMonk Athanasius #
+#--------------------------------------#
+
+#==============================================================================
+=begin comment
+
+Algorithm
+---------
+Prime factors are found via a simple, brute-force search, which is inefficient,
+but fast enough for the given task. Advantage is taken of Raku's in-built
+is-prime() method to provide a small optimization.
+
+=end comment
+#==============================================================================
+
+my UInt constant $TARGET = 10;
+
+#------------------------------------------------------------------------------
+BEGIN
+#------------------------------------------------------------------------------
+{
+ "\nChallenge 133, Task #2: Smith Numbers (Raku)\n".put;
+}
+
+#==============================================================================
+sub MAIN()
+#==============================================================================
+{
+ my UInt @smith;
+
+ loop (my UInt ($count, $n) = (0, 4); $count < $TARGET; ++$n)
+ {
+ if is-smith( $n )
+ {
+ @smith.push: $n;
+ ++$count;
+ }
+ }
+
+ "The first %d Smith numbers: %s\n".printf: $TARGET, @smith.join: ', ';
+}
+
+#------------------------------------------------------------------------------
+sub is-smith( UInt:D $n --> Bool:D )
+#------------------------------------------------------------------------------
+{
+ my UInt @prime-factors = prime-factors( $n );
+
+ return False unless @prime-factors.elems > 1; # Smith nums are composite
+
+ my UInt $factor-digit-sum = 0;
+
+ for @prime-factors # Sum the digits of the prime factors of $n
+ {
+ $factor-digit-sum += $_ for .split: '', :skip-empty;
+ }
+
+ my UInt $n-digit-sum = 0;
+
+ $n-digit-sum += $_ for $n.split: '', :skip-empty; # Sum the digits of $n
+
+ return $n-digit-sum == $factor-digit-sum;
+}
+
+#------------------------------------------------------------------------------
+sub prime-factors( UInt:D $n is copy --> Array:D[UInt:D] )
+#------------------------------------------------------------------------------
+{
+ my UInt @prime-factors;
+ my UInt $max-f = $n.sqrt.floor;
+
+ loop (my UInt $f = 2; $f <= $max-f && $n > 1; ++$f)
+ {
+ next unless $f.is-prime;
+
+ while $n % $f == 0
+ {
+ @prime-factors.push: $f;
+ $n = ($n / $f).Int;
+ }
+ }
+
+ @prime-factors.push: $n if $n > 1;
+
+ return @prime-factors;
+}
+
+#------------------------------------------------------------------------------
+sub USAGE()
+#------------------------------------------------------------------------------
+{
+ my Str $usage = $*USAGE;
+
+ $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/;
+ $usage.put;
+}
+
+##############################################################################
generated by cgit (git 2.34.1) at 2026-05-24 21:53:24 +0000