PWC 239 Adagio for frayed knots
Tags: perl, perlweeklychallenge, pwc
Published: 2023-10-20 15:41:33

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](https://www.youtube.com/watch?v=DYLIf6FGVTI), 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.
<hr>

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](https://theweeklychallenge.org/blog/perl-weekly-challenge-239/#TASK1)

```text
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`](https://perldoc.perl.org/perlvar#$LIST_SEPARATOR), and in exhausting depth in the "Quote and quote-like operators" section of [`perldoc perlop`](https://perldoc.perl.org/perlop#Quote-and-Quote-like-Operators).

Using string interpolation, we should localize `$"` so it only applies in the scope of the subroutine, not globally to the rest of the program:
```perl
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
```perl
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](https://theweeklychallenge.org/blog/perl-weekly-challenge-239/#TASK2)
```text
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.
```perl
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.