PWC 207: She's givin' me H citatations
Tags: perl, pwc, perlweeklychallenge
Published: 2023-03-06 18:57:37

[Week 207 from the Perl Weekly Challenge](https://theweeklychallenge.org/blog/perl-weekly-challenge-207/) is upon us.  This week we have some regular expression fun and pretty easy array manipulation with an academic context.

## Task 1 Keyboard word
This task states:

> You are given an array of words.
> Write a script to print all the words in the given array that
> can be typed using alphabet on only one row of the keyboard.
> Let us assume the keys are arranged as below:
> Row 1: qwertyuiop
> Row 2: asdfghjkl
> Row 3: zxcvbnm

This is asking us to match words against the criterion that all the letters in the word come from a set of characters.  That's pretty easily a character class from a regular expression.  The entire word must match the letters, so we'll want word-boundary markers in the regular expression, too.

Besides the regular expression, we have to design some code that passes over the list of words, and for each word, tries each possible row of the keyboard.

First, let's write a function that does the second part: decide if a word can be formed from one row of the keyboard.
``` perl
sub isKeyboardWord($word)
{
    state @Keyboard = ( qr/[qwertyuiop]+/, qr/[asdfghjkl]+/, qr/[zxcvbnm]+/ );
    return any { $word =~ /\A$_\Z/ } @Keyboard;
}
```
Let's take this apart.

- `sub isKeyboardWord($word)` -- I use 5.36, which has function signatures.  `$word` is a string.
- `state @Keyboard` -- This array is going to define the rows of the keyboard.  I use `state` here so that it only gets initialized once the first time the function is called.
- `( qr/[qwertyuiop]+/,...)` -- Each element of the keyboard array is a regular expression that matches one or more of a set of characters for that row.
- `return any {...} @Keyboard` -- The `any` function from `List::Util` will return true as soon as the code block succeeds.  The advantage of using `any` instead of `grep` is that `any` will stop as soon as it succeeds, while `grep` would continue pointlessly testing other elements of the array.  It's a trivial optimization here, but worth keeping in mind for larger arrays.
- `$word =~ /\A$_\Z/` -- Here's our regular expression match. It reads as "match from the beginning of the string, one or more characters from a keyboard row, to the end of the string." The pattern from `@Keyboard` is in `$_`.  The `\A` anchors the expression to the beginning of the string; `\Z` anchors the end of the string. 

Now that we have a predicate function to test whether any particular word works, we need a loop over a list of words that maps this predicate unto each word.  Here's the next level:
``` perl
sub keyboardWord($list)
{
    my @result = grep { isKeyboardWord(lc trim $_) } $list->@*;
    return \@result;
}
```
Notes on this function:
- `sub keyboardWord($list)` -- our function signature is taking the list of words as an array reference.  I prefer to pass aggregate structures by reference, because my experience with C, C++, and Java made me aware of the performance implications of copying aggregates as function parameters.
- `my @result = grep {} $list->@*` -- selecting words from a list by matching some condition is the definition of `grep`, so let's do that. `$list->@*` is postfix dereferencing; I could have used `@$list`, but since I adopted postfix, I like to use it consistently.
- `{ isKeyboardWord(lc trim $_) }` -- The condition for `grep` is using the function we wrote above.  I inserted some string conditioning here: `lc` is lower-case transformation; and `trim` is a recent experimental built-in to remove white space around the word. `trim` is probably unnecessary, but I like to have excuses to use new stuff. The incantation to use trim is `no warnings "experimental::builtin"; use builtin qw/trim/;`
- `return \@result` -- I return a reference to the array of matching words. Not shown here is the testing rig around this; using a reference makes it slightly more convenient to write a test.

This gives us a function to use, but we also want to use this script from the command line.  The problem asks for output parenthesized and quoted, like `("Alaska","dad")`.  It's a one-liner to do that, but worth explaining.
``` perl
say "(", join(", ", map { qq("$_") } keyboardWord(\@ARGV)->@*), ")";
```
Let's start from the right end.
- `\@ARGV` -- perl has helpfully given us all the command-line arguments in @ARGV, but our function wants a reference.
- `keyboardWord(\@ARGV)->@*`  -- here we call our function, and it returns a reference to an array.  Postfix notation lets us expand the reference when we need it, as we do here to make it the target list for the `map`.
- `map { qq("$_") }` -- for each word in the result, transform it by adding double quotes around it.  The `qq` operator lets us add quotes without needing backslash escapes.
- `join(",", ...)` -- now that we have an array of quoted strings, make a comma-separated list in one string.
- `say "(", ..., ")"` -- the final step is to put exterior parentheses around the list

## Task 2 H-Index
There's a bit of context that goes with this task, but the programming task is actually pretty simple.  The problem statement:
> You are given an array of integers containing citations a
> researcher has received for each paper.
>
> Write a script to compute the researcher’s H-Index. For more
> information please checkout the [wikipedia page](https://en.wikipedia.org/wiki/H-index).
>
> The H-Index is the largest number h such that h articles
> have at least h citations each. For example, if an author has
> five publications, with 9, 7, 6, 2, and 1 citations (ordered
> from greatest to least), then the author’s h-index is 3,
> because the author has three publications with 3 or more
> citations. However, the author does not have four publications
> with 4 or more citations.

(For readers without a background in US popular culture, the title of this blog refers to a hit song from the 1960's by the Beach Boys.  The lyrics of the song "Good Vibrations" include "I'm pickin' up good vibrations / She's giving me excitation".  H citations? Get it? This is why I'm a software developer and not a comedian.)

Throwing aside the academic posturing, what this amounts to is sorting an array descending, and then finding the first index of the array where x[i] < i.
``` perl
sub H_index(@cite)
{
    my @sorted = sort { $b <=> $a } @cite;
    my $h = first { $sorted[$_] < $_+1 } 0 .. $#sorted;
    return $h;
}
```
- `sub H_index(@cite)` -- So after I went on about how I prefer references, here I am using a full array instead.  Consistency is the hobgoblin of small minds.
- `sort { $b <=> $a }` -- All the examples are sorted, but let's not assume that.  This is the usual idiomatic numeric sort in descending order, which we're going to save in a temporary variable.
- `first {..} 0 .. $#sorted` -- Use the range operator to generate the list of indices for the array.  The `first` function from `List::Util` will walk down the list until the condition matches.
- `{ $sorted[$_] < $_+1 }` -- And here's our condition.  There's a `+1` in here because array indexing is zero-based, but the H-Index definition is 1-based.