RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved pattern matching and a subset search. (Note that this ends today.)

Task 1: Missing Letter

You are given a sequence of 5 lowercase letters, with one letter replaced by '?'. Each letter maps to its position in the alphabet ('a = 1', 'b = 2', …, 'z = 26'). The sequence follows a repeating pattern of step sizes between consecutive letters. The pattern is either a constant step (e.g., '+2, +2, +2, +2') or a simple alternating pattern of two distinct steps (e.g., '+2, +3, +2, +3').

The first type of pattern is of course a special case of the second…

In Raku:

sub missingletter($a) {

Split up the letters into character codes.

    my @c = $a.split(" ").grep({$_ ne ""}).map({$_.ord});

Built a list of differences between successive letters. (0 if either of them is the "?".)

    my @d;
    for @c.rotor(2 => -1) -> @i {
        if (@i[0] == 63 || @i[1] == 63) {
            @d.push(0);
        } else {
            @d.push(@i[1] - @i[0]);
        }
    }

Look through that list for the (first) zero difference.

    for @d.kv -> $n, $delta {
        if ($delta == 0) {
            my $ch;

If we're near the start of the list, count backward from two characters later.

            if ($n < 2) {
                $ch = @c[$n + 2] - @d[$n + 2];

Otherwise, count forward from the previous character.

            } else {
                $ch = @c[$n] + @d[$n - 2];
            }
            return $ch.chr;
        }
    }
    "";
}

Task 2: Subset Equilibrium

You are given an array of numbers.

Write a script to find all subsets where the sum of elements equals the sum of their indices.

(Indices are 1-based here.)

Rather than compare the two separate sums a shown in the examples, I build a single list of the differences between value and position: a 2 at index 3 would produce a -1, for example. Then I'll just add up the selected members of that list and check that the total is zero. Not that any of this is very computationally expensive, but I think this minimises what happens inside the combinatorial loop.

I modified the test cases to put the subsets in list-sorted order, which some languages have as standard and others don't. (To compare two lists: compare the elements at each index in turn until you get two that aren't equal.)

Kotlin doesn't have list sorting. Or combinations, but I've written that code before and won't include it here.

fun subsetequilibrium(a: List<Int>): List<List<Int>> {
    var out = ArrayList<List<Int>>()

Build the differences list.

    val b = a.withIndex().map { (i, x) -> x - i - 1 }.toList()

Build the list of indices.

    val ix = (0 .. b.size - 1).toList()

Check all valid combination sizes from 1 to one less than the list length.

    for (n in 1 .. b.size - 1) {

And generate all valid combinations for that size.

        for (iyx in combinations(ix, n)) {

Put the indices in order (this doesn't happen automatically with my combination generator).

            val iy = iyx.sorted()

Work out the sum of differences, which is the same as the difference of sums that we're checking.

            val bp = iy.map { i -> b[i] }.sum()

If that's zero, build the list of elements and put it on the output list..

            if (bp == 0) {
                val ap = iy.map{i -> a[i]}.toList()
                out += ap
            }
        }
    }

Now put the output list of lists in order. Look through each element to find one that differs. Note that this code is longer than the code, above, to solve the actual problem.

    val customComparator = Comparator {
        i: List<Int>, j: List<Int> ->
            val kx = listOf(i.size, j.size).minOrNull()!!
        var k = 0
        while (k < kx - 1) {
            if (i[k] == j[k]) {
                k += 1
            } else {
                break;
            }
        }
        val cmp = i[k] - j[k]
        if (cmp < 0) {
            -1
        } else if (cmp > 0) {
            1
        } else {
            0
        }
    }
    return out.sortedWith(customComparator).toList()
}

Crystal does have list-sorted order. Also Ruby, Raku, Rust and Typst.

Full code on codeberg.