01 May 2026

Challenge 371

Missing Equilibria

• Task 1: Missing Letter
• Task 2: Subset Equilibrium

Task 1: Missing Letter

Submitted by: Reinier Maliepaard

---

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’).

Example 1

Input: $seq = qw(a c ? g i)
Output: e

The pattern of the sequence is +2,+2,+2,+2.
1: a
3: c
5: e
7: g
9: i

Example 2

Input: $seq = qw(a d ? j m)
Output: g

The pattern of the sequence is +3,+3,+3,+3.
1: a
4: d
7: g
10: j
13: m

Example 3

Input: $seq = qw(a e ? m q)
Output: i

The pattern of the sequence is +4,+4,+4,+4.
1: a
5: e
9: i
13: m
17: q

Example 4

Input: $seq = qw(a c f ? k)
Output: h

The pattern of the sequence is +2,+3,+2,+3.
1: a
3: c
6: f
8: h
11: k

Example 5

Input: $seq = qw(b e g ? l)
Output: j

The pattern of the sequence is +3,+2,+3,+2.
2: b
5: e
7: g
10: j
12: l

---

Solution

After converting the letters to their character encodings, this task may be considered as purely numeric.

We are given four numbers at four of the five index positions 0 .. 4 and we are looking for the value at the missing index. This task is always over-determined:
With the values at two index positions having an even distance we find the step size between every other elements and we can determine any value at index positions congruent to the first two modulo 2. An additional value at an index position having an odd distance to the first two provides the remaining index positions.

Any three indices within `0 .. 4` satisfy the above prerequisite and we never need a fourth value.

From four indices within 0 .. 4 we may always pick three that satisfy the above prerequisite and we never need a fourth value.

On the other hand this means that four values may be inconsistent for this task.

Therefore extending this task: Given at least three values as described can reproduce an arbitrary number of missing values. Some checks are required, though.

The task may be solved with these steps:

• find the number of given values at even and at odd index positions. The positions are valid if neither number is zero and there are at least three values given.
• find a pair of congruent indices modulo 2 with given values
• take the difference of the corresponding values and half the difference between the indices.
• if half the index difference does not evenly divide the value difference, the solution is not integer, i.e. there is no solution.
• find the two-step difference as the quotient of both values
• find an index not congruent modulo 2 with a given value.
• all points on a line, defined by a point \((x_0, y_0)\) and a slope \(m\), can be written as \(y = y_0 + m(x - x_0)\). Taking \(x_0\) from the first index of the pair or the other index such that these are congruent gives a formula for every index.

Using the vectorized operations from PDL, all values can be calculated simultaneously.

All generated values at positions with a given value must agree with these values. Otherwise the given values are inconsistent.

Finally, all generated values must fit into the code range from 'a' to 'z' and the missing values can be translated to their corresponding characters.

Consider e.g. missing_letter(qw(a ? ? ? k ? ? q)) which produces b f g l p.

Variations of example 4 are:

a c f ?   -> h
c f ? k   -> h
a c ? ? k -> f h

use strict;
use warnings;
use PDL;
use PDL::NiceSlice;

sub missing_letter {
    # difference between the elements of a two-value ndarray
    state sub pdiff {inner long(-1, 1), shift}

    # convert to code point and set question marks to BAD
    # get a mask of good values and create a sequence in the length of
    # $l
    my $l = long(map ord, @_)->setvaltobad(ord('?'));
    my $good = $l->isgood;
    my $seq = sequence $l;

    # sum of good indices mod 2, must not be zero or number of good
    # values.  Find a congruent pair mod 2.
    my $sum = ($seq->copybad($l) % 2)->sum;
    die "underdetermined" if $l->ngood < 3 || $sum == 0 || $sum == $l->ngood;
    my $sel = ($seq + ($sum > 1)) % 2;
    my $pair = which($good & !$sel)->(0:1);
    my $pair0 = $pair((0));

    # value diff and index diffs for the pair, find the step size
    my $vdiff = pdiff($l($pair));
    my $idiff = pdiff($pair) / 2;
    die "not integer" if $vdiff % $idiff;
    $vdiff /= $idiff;

    # find an index not congruent mod 2 to the pair
    my $other = which($good & $sel)->((0));

    # assign reference indices for all index positions, generate
    # the two lines and check consistency
    my $indx = indx($pair0, $other)->($sel);
    my $gen = $l($indx) + $vdiff * ($seq - $indx) / 2;
    die "conflict" if any $gen($good;?) != $l($good;?);

    # range check
    my ($min, $max) = minmax $gen;
    die "out of range" if $min < ord('a') || $max > ord('z');

    # back-transformation
    map chr, $gen(!$good;?)->list;
}

