RogerBW's Blog

The Weekly Challenge 172: Partition of Five 07 July 2022

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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2022 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1