RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved number lists and word prefixes. (Note that this ends today.)

Task 1: Separate Digits

You are given an array of positive integers.

Write a script to separate the given array into single digits.

This is a pretty easy one to convert into an algorithm: break down each number into digits, and append digits to the output list. Perl:

sub separatedigits($a) {
  my @out;

Take each input number in turn.

  foreach my $n (@{$a}) {

Make a working copy.

    my $m = $n;

Set up this number's output list.

    my @v;

Specifying "positive" rather than "non-negative" integers makes my life easier here; I can ignore the special case where the initial value of $m is zero.

    while ($m > 0) {

Push the mod10 value onto the list and divide the working value.

      push @v, $m % 10;
      $m = int($m / 10);
    }

Now I have a list of the digits in reverse order (least significant first) – so reverse that list and append it to the output.

    push @out, reverse @v;
  }
  return \@out;
}

Other languages are broadly similar. Ruby has its divmod method which is probably slightly more efficient than separate division and modulus operations. Lua doesn't have a list reverser so I end up prepending values to v. Every language has a different way of saying "extend this list with the elements of this other list".

Task 2: Count Words

You are given an array of words made up of alphabetic characters and a prefix.

Write a script to return the count of words that starts with the given prefix.

This is the sort of problem I like to solve in a left-to-right functional style: take the list, filter by prefix, take the length. I couldn't get Raku to do this with a grep, I think because of the way its implementation of index can produce a NaN-like Nil value ("the substring is not in the string at all") which has to be checked separately from a non-zero numeric value ("the substring is in the string, just not at the front"). So I just laid it out in full:

sub prefixwords(@s, $p) {
    my $r = 0;
    for @s -> $w {
        with $w.index($p) -> $i {
            if ($i == 0) {
                $r++;
            }
        }
    }
    return $r;
}

In several other languages this could be a one-liner, as in Kotlin:

fun prefixwords(s: List<String>, p: String): Int {
    return s.filter {it.startsWith(p)}.size
}

Ruby lets me be even briefer by having a filter-and-count keyword:

def prefixwords(s, p)
  return s.count {|i| i.index(p) == 0}
end

I rather like the efficiency of PostScript:

/prefixwords {
    1 dict begin
    /p exch def
    [ exch
      {

The anchorsearch keyword returns either (string-after-match) (match) true or (string) false – so by discarding the top two elements on the stack I end up with either the after-match or nothing at all. And since I'm only going to be counting the number of successful matches, I can casually leave that lying on the stack as the countable element.

          p anchorsearch pop pop
      } forall
    ] length
    end
} bind def

(I could have used a mark and counttomark/cleartomark – which would probably be slightly more efficient – but I'd need to store the result somewhere while clearing down the stack, and I like this approach of building up arrays.)

Full code on github.