Perl Weekly Challenge 172.
My solutions (task 1 and task 2 ) to the The 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 duplicates allowed.
For example,
Input: $m = 18, $n = 2
Output: 5, 13 or 7, 11
Input: $m = 19, $n = 3
Output: 3, 5, 11
I can use a recursive procedure that takes as arguments $m, $n and an array $p of primes, removing a prime from the array, substracting it from $m and decrementing $n until success ($m and $n reach zero) or failure. I may use Math::Primes::Util to generate the array. My first attempt is the following 4-liner
perl -MMath::Prime::Util=primes -E 'my ($m,$n)=@ARGV; my @p=@{primes($m)};
say "$m=". join "+", grep {$_>0} p($m,$n,\@p);sub p($m, $n, $a){
return $m==0?(0):() if $n==0; my @a=grep {$_<=$m} @$a; while(@a){
my $p=pop @a; my @r=p($m-$p, $n-1, \@a); return (@r, $p) if @r;} return ();}
' 19 3
Results:
19=3+5+11
It seems to work, but it returns at most one
partition. Therefore, I modify the recursive function p($m,
$n, $a) to return all partitions of $m into $n elements
of the set $a.
perl -MMath::Prime::Util=primes -E 'my ($m,$n)=@ARGV; my @p=@{primes($m)};
say "$m=". join "+", @$_ foreach p($m, $n, \@p);sub p($m, $n, $a){return $m==0?
([]):() if $n==0; my @a=grep {$_<=$m} @$a; my @f=(); while(@a){my $p=pop @a;
my @r=p($m-$p, $n-1, \@a); push @f, map {push @$_, $p; $_} @r if @r;}return @f;}
' 50 5
Results:
50=2+3+5+11+29
50=2+3+5+17+23
50=2+5+7+13+23
50=2+5+7+17+19
50=2+5+11+13+19
50=2+7+11+13+17
So it seems to work.
The full code is
1 # Perl weekly challenge 172
2 # Task 1: Prime partition
3 #
4 # See https://wlmb.github.io/2022/07/04/PWC172/#task-1-prime-partition
5 use v5.36;
6 use Math::Prime::Util qw(primes);
7 say("Usage: ./ch-1.pl M N\nto find the N-term prime partitions of M\n"), exit
8 unless @ARGV==2;
9 my ($m,$n)=@ARGV;
10 my @primes=@{primes($m)};
11 my @result= partitions($m,$n,\@primes);
12 say "$m=", join "+", @$_ foreach @result;
13 sub partitions($m, $n, $set){
14 # return all partitions of $m into $n elements of the ordered $set
15 return $m==0?([]):() if $n==0; # () means failure, ([]) means we are done
16 my @set=grep {$_<=$m} @$set; # remove high unneeded elements
17 my @results=();
18 while(@set){
19 my $element=pop @set; # try highest elements first
20 my @r=partitions($m-$element, $n-1, \@set);
21 push @results, map {push @$_, $element; $_} @r if @r;
22 }
23 return @results;
24 }
Example:
./ch-1.pl 50 5
Results:
50=2+3+5+11+29
50=2+3+5+17+23
50=2+5+7+13+23
50=2+5+7+17+19
50=2+5+11+13+19
50=2+7+11+13+17
Had I been more thoughtful, I could have guessed: I checked the
documentation of Math::Prime::Util and there it was, ready
for use, the function forpart, to produce partitions, yielding a true oneliner:
perl -MMath::Prime::Util=forpart -MList::Util=uniq -E '
($m, $n)=@ARGV; forpart {say "$m=", join "+",@_ if @_==uniq @_} $m, {n=>$n,prime=>1}' 50 5
Results:
50=2+3+5+11+29
50=2+3+5+17+23
50=2+5+7+13+23
50=2+5+7+17+19
50=2+5+11+13+19
50=2+7+11+13+17
I just had to remove partitions with duplicates. I can use this results to verify my programs above.
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 wikipedia
page.
The five number summary of a set of numbers is given by its minimum, lower quartile, median, upper quartile and maximum. The lower and upper quartiles are the medians of the first half and second half of the ordered data. There are various conventions about the definition of the first and second halfs. The one I use here excludes the median from both sets. To calculate the median we have to distinguish between an even and an odd number of elements in the set. If the number is odd, the median is the element at the center of the ordered array. If the number is even, then an arithmetic average is taken among the two centermost data points. This yields a three-liner:
perl -E '@a=sort {$a<=>$b} @ARGV; ($l, $h)=($a[0], $a[-1]); $m=c(@a);
$f=c(@a[0..(@a-2)/2]); $t=c(@a[(@a+1)/2..@a-1]); say "$l\n $f\n $m\n$t\n $h";
sub c(@d){@d%2?$d[(@d-1)/2]:($d[@d/2-1]+$d[@d/2])/2}
' 0 0 1 2 63 61 27 13
Results:
0
0.5
7.5
44
63
The full code is
1 # Perl weekly challenge 172
2 # Task 2: Five-number summary
3 #
4 # See https://wlmb.github.io/2022/07/04/PWC172/#task-1-five-number-summary
5 use v5.36;
6 say("Usage: ./ch-2.pl N1 N2...Nk\nto find the five-number summary of the sequence N1...Nk"), exit
7 unless @ARGV;
8 say("The sequence should have at least 2 elements"), exit unless @ARGV>=2;
9 my @data=sort {$a<=>$b} @ARGV;
10 my ($min, $max)=($data[0], $data[-1]);
11 my $median=median(@data);
12 my $q1=median(@data[0..(@data-2)/2]);
13 my $q3=median(@data[(@data+1)/2..@data-1]);
14 say join " ", "The five-number summary of ", @ARGV, "is";
15 say "min=$min, Q1=$q1, median=$median, Q3=$q3, max=$max";
16
17 sub median(@d){
18 @d%2?$d[(@d-1)/2]:($d[@d/2-1]+$d[@d/2])/2
19 }
Example:
./ch-2.pl 0 0 1 2 63 61 27 13
Results:
The five-number summary of 0 0 1 2 63 61 27 13 is
min=0, Q1=0.5, median=7.5, Q3=44, max=63
Other examples:
for i in 1 2 3 4 5 6 7; do echo; ./ch-2.pl `seq $i`; done
Results:
The sequence should have at least 2 elements
The five-number summary of 1 2 is
min=1, Q1=1, median=1.5, Q3=2, max=2
The five-number summary of 1 2 3 is
min=1, Q1=1, median=2, Q3=3, max=3
The five-number summary of 1 2 3 4 is
min=1, Q1=1.5, median=2.5, Q3=3.5, max=4
The five-number summary of 1 2 3 4 5 is
min=1, Q1=1.5, median=3, Q3=4.5, max=5
The five-number summary of 1 2 3 4 5 6 is
min=1, Q1=2, median=3.5, Q3=5, max=6
The five-number summary of 1 2 3 4 5 6 7 is
min=1, Q1=2, median=4, Q3=6, max=7
The values for the first and third quartiles of these sequences might look suspicious, but for such small data sets, they strongly depend on the convention adopted.