Solve membership binary mask problem in Scala

Question

Imagine you have two string sequences:

val s1 = Seq("c", "a", "b", "z", "a", "b")
val s2 = Seq("a", "b")

You need to come up with an algorithm that generates a binary membership mask of s2 in s1, e.g.:

algorithm(s1, s2) => 011000

Here are some other examples:

val s1 = Seq("a", "b", "z", "c", "a")
val s2 = Seq("a", "b", "z")
11100

val s1 = Seq("z", "b", "a", "a", "b")
val s2 = Seq("a", "b")
00011

val s1 = Seq("z", "b", "a", "a", "b")
val s2 = Seq("a")
00100

val s1 = Seq("z", "b", "a", "a", "b")
val s2 = Seq("a", "a")
00110

Notice that we only count first sequence match and discard the rest sequence matches.

Basically, in case of s2 = Seq("z", "b", "a", "a", "b") and s1 = Seq("a", "b") we are trying to solve the following task:

"z"  "b"  "a"  "a"  "b"
 |    |    |    |    |
" "  " "  " "  "a"  "b"
 |    |    |    |    |
 0    0    0    1    1

Why? Imagine you have a sequence of auto-generated strings like "This is Google Inc ." but you only need to extract "Google" from it cutting everything else. It is easy when you know what you are searching for but once it is "This is ? Inc ." you have no way but to rely on binary masks that you collected from a big corpus. In order to generate such masks, you first need the algorithm described above.

I have come up with a simple while loop. This looks pretty ugly, so there should be another more Scala-like solution. How would you solve it?

def binmask(a: Seq[String], b: Seq[String]): String = {
  val x = a.sliding(b.length, 1)
  var continue = true
  var mask = ""
  while (continue && x.hasNext) {
    val g = x.next()
    if (g == b) {
      mask += "1"*b.length + "0"*x.length
      continue = false
    } else mask += "0"
  }
  if (continue) mask += "0"
  mask
}

Answer 1

The "never occurs" bug is still there. It stems from the fact that the length of b has an inverse relationship to the length of x. Try varying the length of a non-occurring b and see what you get.

There's also the fact that this is a rather imperative approach, whereas good Scala style tries to be more functional.

When I first saw this I thought, "Doesn't indexOfSlice() offer most of what's needed?"

def binmask(seq :Seq[String], slice :Seq[String]) :String = {
  val ios = seq indexOfSlice slice
  if (ios < 0)
    "0"*seq.length
  else {
    val slcLen = slice.length
    "0"*ios + "1"*slcLen + "0"*(seq.length-slcLen-ios)
  }
}

The slight drawback here is that indexOfSlice() will traverse the seq input until it finds a match (or completely if not found) and then seq is traversed again for its length.

The standard Scala means to achieve iteration with early termination but without mutable state, is via recursion. Preferably tail recursion, which the compiler turns into a while loop under the hood.

def binmask(seq :Seq[String], slice :Seq[String], acc :String = "") :String =
  if (seq startsWith slice) {
    val slcLen = slice.length
    acc + "1"*slcLen + "0"*(seq.length - slcLen)
  }
  else if (seq.isEmpty) acc
  else binmask(seq.tail, slice, acc + "0")

Some feel that making the accumulator a passed parameter (even though it is "hidden" behind a default value) exposes too much implementation in the public interface. For them, an inner recursion loop is preferable.

def binmask(seq :Seq[String], slice :Seq[String]) :String = {
  def loop(subseq: Seq[String], acc: String): String =
    if (subseq startsWith slice) {
      val slcLen = slice.length
      acc + "1" * slcLen + "0" * (subseq.length - slcLen)
    }
    else if (subseq.isEmpty) acc
    else loop(subseq.tail, acc + "0")

  loop(seq, "")
}

Answer 2

The function should be genericized to accept any two sequences of the same type, so that you can also write binmask("abaab", "aa") for convenience.

Recursion is a bit tedious and error-prone, as your correction in Rev 7 shows. I suggest taking advantage of Iterator.indexWhere() to perform the search.

def binmask[T](a: Seq[T], b: Seq[T]): String = a.sliding(b.length, 1).indexWhere(_ == b) match {
  case -1 => "0" * a.length
  case i  => "0" * i + "1" * b.length + "0" * (a.length - i - b.length)
}