The H Word
with Raku

by Arne Sommer

The H Word with Raku

[227] Published 9. March 2023.

This is my response to The Weekly Challenge #207.

Challenge #207.1: Keyboard Word

You are given an array of words.

Write a script to print all the words in the given array that can be types 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
Example 1:
Input: @words = ("Hello","Alaska","Dad","Peace")
Output: ("Alaska","Dad")
Example 2:
Input: @array = ("OMG","Bye")
Output: ()

I choose to interpret the second paragraph above so that a legal word must consist of letters from one row only, but that we can have words from several rows in the same solution. (The examples do not clarify this.)

File: keyboard-word
#! /usr/bin/env raku

unit sub MAIN ($words = "Hello Alaska Dad Peace", :v($verbose));  # [0]

my $row1 = /^ <[qwertyuiop]>+ $/;                                 # [1]
my $row2 = /^ <[asdfghjkl]>+  $/;                                 # [2]
my $row3 = /^ <[zxcvbnm]>+    $/;                                 # [3]

my @ok;                                                           # [4]

for $words.words -> $word                                         # [5]
  say ":word: $word" if $verbose;
  @ok.push($word) if $ ~~ / $row1 | $row2 | $row3 /;       # [6]

say "(",{ '"' ~ $_ ~ '"' }).join(","), ")";              # [7]

[0] Specify the words as a (quoted) sentence on the command line, as a slurpy array cannot have a default value (or rather default values, to be pedantic).

[1] The first row, as a named regex.

[2] The second row.

[3] You get the idea.

[4] The legal words will end up here.

[5] Split the input line into words (with the aptly named words), and iterate over them.

See for more information about words.

[6] Add the word if the lower case version of it (courtesy of lc) matches one of the three row regexes from [1], [2] and [3].

See for more information about lc.

[7] Print the words, quoted, separated by commas and with an outer pair of parens, just as in the examples.

Running it:

$ ./keyboard-word -v 
:word: Hello
:word: Alaska
:word: Dad
:word: Peace

$ ./keyboard-word -v "OMG Bye"
:word: OMG
:word: Bye

Looking good.

We can mix words from different rows:

$ ./keyboard-word "tip lash cv pasta"

Challenge #207.2: H-Index

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.

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.

Example 1:
Input: @citations = (10,8,5,4,3)
Output: 4

Because the 4th publication has 4 citations and the 5th has only 3.
Example 2:
Input: @citations = (25,8,5,3,3)
Output: 3

The H-Index is 3 because the fourth paper has only 3 citations.

An illustration may be illuminating:

The first row is the number of citations, sorted. The second is the index (1-based). The third is the result, is the value higher or equal to the index?

File: h-index
#! /usr/bin/env raku

unit sub MAIN (*@citations where @citations.elems  # [1]
  && all(@citations) ~~ /^ 0 || <[1..9]> <[0..9]>* $/, :v($verbose));

my @sorted = @citations.sort;                      # [2]

say ": Sorted: { @citations.join(", ") }" if $verbose;

for @citations.elems ... 1 -> $index               # [3]
  say "Pos:$index -> val:{ @citations[$index -1] }" if $verbose;

  if @citations[$index -1] >= $index               # [4]
    say $index;                                    # [4a]
    last;                                          # [4b]

[1] At least one element, and the values must be either zero or a positive integer.

[2] Sort the values. The examples are sorted, but there is nothing to prevent the user from specifying non-sorted input. (We could enforce sorted input (with e.g. where [>=] @citations attached to [1]), but it is nicer to just sort the values).

[3] Iterate over indices, from the highest one down to 1 (where we use 1-based indexing, and not zero-based as the program).

[4] If the value at the given position (with zero-based index one less than $index) is higher or equal to the index, we have a solution. Print the solution [4a] and exit [4b].

Running it:

$ ./h-index -v 10 8 5 4 3
: Sorted: 10, 8, 5, 4, 3
Index: 5 -> val: 3
Index: 4 -> val: 4

$ ./h-index -v 25 8 5 3 3
: Sorted: 25, 8, 5, 3, 3
Pos:5 -> val:3
Pos:4 -> val:3
Pos:3 -> val:5

Looking good.

Now you may wonder if we can get a false result by looking from the end. Actually not. All the values to the left of a value labled with or will also satisfy the relation. (As the value to the left cannot be higher than the current one, and the index is one less - thus the value must be the same or higher, and it must be equal or higher than an index that is lower. (Feel free to be confused now.)

It is possible to do the scan from the left instead.

Both methods (scan from the right, scan from the left) work fine for small arrays. But this does not scale too well if the number of elemens in the array become very large (and I mean very large). In that case, we could have checked the halfway point. And continue halving the difference (either add or subtract to the index) until we have found the solution.

And that's it.