RogerBW's Blog

The Weekly Challenge 174: The Rank Smell of Disarium 20 July 2022

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.

See also:
Perl Weekly Challenge 54: permutations and Collatz

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 aviation 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 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 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 2022 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