RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved number searching and binary manipulation. (Note that this ends today.)

Task 1: Absent Smallest Positive

You are given an array of integers.

Write a script to return the smallest absent positive integer such that it is strictly greater than the average of all elements in the given array.

Three helper variables here: tot the sum of the list, mul the length of the list, and ex a set of list members. (I avoid floating point by comparing candidate × list length to total, rather than candidate to total ÷ list length.)

Then I just try numbers from 1 upwards until I find one that passes the conditions. In Raku:

sub absentsmallestpositive(@a) {

Helper variables.

    my $tot = @a.sum;
    my %ex = Set(@a);
    my $mul = @a.elems;

Check each candidate.

    for (1 .. ∞) -> $n {
        if ($n * $mul > $tot && (%ex{$n}:!exists)) {
            return $n;
        }
    }
}

Task 2: Binary Reflection

You are given an array of integer.

Write a script to sort the given array in ascending order based on the binary reflection of each element. If two different numbers have the same binary reflection, the smaller original number should appear first.

Two parts to this: first, a binary reflection, for which I break out each bit and reassemble them in reverse order. Second, a two-stage sort.

There's a bug somewhere in my quicksort library code for PostScript. Iä!

In JavaScript:

function reflect(a) {
    let p = [];
    let am = a;

Break down the input into a bit array.

    while (true) {
        p.push(am % 2);
        am >>= 1;
        if (am == 0) {
            break;
        }
    }

Rebuild it reversed.

    let ar = 0;
    let s = p.length;
    for (let n of p) {
        s -= 1;
        ar += n << s;
    }
    return ar;
}

Build the liste of reflected values.

function binaryreflection(ax) {
    const k = ax.map(x => reflect(x));

Build a list of indices, which is what we'll actuall sort.

    let i = [];
    for (let n = 0; n < ax.length; n++) {
        i.push(n);
    }

Sort that with a custom function.

    i.sort(function(a, b) {

If the reflected values are equal, return the sort order of original values.

        if (k[a] == k[b]) {
            return ax[a] - ax[b];
        } else {

Otherwise return the sort order of reflected values.

            return k[a] - k[b];
        }
    });

Then map the original input list into that sorted order.

    return i.map(x => ax[x]);
}

Full code in all tagged languages is on codeberg.