From 52c6c292577a84067bc22a5eb986dde78d65e154 Mon Sep 17 00:00:00 2001 From: PerlMonk-Athanasius Date: Sun, 10 Oct 2021 18:17:27 +1000 Subject: Perl & Raku solutions to Tasks 1 & 2 of the Perl Weekly Challenge #133 --- challenge-133/athanasius/perl/ch-1.pl | 150 ++++++++++++++++++++++++++++++++ challenge-133/athanasius/perl/ch-2.pl | 123 ++++++++++++++++++++++++++ challenge-133/athanasius/raku/ch-1.raku | 120 +++++++++++++++++++++++++ challenge-133/athanasius/raku/ch-2.raku | 124 ++++++++++++++++++++++++++ 4 files changed, 517 insertions(+) create mode 100644 challenge-133/athanasius/perl/ch-1.pl create mode 100644 challenge-133/athanasius/perl/ch-2.pl create mode 100644 challenge-133/athanasius/raku/ch-1.raku create mode 100644 challenge-133/athanasius/raku/ch-2.raku 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 + + 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; +} + +############################################################################## -- cgit