Weekly Challenge: Strings and Binaries

Weekly Challenge 352

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. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Match String

Task

You are given an array of strings.

Write a script to return all strings that are a substring of another word in the given array in the order they occur.

My solution

The Python solution is relatively straight forward. I have a loop that has i as the index and word as the word I are matching. I then check if any words in the words list are a substring (including a complete match) that are not at the same position. If there are, I append it to the matches list. I also do a check to ensure a word does not appear twice.

def match_string(words: list) -> list:
    matches = []

    for i, word in enumerate(words):
        if word in matches:
            continue

        if any(word in other_word for j, other_word in enumerate(words) if i != j):
            matches.append(word)

    return matches

The Perl solution follows the same logic, but does it slightly differently. Perl has a (documented) quirk that calling each on a array (or hash) does not reset the counter when called a second time. I even made a blog post about the dangers of each in Perl. For the Perl solution, I use a foreach loop to find a match.

sub main (@words) {
    my @other_words = @words;
    my @matches = ();

    while ( my ( $i, $word ) = each(@words) ) {
        if ( any { $_ eq $word } @matches ) {
            next;
        }

        my $j = 0;
        foreach my $other_word (@other_words) {
            if ( $i != $j and index( $other_word, $word ) != -1 ) {
                push @matches, $word;
                last;
            }
            $j++;
        }
    }

    say '(' . join( ', ', map { "\"$_\"" } @matches ) . ')';

Examples

$ ./ch-1.py cat cats dog dogcat dogcat rat ratcatdogcat
['cat', 'dog', 'dogcat', 'rat']

$ ./ch-1.py hello hell world wor ellow elloworld
['hell', 'world', 'wor', 'ellow']

$ ./ch-1.py a aa aaa aaaa
['a', 'aa', 'aaa']

$ ./ch-1.py flower flow flight fl fli ig ght
['flow', 'fl', 'fli', 'ig', 'ght']

$ ./ch-1.py car carpet carpenter pet enter pen pent
['car', 'pet', 'enter', 'pen', 'pent']

Task 2: Binary Prefix

Task

You are given an array, @nums, where each element is either 0 or 1.

Define x_i as the number formed by taking the first i+1 bits of @nums (from $nums[0] to $nums[i]) and interpreting them as a binary number, with $nums[0] being the most significant bit.

Write a script to return an array @answer where $answer[i] is true if x_i is divisible by 5, otherwise false.

My solution

This is the more straight forward of the two tasks. For this task, I have a variable called current_binary that starts with an empty string. For each iteration of nums, I append the value to the current_binary string. I then use int (Python) or oct (Perl) to convert the value to an integer. I then see if it is divisible by five, and append the boolean (string in Perl) to the results list.

def binary_prefix(nums: list) -> list:
    if any(type(n) != int or n not in (0, 1) for n in nums):
        raise ValueError("Input list must contain only 0s and 1s")

    current_binary = ''
    results = []

    for n in nums:
        current_binary += str(n)
        results.append(int(current_binary, 2) % 5 == 0)

    return results

Examples

$ ./ch-2.py 0 1 1 0 0 1 0 1 1 1
[True, False, False, False, False, True, True, False, False, False]

$ ./ch-2.py 1 0 1 0 1 0
[False, False, True, True, False, False]

$ ./ch-2.py 0 0 1 0 1
[True, True, False, False, True]

$ ./ch-2.py 1 1 1 1 1
[False, False, False, True, False]

$ ./ch-2.py 1 0 1 1 0 1 0 0 1 1
[False, False, True, False, False, True, True, True, False, False]