RogerBW's Blog

The Weekly Challenge 191: Large but Cute 20 November 2022

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.

See also:
The Weekly Challenge 174: The Rank Smell of Disarium

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 advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech 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 crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 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 2021 hugo 2022 hugo 2023 hugo 2024 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 mpd 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 scala 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