I’ve been doing the Weekly
Challenges. The
latest
involved prime partitioning and some basic statistics. (Note that this is
open until 10 July 2022.)
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.
I find only one valid partition, but the code change to find all would
be trivial. I use my standard depth-first search pattern, last seen in
challenge 166 task 1. In Raku:
sub primepartition($n, $divs) {
Get a list of primes that may be elements in the partition.
my @pl = genprimes($n);
Start the depth-first search stack.
my @p = [[],];
while (@p.elems > 0) {
Pull a list of elements (which may be empty) off the stack.
my @pa = @p.pop.flat;
If it's the desired length,
if @pa.elems == $divs {
and it adds up to the right total,
if @pa.sum == $n {
return it. (To find all partitions, push this onto an output list instead.)
return @pa;
}
If it wasn't long enough,
} else {
make a set of every element that's already in it.
my $px = @pa.SetHash;
Then, for each possible element (in the list of primes),
for @pl -> $pq {
if it's not already in the set (which is quicker to check than the
list would be),
unless ($px{$pq}:exists) {
make a new list that consists of this list plus the new possible element,
my @pb = @pa.clone;
@pb.push($pq);
and put it on the stack for later consideration.
@p.push(@pb);
}
}
}
}
If we didn't find anything, return anyway.
return [$n];
}
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.
After a bit of hunting, I found that:
the five-number summary is the minimum, then the first quartile,
median, third quartile, and finally the maximum;
conventionally if the list being checked for a median has an even
number of elements the median is taken as the mean of the middle two
elements.
For the latter reason I do this one in floating point. Kotlin:
fun fivenumber(n0: List<Double>): ArrayList<Double> {
Start by sorting the input list:
var n = ArrayList(n0)
n.sort()
I'll be using this value a lot so stick it in a variable.
val nl = n.size - 1
The output list starts with the minimum.
var o = arrayListOf(n[0])
The median is just the second quartile, so calculate first second and
third. (I could do this for the zeroth and fourth quartile too, but
this seems neater.)
for (quartile in 1..3) {
val bx = quartile * nl
val base = bx / 4
base
is the integer part of the index of the median value.
var v = n[base]
If the index wasn't an integer, take the mean of the value at base
and the next one.
if (bx % 4 != 0) {
v = (n[base] + n[base+1]) / 2.0
}
o.add(v)
}
Finally, push on the last value.
o.add(n[n.size - 1])
return o
}
In PostScript I can eliminate some of those variables by building the
output list step by step with [ ]
and leaving values on the stack.
(quicksort
is from my existing code library.)
/fivenumber {
4 dict begin
/n exch quicksort def
/nl n length 1 sub def
[
n 0 get
1 1 3 {
nl mul /bx exch def
/base bx 4 idiv def
n base get
If I'm generating a mean, I can simply use the value left on the stack
as one of my inputs.
bx 4 mod 0 ne {
n base 1 add get add 2.0 div
} if
} for
n nl get
]
end
} bind def
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.