laurent_r

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

Update July 05, 2022: Shortly after I published this post earlier today, it occurred to me that there is a simpler way to do it, using the Raku built-in combinations routine:

sub partition(Int $m, Int $n) {
    my $found = False;
    for (2..$m).grep({.is-prime}).combinations($n) -> $comb {
        say "$m $n: ", $comb and $found = True if $comb.sum == $m;
    }
    say "$m $n: no solution " unless $found;
}
for <18 2>, <19 3>, <17 3>, <25 2> -> $test {
    my @partition = partition($test[0], $test[1]);
}

This program displays the following output:

$ ./raku prime-partition2.raku
18 2: (5 13)
18 2: (7 11)
19 3: (3 5 11)
17 3: no solution
25 2: (2 23)

Note that we are now displaying all solutions, not just the first one.

Prime Partition in Perl

This is a port to Perl of the first 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

Prime Partition in Julia

In Julia, the Primes.primes function returns an iterable collection of prime numbers. And the Combinatoric package provides the combinations function, which does exactly what its name implies. With thezse two functions, the solution is very simple:

using Primes
using Combinatorics

function partition(m, n)
    for comb in combinations(primes(m),n)
        sum(comb) == m && println("$m $n: ", comb)
    end
end

partition(18,2)
partition(19, 3)
partition(25, 2)

Output:

$ julia ./prime-partition.jl
18 2: [5, 13]
18 2: [7, 11]## Task 2: Five-number Summary
19 3: [3, 5, 11]
25 2: [2, 23]*You are given an array of integers.*

Prime Partition in Python

Python also has combinations function, provided by the itertools package. We implement our own is_prime function.

import math
from itertools import combinations

def is_prime(n):
  if n == 2:
    return True
  if n == 0 or n == 1 or n % 2 == 0:
    return False
  p = 3
  sqrt_n = math.sqrt(n)
  while (p <= sqrt_n):
    if ((n % p) == 0):
      return False
    p += 2
  return True

def partition(m, n):
  primes = filter(is_prime, range (1, m))
  for combination in combinations(primes, n):
    if sum(combination) == m:
      print(m, n, ": ", combination)

partition(18, 2)
partition(19, 3)
partition(25, 2)

Output:

$ python3 prime-partition.py
18 2 :  (5, 13)
18 2 :  (7, 11)
19 3 :  (3, 5, 11)
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

Five-number Summary in Julia

The Statistics package provides a number of functions, including quantile that we are using here:

using Statistics

moons = sort([0, 0, 1, 2, 63, 61, 27, 13])

min = moons[1]  # Julia indices start at 1
first_quart = quantile(moons, 0.25)
median = quantile(moons, 0.5)
third_quart = quantile(moons, 0.75)
max = last(moons)

println("Min: $min; First quartile = $first_quart; Median: $median; Third quartile: $third_quart; Max: $max")

Output:

$ julia ./five-nums-summary.jl
Min: 0; First quartile = 0.75; Median: 7.5; Third quartile: 35.5; Max: 63

Five-number Summary in Python

def median(n):
  c = len(n)
  return n[int((c - 1) / 2)] if c % 2 != 0 else (n[int(c/2 -1)] + n[int(c/2)])/2


def summary(input):
  min = input[0]
  max = input[-1]
  med = median(input)
  lower_half = list(filter(lambda p: p < med, input))
  # print(lower_half)
  first_quart = median(lower_half)
  third_quart = median(list(filter(lambda p: p > med, input)))
  return(min, first_quart, med, third_quart, max)

moons = sorted([0, 0, 1, 2, 63, 61, 27, 13])
print(summary(moons));

Output:

$ python3 ./five-nums-summary.py
(0, 0.5, 7.5, 44.0, 63)

Five-number Summary in Ruby

def median(n)
    size = n.length
    if size %2 != 0
        n[(size + 1) / 2] 
    else
        (n[size/2] + n[size/2 + 1]) / 2.0
    end
end

def summary(n)
    min = n[0]
    max = n[-1]
    med = median(n)
    first_q = median( n.select { |i| i < med })
    last_q = median( n.select { |i| i > med })
    return min, first_q, med, last_q, max
end

moons = [0, 0, 1, 2, 63, 61, 27, 13]
print summary(moons.sort), "\n"

Output:

[0, 0.5, 7.5, 44.0, 63]

Five-number Summary in C

#include <stdio.h>
#include <stdlib.h>

int compare_int(const void *a,const void *b) {
    int *x = (int *) a;
    int *y = (int *) b;
    return *x - *y;
}

float median (int count, int m[]) {
    if (count % 2) {
        return 1.0 * m[(count -1)/2];
    } else {
        return (m[count/2 -1] + m[count/2])/2.0;
    }
}

int main() {
    int moons[] = {0, 0, 1, 2, 63, 61, 27, 13};
    int size = sizeof(moons)/sizeof(*moons);
    qsort (moons, size, sizeof(*moons), compare_int);
    float min = 1.0 * moons[0];
    float med = median(size, moons);
    int half = (int)size/2;
    float first_q = median(half, moons);
    float last_q = median(half, moons + 4);
    float max = 1.0 * moons[size - 1];
    printf ("%.2f %.2f %.2f %.2f %.2f", min, first_q, med, last_q, max);
    return 0;
}

Output:

0.00 0.50 7.50 44.00 63.00

Five-number Summary in Ring

Ring does not seem to have a filter (or grep) function and also doesn’t seem to have array slices. Or, if it has any of these two features, I did not find them in the documentation. In addition, Ring array indices start with 1. So, I managed manually the various ranges, but I must admit that, being used with array indices starting at 0, it took me quite a while to get the array index computations right.

moons = [0, 0, 1, 2, 63, 61, 27, 13]
see summary(sort(moons))

func summary(n)
    min = n[1]
    max = n[len(n)]
    size = len(n)
    med = median(1, size, n)
    first_q =  median(1, size/2, n)
    last_q = median(size/2 +1, size, n)
    return [min, first_q, med, last_q, max]

func median(low, high, n)
    if (high + low) % 2 = 0 
        return n[low + (high - low + 1)/2]
    else
        return (n[low + (high - low + 1)/2] + n[low + (high - low + 1)/2 - 1]) / 2.0
    ok

Output:

0
0.50
7.50
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.