RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved list sorting and permutation checking. (Note that this is open until 20 November 2022.)

Task 1: Twice Largest

You are given list of integers, @list.

Write a script to find out whether the largest item in the list is at least twice as large as each of the other items.

It's a truism that simply finding the largest value in a list is always quicker than sorting the list, but finding the two largest values would be more involved, and I'm not convinced that the extra code complexity would be worth any marginal performance gain. So instead I sort, and make a single comparison between the two largest values.

Raku:

sub twicelargest(@l0) {
    my @l = @l0.sort;
    return @l[*-1] >= 2*@l[*-2];
}

(The examples assume a +1/-1 return value, but I use booleans in the languages that support them.)

Task 2: Cute List

You are given an integer, 0 < $n <= 15.

Write a script to find the number of orderings of numbers that form a cute list.

With an input @list = (1, 2, 3, .. $n) for positive integer $n, an ordering of @list is cute if for every entry, indexed with a base of 1, either

1) $list[$i] is evenly divisible by $i 
or
2) $i is evenly divisible by $list[$i]

I see three basic approaches here. The most obvious is to use a standard permuting routine, look at each permutation one at a time, and check each place. (We can optimise a bit because the first place, i = 1, will never disqualify the sequence, so doesn't need to be checked – and similarly any time list[i] == 1.) This is quite slow.

Another approach turns this inside-out. Generate a list of permutations as before; then check each combination of place and number, and if it's a disqualifying one, filter the list to remove any entries that include it. This is, as it turns out, slightly slower (at least in Kotlin where I tried it).

Finally, I can abandon the permutation library and use my good old reliable non-recursive recursive search pattern, in this case configured as a depth-first search (i.e. pop rather than shift off the stack). In two parallel stacks I keep an ordered list of filled places so far (e.g. [1, 4, 3] and a list of candidates for the remaining places (e.g. [2, 5, 6, 7]). (I could calculate the latter from the former, of course, but these data sets aren't huge; if I were using this seriously I'd profile both approaches.) If the candidate list is empty and the list of filled places is long enough, that's a valid permutation; otherwise, I check whether each candidate can fit in the next place, and append to the stack a separate copy with each valid candidate appended (in this case only 2 is valid in position 4, so I'll push [1, 4, 3, 2] alongside new candidate list [5, 6, 7]. Thus for example I look at [1, 3] only once, reject it, and never bother to go any further down that branch of the permutation list. This gains me about two orders of magnitude over the first version at n = 10.

It's all a bit reminiscent of #174.1, disarium numbers, which similarly relied on early rejection to get any speed.

The resultant sequence is OEIS #A320843 which also suggests that there's no simpler way of generating these numbers.

In JavaScript:

function cutelist(n) {

tab is the lookup table: true values indicate a disqualifying combination (e.g. [2, 3]).

    let tab = [[false]];
    let t = [];
    for (let x = 1; x <= n; x++) {
        tab.push(new Array(n+1).fill(false));
        t.push(x);
    }
    for (let x = 1; x <= n; x++) {
        for (let y = 1; y <= x; y++) {
            if (x % y != 0 && y % x != 0) {
                tab[x][y] = true;
                tab[y][x] = true;
            }
        }
    }

Start the search loop.

    let count = 0;
    let stackl = [[]];
    let stackc = [t];
    while (stackl.length != 0) {
        let l = stackl.pop();
        let c = stackc.pop();

If we have an answer, count it.

        if (c.length == 0 && l.length == n)  {
            count++;
        } else {

Otherwise, for each candidate, place a new pair of stack entries.

            let place = l.length + 1;
            for (let candidate of c) {
                if (!tab[place][candidate]) {
                    let q = Array.from(l);
                    q.push(candidate);
                    stackl.push(q);
                    stackc.push(Array.from(c.filter(i => i != candidate)));
                }
            }
        }
    }
    return count;
}

For my test cases, I calculated with n = 2, 10 and 15. Timings (in seconds, on an unloaded machine, running twice in quick succession and timing the second, averaging 3 timed runs) were:

• 0.216 Rust (precompiled, optimised)
• 0.303 JavaScript (Node)
• 1.119 Kotlin on JVM (precompiled)
• 1.134 Python
• 1.546 Perl
• 1.793 Rust (including compile time, unoptimised)
• 2.203 Ruby
• 4.084 Lua
• 5.783 PostScript
• 6.657 Kotlin on JVM (including compile time)
• 18.296 Kotlin native
• 30.260 Kotlin native (including compile time)
• 34.150 Raku

I'm quite surprised by the poor performance of Kotlin native code here, though I suppose most of the optimisation work has gone into the JVM version. I'm impressed once again by JavaScript (which, in spite of its poor reputation, is possible to use pleasantly with the ES6 revisions). And oh dear Raku. Maybe newer versions are faster.

Full code on github.