I’ve been doing the Weekly
Challenges. The
latest
involved disarium numbers and ranked permutations. (Note that this is
open until 24 July 2022.)
No Lua this week. I lost heart. Its 1-based indices and lack of
proper hash support just made both problems feel too much like hard
work. I'll probably come back to it next time.
Task 1: Disarium Numbers
Write a script to generate first 19 Disarium Numbers.
A disarium number is an integer for which the sum of each digit,
raised to the power of its position in the number, is equal to the
number.
i.e. 5¹ + 1² + 8³ = 518.
This is clearly a matter of searching, but some optimisations are
possible: most obviously, one can pre-compute all the digit powers.
That's what I did for these answers. If you want to find the 20th
number (which is 20 digits long) in reasonable time, you need more
optimisations; the code I found
here
prunes based on partial numbers so that whole blocks can be skipped,
and I've ported it to Rust but not the other languages.
Here are the timings to find 19 numbers in various languages. Note
that this includes compilation time where appropriate; compiled Rust
with the optimiser turned on finds 19 in less than a millisecond.
- JavaScript: 0.474s
- Python: 6.30s
- Kotlin: 6.38s
- Rust: 7.20s
- Perl: 7.80s
- Ruby: 10.9s
- PostScript: 19.9s
- Raku: 76.5s
(Raku is 6.d running on Rakudo v2020.12, Debian/stable.)
I'm jolly impressed with Node.js here, which isn't normally much of a
speed demon.
The Raku version is typical:
sub disarium($ct) {
my @o;
Set up the first list of digit powers.
my @pows;
@pows.push([(1 xx 10)».List.flat]);
Loop over candidates.
my $c = 0;
while (True) {
In the special case of c = 0
, just skip all the calculation.
my $disar = 0;
if $c > 0 {
Break down the number into a series of individual digits.
my $ca = $c;
my @cl;
my $tx = 0;
while ($ca > 0) {
$tx++;
@cl.push($ca % 10);
$ca div= 10;
}
@cl = @cl.reverse;
If we've got more digits than the power table can support, expand it
by multiplying up the previous row. (This will happen at 1, 10, 100,
etc.)
if ($tx >= @pows.elems) {
for @pows.elems..$tx -> $power {
my @row;
for 0..9 -> $digit {
@row.push(@pows[$power-1][$digit] * $digit);
}
@pows.push(@row);
}
}
Then add up all the relevant digit powers.
for 0..@cl.end -> $i {
$disar += @pows[$i+1][@cl[$i]];
}
}
(In PostScript the key line there is
/disar disar pows i 1 add get cl i get get add def
which I rather like.)
And if the number matches, push it onto the output list.
if ($disar == $c) {
@o.push($c);
if (@o.elems >= $ct) {
last;
}
}
$c++;
}
return @o;
}
Task 2: Permutation Ranking
You are given a list of integers with no duplicates, e.g.
[0, 1, 2]
.
Write two functions, permutation2rank
which will take the list and
determine its rank (starting at 0) in the set of possible
permutations arranged in lexicographic order, and rank2permutation
which will take the list and a rank number and produce just that
permutation.
In other words, dig into the ordered list of permutations and locate a
specific result. The neat thing here is that we don't actually need to
calculate all the other permutations; we can just break down the rank
based on a factorial number
system, and
the value in each place is the index into the unused entries. (I
learned this after I'd worked out the technique. Indeed, I had
forgotten that I'd done something similar for challenge #54.)
Testing only on 3-permutations can leave some bugs undetected, so I
set up 4-permutations too:
00: [0, 1, 2, 3]
01: [0, 1, 3, 2]
02: [0, 2, 1, 3]
03: [0, 2, 3, 1]
04: [0, 3, 1, 2]
05: [0, 3, 2, 1]
06: [1, 0, 2, 3]
07: [1, 0, 3, 2]
08: [1, 2, 0, 3]
09: [1, 2, 3, 0]
10: [1, 3, 0, 2]
11: [1, 3, 2, 0]
12: [2, 0, 1, 3]
13: [2, 0, 3, 1]
14: [2, 1, 0, 3]
15: [2, 1, 3, 0]
16: [2, 3, 0, 1]
17: [2, 3, 1, 0]
18: [3, 0, 1, 2]
19: [3, 0, 2, 1]
20: [3, 1, 0, 2]
21: [3, 1, 2, 0]
22: [3, 2, 0, 1]
23: [3, 2, 1, 0]
In JavaScript:
function permutation2rank(perm) {
let n = 0;
Get the sorted list.
let pp = [...perm];
pp.sort(function(a,b) {
return a-b;
});
Build the factorial bases (1, 2, 6, 24, etc.)
let oi = [];
let l = 1;
for (let index = 2; index <= perm.length; index++) {
oi.push(l);
l *= index;
}
oi.reverse();
For each step, build a map that links the remaining digits to their
position in the sorted list.
for (let index=0; index <= perm.length-2; index++) {
let base = new Map();
for (let i=0; i < pp.length; i++) {
base.set(pp[i],i);
}
Then add to the rank value the factorial base for this position
multiplied by that value.
n += oi[index] * base.get(perm[index]);
Remove that digit, and sort the remaining ones for the next pass.
(Probably it would be more efficient to filter, as I'll do below. This
is a Perl-flavoured answer; it might indeed be computationally cheaper
not to use the hash at all but just to search for the one value I
want.)
base.delete(perm[index]);
pp = [...base.keys()];
pp.sort(function(a,b) {
return a-b;
});
}
return n;
}
rank2permutation
is very similar, except I don't need the place lookups.
function rank2permutation(perm, rank0) {
let rank = rank0;
let pp = [...perm];
pp.sort(function(a,b) {
return a-b;
});
let o = [];
let oi = [];
let l = 1;
for (let index = 2; index <= perm.length; index++) {
oi.push(l);
l *= index;
}
oi.reverse();
Instead, for each place, work out the index from the factorial number,
and append that to the output – then remove that from the list.
for (let index=0; index <= perm.length-2; index++) {
let ix = Math.floor(rank / oi[index]);
o.push(pp[ix]);
pp = pp.filter(x => x != pp[ix]);
rank %= oi[index];
}
Rather than making one final pass, just push the last entry onto the
list.
o.push(pp[0]);
return o;
}
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.