From b281b5ca880c478d71b9a44dfa5ed7f1edc0a653 Mon Sep 17 00:00:00 2001 From: PerlMonk-Athanasius Date: Sun, 10 Jul 2022 18:51:32 +1000 Subject: Perl & Raku solutions to Tasks 1 & 2 for Week 172 --- challenge-172/athanasius/perl/ch-1.pl | 146 ++++++++++++++++++++++ challenge-172/athanasius/perl/ch-2.pl | 210 ++++++++++++++++++++++++++++++++ challenge-172/athanasius/raku/ch-1.raku | 109 +++++++++++++++++ challenge-172/athanasius/raku/ch-2.raku | 193 +++++++++++++++++++++++++++++ 4 files changed, 658 insertions(+) create mode 100644 challenge-172/athanasius/perl/ch-1.pl create mode 100644 challenge-172/athanasius/perl/ch-2.pl create mode 100644 challenge-172/athanasius/raku/ch-1.raku create mode 100644 challenge-172/athanasius/raku/ch-2.raku diff --git a/challenge-172/athanasius/perl/ch-1.pl b/challenge-172/athanasius/perl/ch-1.pl new file mode 100644 index 0000000000..d233189e7c --- /dev/null +++ b/challenge-172/athanasius/perl/ch-1.pl @@ -0,0 +1,146 @@ +#!perl + +############################################################################### +=comment + +Perl Weekly Challenge 172 +========================= + +TASK #1 +------- +*Prime Partition* + +Submitted by: Mohammad S Anwar + +You are given two positive integers, $m and $n. + +Write a script to find out the Prime Partition of the given number. No dupli- +cates allowed. + +For example, + + Input: $m = 18, $n = 2 + Output: 5, 13 or 7, 11 + + Input: $m = 19, $n = 3 + Output: 3, 5, 11 + +=cut +############################################################################### + +#--------------------------------------# +# Copyright © 2022 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=comment + +Note +---- +If there are no prime partitions of the required size, the output field is left +blank. + +Algorithm +--------- +1. Find P, the set of all prime numbers <= m +2. For each n-combination C of the elements of P: + - find s, the sum of the elements of C + - if s = m, record C as a prime n-partition of m +3. Output the results + +Implementation +-------------- +1. Prime numbers between 2 and m are found using the primes() routine from the + CPAN module Math::Prime::Util (aka ntheory). +2. Combinations are found using the combinations() routine from the CPAN module + Algorithm::Combinatorics. + +Reference +--------- +[1] "Partition (number theory)", Wikipedia, + https://en.wikipedia.org/wiki/Partition_(number_theory) + +=cut +#============================================================================== + +use strict; +use warnings; +use Algorithm::Combinatorics qw( combinations ); +use Const::Fast; +use Math::Prime::Util qw( primes ); +use Regexp::Common qw( number ); + +const my $USAGE => +"Usage: + perl $0 + + Positive integer: the number to be partitioned + Positive integer: the number of partitions required\n"; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + $| = 1; + print "\nChallenge 172, Task #1: Prime Partition (Perl)\n\n"; +} + +#============================================================================== +MAIN: +#============================================================================== +{ + my ($m, $n) = parse_command_line(); + + print "Input: \$m = $m, \$n = $n\n"; + + my @prime_parts; + my $primes = primes( $m ); + + if ($n <= scalar @$primes) + { + my $iter = combinations( $primes, $n ); + + while (my $comb = $iter->next) + { + my $sum = 0; + $sum += $_ for @$comb; + + push @prime_parts, $comb if $sum == $m; + } + } + + printf "Output: %s\n", + join ', ', map { '(' . join( ', ', @$_ ) . ')' } @prime_parts; +} + +#------------------------------------------------------------------------------ +sub parse_command_line +#------------------------------------------------------------------------------ +{ + my $args = scalar @ARGV; + $args == 2 + or error( "Expected 2 command line arguments, found $args" ); + + my ($m, $n) = @ARGV; + + for my $i ($m, $n) + { + $i =~ / ^ $RE{num}{int} $ /x + or error( qq[Argument "$i" is not a valid integer] ); + + $i > 0 or error( qq[Argument "$i" is not positive] ); + } + + return ($m, $n); +} + +#------------------------------------------------------------------------------ +sub error +#------------------------------------------------------------------------------ +{ + my ($message) = @_; + + die "ERROR: $message\n$USAGE"; +} + +############################################################################### diff --git a/challenge-172/athanasius/perl/ch-2.pl b/challenge-172/athanasius/perl/ch-2.pl new file mode 100644 index 0000000000..10ff2a9ee5 --- /dev/null +++ b/challenge-172/athanasius/perl/ch-2.pl @@ -0,0 +1,210 @@ +#!perl + +############################################################################### +=comment + +Perl Weekly Challenge 172 +========================= + +TASK #2 +------- +*Five-number Summary* + +Submitted by: Mohammad S Anwar + +You are given an array of integers. + +Write a script to compute the five-number summary of the given set of integers. + +You can find the definition and example in the +[ https://en.wikipedia.org/wiki/Five-number_summary |wikipedia page]. + +=cut +############################################################################### + +#--------------------------------------# +# Copyright © 2022 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=comment + +Median +------ +For n data samples arranged in ascending numerical order: +- if n is odd, then the median is sample number (n+1)/2. +- if n is even, then the median is the average of sample number n/2 and sample + number (n/2)+1. [2] + +Quartiles +--------- +"For discrete distributions, there is no universal agreement on selecting the +quartile values." [3] The approach adopted here is as follows: + + "The lower quartile value is the median of the lower half of the data. + The upper quartile value is the median of the upper half of the data." [3] + +This leaves open the question of whether the median should be included in each +of the lower and upper halves. Set the constant $INCLUDE_MEDIAN as desired. + +References +---------- +[1] "Five-number summary", + Wikipedia, https://en.wikipedia.org/wiki/Five-number_summary +[2] "Median", Wikipedia, https://en.wikipedia.org/wiki/Median +[3] "Quartile", Wikipedia, https://en.wikipedia.org/wiki/Quartile + +=cut +#============================================================================== + +use strict; +use warnings; +use Const::Fast; +use Regexp::Common qw( number ); + +const my $INCLUDE_MEDIAN => 0; +const my $USAGE => +"Usage: + perl $0 [ ...] + + [ ...] A non-empty array of integers\n"; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + $| = 1; + print "\nChallenge 172, Task #2: Five-number Summary (Perl)\n\n"; +} + +#============================================================================== +MAIN: +#============================================================================== +{ + my @samples = parse_command_line(); + my @ordered = sort { $a <=> $b } @samples; + + my ($lower, $upper) = $INCLUDE_MEDIAN ? + quartiles_include_median( \@ordered ) : + quartiles_exclude_median( \@ordered ); + + printf "Input: %s\n\n" . + "Five-number Summary\n" . + "-------------------\n" . + "Sample minimum: %d\n" . + "Lower quartile: %.2f\n" . + "Median: %.1f\n" . + "Upper quartile: %.2f\n" . + "Sample maximum: %d\n", + join( ', ', @samples ), + $ordered[ 0 ], + $lower, + median( \@ordered ), + $upper, + $ordered[ -1 ]; +} + +#------------------------------------------------------------------------------ +sub median +#------------------------------------------------------------------------------ +{ + my ($samples) = @_; # Ordered (numerical ascending) + my $sample_size = scalar @$samples; + my $median; + + if ($sample_size % 2 == 0) # Even + { + my $mid = int( $sample_size / 2 ) - 1; + my $lower = $samples->[ $mid ]; + my $higher = $samples->[ $mid + 1 ]; + + $median = ($lower + $higher) / 2; + } + else # Odd + { + $median = $samples->[ int( ($sample_size + 1) / 2 ) - 1 ]; + } + + return $median; +} + +#------------------------------------------------------------------------------ +sub quartiles_exclude_median # "Method 1" from [3] +#------------------------------------------------------------------------------ +{ + my ($samples) = @_; # Ordered (numerical ascending) + my $sample_size = scalar @$samples; + my ($lower_end, $upper_start); + + if ($sample_size % 2 == 0) # Even + { + my $mid_point = $sample_size / 2; + $lower_end = $mid_point - 1; + $upper_start = $mid_point; + } + else # Odd + { + my $mid_point = ($sample_size - 1) / 2; + $lower_end = $mid_point - 1; + $upper_start = $mid_point + 1; + } + + my @lower_range = @$samples[ 0 .. $lower_end ]; + my @upper_range = @$samples[ $upper_start .. $#$samples ]; + + return (median( \@lower_range ), median( \@upper_range )); +} + +#------------------------------------------------------------------------------ +sub quartiles_include_median # "Method 2" from [3] (aka "Tukey's hinges") +#------------------------------------------------------------------------------ +{ + my ($samples) = @_; # Ordered (numerical ascending) + my $sample_size = scalar @$samples; + my ($lower_end, $upper_start); + + if ($sample_size % 2 == 0) # Even + { + my $mid_point = $sample_size / 2; + $lower_end = $mid_point - 1; + $upper_start = $mid_point; + } + else # Odd + { + my $mid_point = ($sample_size - 1) / 2; + $lower_end = $mid_point; + $upper_start = $mid_point; + } + + my @lower_range = @$samples[ 0 .. $lower_end ]; + my @upper_range = @$samples[ $upper_start .. $#$samples ]; + + return (median( \@lower_range ), median( \@upper_range )); +} + +#------------------------------------------------------------------------------ +sub parse_command_line +#------------------------------------------------------------------------------ +{ + scalar @ARGV > 0 + or error( 'No command line arguments found' ); + + for my $n (@ARGV) + { + $n =~ / ^ $RE{num}{int} $ /x + or error( qq[Argument "$n" is not a valid integer] ); + } + + return @ARGV; +} + +#------------------------------------------------------------------------------ +sub error +#------------------------------------------------------------------------------ +{ + my ($message) = @_; + + die "ERROR: $message\n$USAGE"; +} + +############################################################################### diff --git a/challenge-172/athanasius/raku/ch-1.raku b/challenge-172/athanasius/raku/ch-1.raku new file mode 100644 index 0000000000..0899084218 --- /dev/null +++ b/challenge-172/athanasius/raku/ch-1.raku @@ -0,0 +1,109 @@ +use v6d; + +############################################################################### +=begin comment + +Perl Weekly Challenge 172 +========================= + +TASK #1 +------- +*Prime Partition* + +Submitted by: Mohammad S Anwar + +You are given two positive integers, $m and $n. + +Write a script to find out the Prime Partition of the given number. No dupli- +cates allowed. + +For example, + + Input: $m = 18, $n = 2 + Output: 5, 13 or 7, 11 + + Input: $m = 19, $n = 3 + Output: 3, 5, 11 + +=end comment +############################################################################### + +#--------------------------------------# +# Copyright © 2022 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=begin comment + +Note +---- +If there are no prime partitions of the required size, the output field is left +blank. + +Algorithm +--------- +1. Find P, the set of all prime numbers <= m +2. For each n-combination C of the elements of P: + - find s, the sum of the elements of C + - if s = m, record C as a prime n-partition of m +3. Output the results + +Implementation +-------------- +1. Prime numbers between 2 and m are found by filtering integers in this range + using Raku's built-in is-prime() method. +2. Combinations are found using Raku's built-in combinations() method. + +Reference +--------- +[1] "Partition (number theory)", Wikipedia, + https://en.wikipedia.org/wiki/Partition_(number_theory) + +=end comment +#============================================================================== + +subset Pos of Int where * > 0; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + "\nChallenge 172, Task #1: Prime Partition (Raku)\n".put; +} + +#============================================================================== +sub MAIN +( + Pos:D $m, #= Positive integer: the number to be partitioned + Pos:D $n #= Positive integer: the number of partitions required +) +#============================================================================== +{ + "Input: \$m = $m, \$n = $n".put; + + my Pos @primes = (2 .. $m).grep: { .is-prime }; + my Array[Pos] @prime-partitions; + + for @primes.combinations: $n -> List $comb + { + my UInt $sum = [+] $comb; + + @prime-partitions.push: Array[Pos].new: |$comb if $sum == $m; + } + + "Output: %s\n".printf: + @prime-partitions.map( { '(' ~ .join( ', ' ) ~ ')' } ).join: ', '; +} + +#------------------------------------------------------------------------------ +sub USAGE() +#------------------------------------------------------------------------------ +{ + my Str $usage = $*USAGE; + + $usage ~~ s/ ($*PROGRAM-NAME) /raku $0/; + + $usage.put; +} + +############################################################################### diff --git a/challenge-172/athanasius/raku/ch-2.raku b/challenge-172/athanasius/raku/ch-2.raku new file mode 100644 index 0000000000..6e773bf073 --- /dev/null +++ b/challenge-172/athanasius/raku/ch-2.raku @@ -0,0 +1,193 @@ +use v6d; + +############################################################################### +=begin comment + +Perl Weekly Challenge 172 +========================= + +TASK #2 +------- +*Five-number Summary* + +Submitted by: Mohammad S Anwar + +You are given an array of integers. + +Write a script to compute the five-number summary of the given set of integers. + +You can find the definition and example in the +[ https://en.wikipedia.org/wiki/Five-number_summary |wikipedia page]. + +=end comment +############################################################################### + +#--------------------------------------# +# Copyright © 2022 PerlMonk Athanasius # +#--------------------------------------# + +#============================================================================== +=begin comment + +Median +------ +For n data samples arranged in ascending numerical order: +- if n is odd, then the median is sample number (n+1)/2. +- if n is even, then the median is the average of sample number n/2 and sample + number (n/2)+1. [2] + +Quartiles +--------- +"For discrete distributions, there is no universal agreement on selecting the +quartile values." [3] The approach adopted here is as follows: + + "The lower quartile value is the median of the lower half of the data. + The upper quartile value is the median of the upper half of the data." [3] + +This leaves open the question of whether the median should be included in each +of the lower and upper halves. Set the constant $INCLUDE-MEDIAN as desired. + +References +---------- +[1] "Five-number summary", + Wikipedia, https://en.wikipedia.org/wiki/Five-number_summary +[2] "Median", Wikipedia, https://en.wikipedia.org/wiki/Median +[3] "Quartile", Wikipedia, https://en.wikipedia.org/wiki/Quartile + +=end comment +#============================================================================== + +my Bool constant $INCLUDE-MEDIAN = False; + +#------------------------------------------------------------------------------ +BEGIN +#------------------------------------------------------------------------------ +{ + "\nChallenge 172, Task #2: Five-number Summary (Raku)\n".put; +} + +#============================================================================== +sub MAIN +( + #= A non-empty array of integers + + *@samples where { +@samples > 0 && .all ~~ Int:D } +) +#============================================================================== +{ + my Int @ordered = @samples.sort; + my Real ($lower, $upper) = $INCLUDE-MEDIAN ?? + quartiles-include-median( @ordered ) !! + quartiles-exclude-median( @ordered ); + + ("Input: %s\n\n" ~ + "Five-number Summary\n" ~ + "-------------------\n" ~ + "Sample minimum: %d\n" ~ + "Lower quartile: %.2f\n" ~ + "Median: %.1f\n" ~ + "Upper quartile: %.2f\n" ~ + "Sample maximum: %d\n").printf: + @samples.join( ', ' ), + @ordered[ 0 ], + $lower, + median( @ordered ), + $upper, + @ordered[ *-1 ]; +} + +#------------------------------------------------------------------------------ +sub median( *@samples where { +@samples > 0 && .all ~~ Int:D } --> Real:D ) +#------------------------------------------------------------------------------ +{ + my UInt $sample-size = +@samples; + my Real $median; + + if $sample-size %% 2 # Even + { + my Int $mid = ($sample-size / 2).Int - 1; + my Int $lower = @samples[ $mid ]; + my Int $higher = @samples[ $mid + 1 ]; + + $median = ($lower + $higher) / 2; + } + else # Odd + { + $median = @samples[ (($sample-size + 1) / 2).Int - 1 ]; + } + + return $median; +} + +#------------------------------------------------------------------------------ +sub quartiles-exclude-median # "Method 1" from [3] +( + @samples where { +@samples > 0 && .all ~~ Int:D } +--> List:D[Real:D] +) +#------------------------------------------------------------------------------ +{ + my UInt $sample-size = +@samples; + my Real ($lower-end, $upper-start); + + if $sample-size %% 2 # Even + { + my Real $mid-point = $sample-size / 2; + $lower-end = $mid-point - 1; + $upper-start = $mid-point; + } + else # Odd + { + my Real $mid-point = ($sample-size - 1) / 2; + $lower-end = $mid-point - 1; + $upper-start = $mid-point + 1; + } + + my Int @lower-range = @samples[ 0 .. $lower-end ]; + my Int @upper-range = @samples[ $upper-start .. @samples.end ]; + + return median( @lower-range ), median( @upper-range ); +} + +#------------------------------------------------------------------------------ +sub quartiles-include-median # "Method 2" from [3] (aka "Tukey's hinges") +( + @samples where { +@samples > 0 && .all ~~ Int:D } +--> List:D[Real:D] +) +#------------------------------------------------------------------------------ +{ + my UInt $sample-size = +@samples; + my Real ($lower-end, $upper-start); + + if $sample-size %% 2 # Even + { + my Real $mid-point = $sample-size / 2; + $lower-end = $mid-point - 1; + $upper-start = $mid-point; + } + else # Odd + { + my Real $mid-point = ($sample-size - 1) / 2; + $lower-end = $mid-point; + $upper-start = $mid-point; + } + + my Int @lower-range = @samples[ 0 .. $lower-end ]; + my Int @upper-range = @samples[ $upper-start .. @samples.end ]; + + return median( @lower-range ), median( @upper-range ); +} + +#------------------------------------------------------------------------------ +sub USAGE() +#------------------------------------------------------------------------------ +{ + my Str $usage = $*USAGE; + + $usage ~~ s:g/ ($*PROGRAM-NAME) /raku $0/; + + $usage.put; +} + +############################################################################### -- cgit