RogerBW's Blog

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.