RogerBW's Blog

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.