RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved keyed sorting and digit searching. (Note that this ends today.)

Task 1: Sort Language

You are given two array of languages and its popularity.

Write a script to sort the language based on popularity.

This is basically a sort by external key, but we have a separate list of sort keys rather than a mapping function. Building a hashmap would be one way to do it, but that fails if any key values are non-unique; so instead I take a third list, of indices into the other two. Sort the indices by the popularity value of each, then output a map of the language name for each index. Some similarity to last week's 244.1, in that the last line tends to be a map and return.

My PostScript library already has a ".with_keylist" mode for its sort routines, which does all the work this behind the scenes.

/sortlanguage {
    quicksort.with_keylist
} bind def

But more conventionally in JavaScript:

function sortlanguage(langs, popularities) {
    let ix = Array(langs.length).fill().map((element, index) => index);
    ix.sort(function(a,b) {
        return popularities[a] - popularities[b];
    });
    return ix.map(n => langs[n]);
}

Task 2: Largest of Three

You are given an array of integers >= 0.

Write a script to return the largest number formed by concatenating some of the given integers in any order which is also multiple of 3.

There's an efficiency gain to be had in the specific constraints of the problem, since the divisibility test is by 3: any set of base-10 digits will preserve its divisibility 3 regardless of its order. And the maximum value of that set will be the one with the highest digits first. So those are the only permutations we need to look at. As with 244 task 2 last week, I pre-sort the digit array (in this case I want it descending), then test each combination at each length.

A modularity test is probably slower than a comparison, so I do the comparison first; languages which short-circuit get the chance to do so.

I thought about bailing out after the length at which the first candidate max value is found, but what about (2, 3)? No two-digit combination is divisible by 3, but at least one one-digit combination is.

Raku:

sub largestofthree(@digits) {
    my @ordered = @digits.sort({$^b <=> $^a});
    my $mx = 0;
    for (0 .. @ordered.end).reverse -> $n {
        for combinations(@ordered, $n + 1) -> @c {
            my $t = 0;
            for @c -> $d {
                $t *= 10;
                $t += $d;
            }
            if ($t > $mx && $t % 3 == 0) {
                $mx = $t;
            }
        }
    }
    return $mx;
}

Full code on github.