Perl Weekly Challenge 352 - Match String and Binary Prefix

Task 1: Match String

"Needle in a Word Stack: Finding Embedded Strings!"

This week's first task asks us to scan an array of strings and return every string that appears as a substring of another string in the same array. The order must follow the original input order, and the examples also show that duplicate matches should only appear once in the output.

The Strategy: Walk through the list in order, skip words already seen, and for each remaining word check whether it appears inside any other word in the array. As soon as we find one containing word, we add the candidate to the result and move on. This preserves first-occurrence order while de-duplicating repeated inputs.

Perl Implementation

sub match_string ($words) {
    ($words) = $WORDS_CHECK->($words);

    my %seen;
    my @result;

    for my $i ( 0 .. $#$words ) {
        my $word = $words->[$i];
        next if $seen{$word}++;

        for my $j ( 0 .. $#$words ) {
            next if $i == $j;
            if ( index( $words->[$j], $word ) >= 0 ) {
                push @result, $word;
                last;
            }
        }
    }

    return \@result;
}

Python Implementation

def match_string(words: Sequence[str]) -> list[str]:
    """
    Return words that occur as substrings of other words, in first-occurrence order.
    Duplicate inputs are returned only once.
    """
    result: list[str] = []
    seen: set[str] = set()

    for idx, word in enumerate(words):
        if word in seen:
            continue
        seen.add(word)

        for other_idx, other in enumerate(words):
            if other_idx == idx:
                continue
            if word in other:
                result.append(word)
                break

    return result

Task 2: Binary Prefix

"Prefix Power: Is This Binary Number Divisible by 5?"

The second task builds binary numbers from prefixes of a bit array. For each prefix, we interpret the bits seen so far as one binary number and need to return whether that prefix value is divisible by 5.

The Strategy: Recomputing each full prefix value would be wasteful and could produce huge integers. Instead, we carry only the remainder modulo 5. When a new bit arrives, the new remainder is (old_remainder * 2 + bit) % 5. A prefix is divisible by 5 exactly when this remainder becomes 0.

Perl Implementation

sub binary_prefix_div_by_5 ($nums) {
    ($nums) = $NUMS_CHECK->($nums);
    die 'Expected only 0/1 values' if grep { $_ != 0 && $_ != 1 } @$nums;

    my $remainder = 0;
    my @answer;

    for my $bit (@$nums) {
        $remainder = ( $remainder * 2 + $bit ) % 5;
        push @answer, ( $remainder == 0 ? 1 : 0 );
    }

    return \@answer;
}

Python Implementation

def binary_prefix_divisible_by_5(nums: Sequence[int]) -> list[bool]:
    """
    For each prefix of a 0/1 list, return whether the binary value is divisible by 5.
    """
    remainder = 0
    answer: list[bool] = []

    for bit in nums:
        if bit not in (0, 1):
            raise ValueError("Expected only 0/1 values")
        remainder = (remainder * 2 + bit) % 5
        answer.append(remainder == 0)

    return answer