Ah, strings, the inexhaustible cornucopia of programming tasks. I found this week's challenges easy, so I cast around for what else "strings" reminds me of. The first thing that came to mind was Samuel Barber's Adagio for Strings, which has been called the saddest music ever written. Take seven minutes to listen to it in a quiet place, and come back when you've stopped sobbing.

The other thing it reminded me of was a joke that, when I first heard it, I thought was the funniest joke ever. A string goes into a bar, and the bartender yells at him, "Get out! We don't serve your kind here!" So the string steps outside. He ties himself in a knot, ruffles up his ends, and steps back into the bar. The bartender says, "Hey, aren't you that string that was just here?" The string says, "No, I'm a frayed knot."

Now that I am older and wiser, I know that this is not actually the funniest joke ever. The funniest joke ever is this:

Q: What's brown and sticky?
A: A stick.

Thank you; thank you. I'll be here all week. Don't forget to tip your waiter.

Okay, let's solve those string problems. I thought of answers almost as soon as I read the problems, so I'm not going to belabor alternatives. These are the answers.

Task 1 Same String

You are given two arrays of strings.
Write a script to find out if the word created
by concatenating the array elements is the same.

Example 1

Input: @arr1 = ("ab", "c"), @arr2 = ("a", "bc")
Output: true

Using @arr1, word1 => "ab" . "c" => "abc"
Using @arr2, word2 => "a" . "bc" => "abc"

Example 2

Input: arr1 = ("ab", "c"), @arr2 = ("ac", "b")
Output: false

Example 3

Input: @arr1 = ("ab", "cd", "e"), @arr2 = ("abcde")
Output: true

Solution

What's happening here is that the elements of @arr1 are being concatenated into one long string; the elements of @arr2 are being concatenated into another; and we want the result of comparing them.

There are two good ways of concatenating a list of strings. The first is to use join with an empty delimiter: join('', @arr1). That's a perfectly good solution, and for people who switch among languages, it's easy to read and remember because there's a similar function in a lot of programming languages, including at least Java, Javascript, Python, Ruby, Tcl, and PHP.

The other pretty good way is to use string interpolation. When an array is interpolated into a string in Perl, all the elements of the array are listed in order, with a separator given by the $" special variable. This is documented in perldoc perlvar, and in exhausting depth in the "Quote and quote-like operators" section of perldoc perlop.

Using string interpolation, we should localize $" so it only applies in the scope of the subroutine, not globally to the rest of the program:

sub sameString($arr1, $arr2)
{
    local $" = '';
    return "$arr1->@*" eq "$arr2->@*"; 
}

What other Perl subtleties lurk here? Well, we want to pass two arrays into a subroutine. We're doing that by reference, because passing two lists as arguments of a function call doesn't work -- they get flattened into one long list. That means the subroutine has to be called like

sameString([ qw(ab c) ], [ qw(a bc) ] ); # Literal strings
sameString(\@arr1, \@arr2); # Using references to arrays

I'm using post-fix array dereferencing. I find it more readable than the older @$arr1 syntax.

Task 2 Consistent Strings

You are given an array of strings and an
allowed string having distinct characters.

A string is consistent if all characters in
the string appear in the string allowed.

Write a script to return the number of
consistent strings in the given array.

Example 1

Input: @str = ("ad", "bd", "aaab", "baa", "badab")
$allowed = "ab"
Output: 2

Strings "aaab" and "baa" are consistent since they only
contain characters 'a' and 'b'.

Example 2

Input: @str = ("a", "b", "c", "ab", "ac", "bc", "abc")
$allowed = "abc"
Output: 7

Example 3

Input: @str = ("cc", "acd", "b", "ba", "bac", "bad", "ac", "d")
$allowed = "cad"
Output: 4

Strings "cc", "acd", "ac", and "d" are consistent.

Regular expression match, done. The allowed characters form a character class, and we want a string that contains one or more of those characters between the beginning and end. Using grep in scalar mode returns a count.

sub consistentStrings($allowed, @str)
{
    return 0 if $allowed eq "";
    my $rx = qr/^[$allowed]+$/;

    return scalar grep /$rx/, @str;
}

What's that first part about return 0? If $allowed could be an empty string, it would create /^[]$/, which is an invalid regular expression. That's a minimal sanity check, but more should be done. Once we open that can of worms, some interesting complications arise. What, exactly, can come between the [ and ] of a character class? Most metacharacters lose their special powers within brackets, but there are rules for ^, -, brackets, and braces, and Unicode named characters are still allowed. $allowed could even look like .]anything could go here[. It might be best to sanitize the $allowed string and limit it to only alphabetic characters before we use it.

In this subroutine, I didn't use array references. By making the $allowed parameter the first one, it's possible to infer where the array parameter begins, even after Perl flattens the arguments in the subroutine call.