PWC 352 Five is the one-liest number

Task 1: Match String

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

• Example 1:
  • Input: @words = ("cat", "cats", "dog", "dogcat", "dogcat", "rat", "ratcatdogcat")
  • Output: ("cat", "dog", "dogcat", "rat")

The Deep Thoughts

Example 1 implies a couple of constraints. A complete match counts as a substring. Words may be repeated in the input. Repeated words are not duplicated in the output. The output order must match the input order. Noted.

For each word, we'll need to take it out of the list, check for substrings, and then put it back for the next round. A relatively simple way of doing that would be to shift it off the front of the list, do what needs to be done, and then return it by pushing it onto the back.

I don't see much of a way of getting around the idea that every word must be compared to every other word, so we're looking at an O(n²) performance algorithm.

One possibility for reducing the operation count might be to compare a pair of words both ways. If I have $w1 and $w2 in hand, I can check both directions for substring-i-ness. That way, instead of having to loop over the entire NxN matrix, we would only have to loop over the upper or lower triangle of the matrix. It's fewer looping operations, but still the same number of string comparisons. But it would mean more complexity in keeping track of what's been checked, so, meh.

The Code

sub matchString(@words)
{
    use List::Util qw/any/;
    my %seen;
    my @match;
    for ( 1 .. @words )
    {
        my $w = shift @words;
        push @match, $w if ( ! $seen{$w}++ && any { index($_, $w) >= 0  } @words );
        push @words, $w;
    }
    return \@match;
}

Notes:

• Use a hash (%seen) to eliminate duplicates, and coincidentally optimize a little by not searching multiple times.
• The main loop is once per word, so simply count. Normally, I would prefer something obviously tied to the array (like for (@words)), but since I'm changing the array within the loop, I don't want to have to think too hard about whether the iterator remains valid after removing and adding an element.
• index is a cheaper operation than a regular expression match. Benchmarking bears this out -- it's about three times more efficient in my environment and test data.
• List::Util::any stops as soon as something works, so it's cheaper than grep, which would evaluate the entire list every time.

Task 2: Binary Prefix

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

For example: If @nums = (1, 0, 1), then:
x₀ = 1 (binary 1)
x₁ = 2 (binary 10)
x₂ = 5 (binary 101)

For each i, check whether x_i is divisible by 5.

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

• Example 1:
  • Input: @nums = (0,1,1,0,0,1,0,1,1,1)
  • Output: (true, false, false, false, false, true, true, false, false, false)

Binary numbers formed (decimal values):

         0:   0  (false)
        01:   1  (false)
       011:   3  (false)
      0110:   6  (false)
     01100:  12  (false)
    011001:  25  ( true)
   0110010:  50  ( true)
  01100101: 101  (false)
 011001011: 203  (false)
0110010111: 407  (false)

The Deep Thoughts

Weird flex, but OK.

This puts me in mind of bit-twiddling with C code, but bit-twiddling in Perl is equally possible. The other alternative is probably to build strings and do binary number conversions by prefixing with '0b'.

I kind of want to do a list-based solution, using map to convert each 0 or 1 to a true or false, but I think that would be obfuscating a pretty simple loop.

The Code

sub bpre(@nums)
{
    my @isFive;
    my $b = 0;

    while ( defined(my $bit = shift @nums) )
    {
        $b = ($b << 1) | $bit;
        push @isFive, ( $b % 5 == 0 );
    }
    return \@isFive;
}

Notes:

• Destroy the input by shifting a 1 or 0 off the left until the list is gone.
• Do bit operations to form a new number.
• Build an answer array consisting of boolean values.

Musical Interlude

The solution to task 1 reminds me of Katy Perry's Hot N Cold -- "You're yes, then you're no. You're in, then you're out."

And for Task 2, Mambo Number 5 is oddly appropriate. "Take one step left and one step right, One to the front and one to the side. Clap your hands once and clap your hands twice, And if it looks like this, then you're doin' it right."