The H Word with Raku

This is my response to The Weekly Challenge #207.

Challenge #207.1: Keyboard Word

Row 1: qwertyuiop
Row 2: asdfghjkl
Row 3: zxcvbnm

Input: @words = ("Hello","Alaska","Dad","Peace")
Output: ("Alaska","Dad")

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

#! /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 $word.lc ~~ / $row1 | $row2 | $row3 /;       # [6]
}

say "(", @ok.map({ '"' ~ $_ ~ '"' }).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 docs.raku.org/routine/words 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 docs.raku.org/routine/lc.html 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
("Alaska","Dad")

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

Looking good.

We can mix words from different rows:

$ ./keyboard-word "tip lash cv pasta"
("tip","lash","cv")

Challenge #207.2: H-Index

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

Because the 4th publication has 4 citations and the 5th has only 3.

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?

#! /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
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
3

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.