See the full solution to task 1.

Task 2: Subset Equilibrium

Submitted by: Mohammad Sajid Anwar

---

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.

Example 1

Input: @nums = (2, 1, 4, 3)
Output: (2, 1), (1, 4), (4, 3), (2, 3)

Subset 1: (2, 1)
Values: 2 + 1 = 3
Positions: 1 + 2 = 3

Subset 2: (1, 4)
Values: 1 + 4 = 5
Positions: 2 + 3 = 5

Subset 3: (4, 3)
Values: 4 + 3 = 7
Positions: 3 + 4 = 7

Subset 4: (2, 3)
Values: 2 + 3 = 5
Positions: 1 + 4 = 5

Example 2

Input: @nums = (3, 0, 3, 0)
Output: (3, 0), (3, 0, 3)

Subset 1: (3, 0)
Values: 3 + 0 = 3
Positions: 1 + 2 = 3

Subset 2: (3, 0, 3)
Values: 3 + 0 + 3 = 6
Positions: 1 + 2 + 3 = 6

Example 3

Input: @nums = (5, 1, 1, 1)
Output: (5, 1, 1)

Subset 1: (5, 1, 1)
Values: 5 + 1 + 1 = 7
Positions: 1 + 2 + 4 = 7

Example 4

Input: @nums = (3, -1, 4, 2)
Output: (3, 2), (3, -1, 4)

Subset 1: (3, 2)
Values: 3 + 2 = 5
Positions: 1 + 4 = 5

Subset 2: (3, -1, 4)
Values: 3 + (-1) + 4 = 6
Positions: 1 + 2 + 3 = 6

Example 5

Input: @nums = (10, 20, 30, 40)
Output: ()

---

Solution

There are some differences between my reading of the task and the examples. I haven’t tried to find an interpretation that fully reproduces the given results.

• The empty subset always fits. Suppressing this trivial solution.
• In example 1 the subset (2, 1, 4, 3) has a value sum and a position sum of 10 and thus qualifies as valid subset. As this is not a trivial solution, I’ll keep it in the result.
• In example 2 the subset (3) taken at index position 3 qualifies for the solution, too. I’ll keep it in the result.

Perl

Using Math::Prime::Util’s forcomb the solution becomes fairly simple.

use strict;
use warnings;
use Math::Prime::Util qw(vecsum forcomb);
use List::Gather;
use experimental 'signatures';

sub subset_eq (@nums) {
    gather {
        forcomb {
            take [@nums[@_]] if @_ && vecsum(@_) + @_ == vecsum(@nums[@_]);
        } @nums;
    };
}

See the full solution to task 2.

J

This is just a quick and dirty hack. Certainly there is a better solution.

Counting from 1 to \(2^n - 1\), convert to binary, use the binary digits as a mask for the array’s elements, compare their sum with the 1-based index sum and pick those with a match.

   subsetEq =: >@(>@] # [)/@|:@(] ([ (<@#~ (<@[ , [ <@=&(+/&>)  <@:>:@I.@]) ])"1 #&2@] #: >:@i.@<:@(2&^)@]) #)
   subsetEq 2 1 4 3
┌───┬───┬───┬───┬───────┐
│4 3│1 4│2 3│2 1│2 1 4 3│
└───┴───┴───┴───┴───────┘
   subsetEq 3 0 3 0
┌─┬───┬─────┐
│3│3 0│3 0 3│
└─┴───┴─────┘
   subsetEq 5 1 1 1
┌─────┐
│5 1 1│
└─────┘
   subsetEq 3 _1 4 2
┌───┬──────┐
│3 2│3 _1 4│
└───┴──────┘
   subsetEq 10 20 30 40