Weekly Challenge: Question the bits

Weekly Challenge 371

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. Unless otherwise stated, Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Missing Letter

Task

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

My solution

Given this is the first task (which is usually more straight forward), my first solution was massively over engineered.

After thinking about it, I came up with the solution that is better. As a bit of an explanation, the ord function (in both Python and Perl) will convert a character to it's character number (for English characters it's ASCII code). ord("a") is 97. The chr function does the opposite, converting a character number to a letter. chr(97) is a.

I start by checking that there is four lower case letters and one question mark.

def missing_letter(seq: list[str]) -> str:
    if (
        len(seq) != 5 or
        seq.count("?") != 1 or
        any(s not in string.ascii_lowercase+"?" for s in seq)
    ):
        raise ValueError("I expected four letters and a question mark")

I then get the position of the question mark.

    pos = seq.index("?")

If this question mark is first, I take the second letter, and subtract the difference between the 4th and 3rd letter.

    if pos == 0:
        return chr(ord(seq[1]) - (ord(seq[3]) - ord(seq[2])))

If the question mark is any other position, I take the letter before it, and add the difference between the two known digits in the same odd/even position. For example if the third letter is missing, I take the second letter and add the difference between the 5th and 4th letters.

     diff_pos = [None, 2, 3, 0, 1][pos]
    return chr(ord(seq[pos-1]) + ord(seq[diff_pos+1]) - ord(seq[diff_pos]))

The Perl solution follows the same logic.

Examples

$ ./ch-1.py a c ? g i
e

$ ./ch-1.py a d ? j m
g

$ ./ch-1.py a e ? m q
i

$ ./ch-1.py a c f ? k
h

$ ./ch-1.py b e g ? l
j

Task 2: Subset Equilibrium

Task

You are given an array of numbers.

Write a script to find all proper subsets with more than one element where the sum of elements equals the sum of their indices.

My solution

The wording of this task changed since it was originally published.

The first part my solution is to find all possible subsets. For this I use bit manipulation to generate and check all possible subsets. The bits value iterates from one (to exclude an empty list) to two less than two to the power of length of the list (i.e. 2^len(seq) - 2). This excludes all the bits been set.

For each iteration, I set the digit_sum and pos_sum variables to zero, and make result an empty list. I have an inner loop through the original list and include the value if its bit is set. The least significant bit is the first number. For example if bits is 6 (binary 110), the second and third values will be used.

If the bit is set for a value, I update digit_sum, pos_sum and result value. After the inner loop completes and if the digit_sum and pos_sum are the same and result has more than one item, I append the result list into the results list.

def subset_equilibrium(nums: list[int]) -> list[list[int]]:
    results = []

    for bits in range(1, 2**len(nums)-1):
        digit_sum = 0
        pos_sum = 0
        result = []
        for pos, value in enumerate(nums):
            if 2 ** pos & bits:
                digit_sum += value
                pos_sum += pos + 1
                result.append(value)

        if digit_sum == pos_sum and len(result) > 1:
            # This matches the criteria
            results.append(result)

    return results

Examples

The order is different than that in the examples on the TWC web site.

$ ./ch-2.py 2 1 4 3
(2, 1), (1, 4), (2, 3), (4, 3)

$ ./ch-2.py 3 0 3 0
(3, 0), (3, 0, 3)

$ ./ch-2.py 5 1 1 1
(5, 1, 1)

$ ./ch-2.py 3 -1 4 2
(3, -1, 4), (3, 2)

$ ./ch-2.py 10 20 30 40 50
()