RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved string relations and binary numbers. (Note that this ends today.)

Task 1: Match String

You are given an array of strings.

Write a script to return all strings that are a substring of another word in the given array in the order they occur.

A more efficient approach would be to sort the strings by length, and then do just half the comparisons. But too bad, I didn't; I just check each string against each other string, and every language I use has some sort of "is X contained in Y". (Also, from the examples, input strings should appear only once each in the output; sometimes I keep a separate set of strings I've seen, or if the language makes it easy I'll just search through the output list.)

Python:

def matchstring(a):
  out = []
  for x in a:
    if x not in out:
      for y in a:
        if len(y) > len(x) and y.find(x) > -1:
          out.append(x)
          break
  return out

Task 2: Binary Prefix

You are given an array, @nums, where each element is either 0 or 1.

Define x-sub-i as the number formed by taking the first i+1 bits of @nums (from $nums[0] to $nums[i]) and interpreting them as a binary number, with $nums[0] being the most significant bit.

For example:

`If @nums = (1, 0, 1), then:

x0 = 1 (binary 1)

x1 = 2 (binary 10)

x2 = 5 (binary 101)

For each i, check whether xi is divisible by 5.Write a script to return an array @answerwhere$answer[i]istrueif x-sub-i is divisible by5, otherwise false`.

There's probably a name for this pattern, but I think of it as a rolling accumulator, which I often use in base conversion: as I go through the list, double what I already have, add the next entry, and test. Perl:

sub binaryprefix($a) {
  my $c = 0;
  my @out;
  foreach my $n (@{$a}) {
    $c *= 2;
    $c += $n;
    push @out, ($c % 5 == 0)?1:0;
  }
  \@out;
}

Full code on github.