Джерело:
blogs.perl.org
Дата публікації:
05/07/2022 23:49
Постійна адреса новини:
http://www.vsinovyny.com/9138235
Perl Weekly Challenge 172: Prime Partition and Five-Number Summary
05/07/2022 23:49 // blogs.perl.org
These are some answers to the Week 172 of the Perl Weekly Challenge organized by Mohammad S. Anwar.
Spoiler Alert: This weekly challenge deadline is due in a few of days from now (on July 10, 2022 at 23:59). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.
Task 1: Prime Partition
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
The task description doesn’t say what a prime partition is. In mathematics, a partition of a positive integer n is usually a way of writing n as a sum of positive integers. We can assume that a prime partition is a partition made of only prime numbers. This is confirmed by the examples. From the examples, we can also infer that the second integer $n is the number of (prime) integers whose sum should be equal to $m. Also, the first example has two solutions (5, 13 or 7, 11). To me, this means that either solution is valid. So, I won’t bother to display all solutions when there is more than one, but will stop searching as soon as one solution has been found. Finally, since duplicates are not allowed, there will be some input values for which there is no solution. For example, for the input integers (17, 3): 17 could be considered as the sum of 3 primes, 13, 2, 2, but this isn’t a valid solution because of the duplicate 2 values. It is quite easy to check manually that there is no valid solution.
Prime Partition in Raku
We implement a recursive partition subroutine. If the second parameter ($n) is larger than 2, then partition subroutine loops through a list of prime number and calls itself recursively with a second parameter of $n - 1. If the second parameter is 2, then we stop recursion and find the solution (if any).
my @primes = grep { .is-prime }, 1..100;
my %seen;
sub partition (Int $m, Int $n) {
return if $n < 2;
if $n == 2 {
for @primes -> $i {
last if $i >= $m;
my $j = $m - $i;
next if $j == $i;
next if %seen{$i} or %seen{$j};
return $i, $j if $j.is-prime;
}
return;
} else {
for @primes -> $i {
last if $i >= $m;
%seen = $i => True;
my @sub-partition = partition($m - $i, $n-1);
next if @sub-partition.elems < 2;
return ($i, @sub-partition).flat;
}
return;
}
}
for <18 2>, <19 3>, <17 3>, <25 2> -> $test {
my @partition = partition($test[0], $test[1]);
say @partition.elems < 2 ?? "$test: No solution" !! "Solution for $test: @partition[]";
}
With the four input tests provided, this program displays the following output:
$ raku ./prime-partition.raku
Solution for 18 2: 5 13
Solution for 19 3: 3 5 11
17 3: No solution
Solution for 25 2: 2 23
Prime Partition in Perl
This is a port to Perl of the Raku program above. The only significant difference is that we had to implement our own is_prime subroutine.
use strict;
use warnings;
use feature "say";
my @primes = grep { is_prime($_) } 1..100;
my %seen;
sub is_prime {
my $n = shift;
return 1 if $n == 2;
return 0 if $n % 2 == 0;
return 0 if $n == 1;
my $p = 3;
my $sqrt = sqrt $n;
while ($p <= $sqrt) {
return 0 if $n % $p == 0;
$p += 2;
}
return 1;
}
sub partition {
my ($m, $n) = @_;
return if $n < 2;
if ($n == 2) {
for my $i (@primes) {
last if $i >= $m;
my $j = $m - $i;
next if $j == $i;
next if $seen{$i} or $seen{$j};
return $i, $j if is_prime($j);
}
return;
} else {
for my $i (@primes) {
last if $i >= $m;
%seen = ($i => 1);
my @sub_partition = partition($m - $i, $n-1);
next if @sub_partition < 2;
return ($i, @sub_partition);
}
return;
}
}
for my $test ([18, 2], [19, 3], [17, 3], [25, 2]) {
my @partition = partition(@$test);
say @partition < 2 ? "@$test: No solution" : "Solution for @$test: @partition";
}
This program displays the following results:
$ perl ./prime-partition.pl
Solution for 18 2: 5 13
Solution for 19 3: 3 5 11
17 3: No solution
Solution for 25 2: 2 23
Task 2: Five-number Summary
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 is a set of descriptive statistics that provides information about a dataset. It consists of the five most important sample percentiles:
- the sample minimum (smallest observation)
- the lower quartile or first quartile
- the median (the middle value)
- the upper quartile or third quartile
- the sample maximum (largest observation)
Intuitively, with a sorted data set, the median is the middle value separating the greater and lesser halves of the set. If the input set has an odd number of items, the median is the middle value. With an even number of items, the median is usually computed as the arithmetic mean of the two middle values.
The lower quartile or first quartile is the value such that one quarter (or 25%) of the items are smaller and three quarters (75%) are larger. It is the median of the lower half of the sorted dataset. And the upper or third quartile is the median of the upper half, i.e. a value such that three quarters are larger and one quarter larger. Having said that, I must add that, as often, the devil hides in the details. Depending on whether or not we include the median in the two halves, we might obtain different results, and there is no universal agreement on selecting the quartile values. This Wikipedia page lists four different methods for computing the quartiles (and, for some data sets, they will compute different results). So, it is sort of your draw, you may pick the method you prefer.
Five-number Summary in Raku
We implement a median subroutine to compute the median of a data set. As noted above, there are two formulas to compute the median, depending on whether the number of elements if even or odd. Note that our median subroutine relies on the fact that its input data has been previously sorted in ascending order (in the summary subroutine). Note that the median subroutine is used three times (to compute the median, or course, but also to compute the lower and upper quartiles).
The test data set is the set of observations of the number of moons for each planet in the solar system: 0, 0, 1, 2, 63, 61, 27, 13, as provided in the Wikipedia page on the five-number summary.
sub median (@in) { # input values must have been sorted
my $count = @in.elems;
if $count %% 2 {
return (@in[$count/2 -1] + @in[$count/2])/2;
} else {
return @in[($count - 1) / 2];
}
}
sub summary (@input) {
my @in = sort @input;
my $min = @in[0];
my $max = @in[*-1];
my $median = median(@in);
my $first-quart = median( grep { $_ < $median}, @in);
my $third-quart = median( grep { $_ > $median}, @in);
return $min, $first-quart, $median, $third-quart, $max;
}
my @moons = 0, 0, 1, 2, 63, 61, 27, 13;
say summary(@moons);
This program displays the following output:
$ raku ./five-nums-summary.raku
(0 0.5 7.5 44 63)
Five-number Summary in Perl
This is a port to Perl of the Raku program just above. Please refer to the previous section for further explanations.
use strict;
use warnings;
use feature "say";
sub median {
my @in = @_; # Input values have been sorted previously
my $count = scalar @in;
if ($count % 2) {
return $in[($count - 1) / 2];
} else {
return ($in[$count/2 -1] + $in[$count/2])/2;
}
}
sub summary {
my @in = sort { $a <=> $b } @_;
my $min = $in[0];
my $max = $in[-1];
my $median = median(@in);
my $first_quart = median( grep { $_ < $median} @in);
my $third_quart = median( grep { $_ > $median} @in);
return $min, $first_quart, $median, $third_quart, $max;
}
my @moons = (0, 0, 1, 2, 63, 61, 27, 13);
say join " ", summary(@moons);
This program displays the following output:
$ perl ./five-nums-summary.pl
0 0.5 7.5 44 63
Wrapping up
The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on July 17, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.
| « |
Наступна новина з архіву Під час грози на Львівщині оголосили повітряну тривогу |
Попередня новина з архіву Зеленського просять заборонити очне навчання в школах до завершення війни |
» | |
|
|
||||