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.

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.