Two Two

This is a problem on HackerRank, the second-to-last problem in the algorithm-string section. Since I'm practicing Scala, I naturally implemented it in Scala

The problem is easy to understand: suppose there is a dataset y consisting of powers of 2, where the exponent x is an integer in the range [0, 800]. Given a string, find how many of its substrings are contained in this dataset.

First, note that x ranges over [0, 800], so don't forget 1 (= 2^0); otherwise some numbers will be missing.

The basic idea is to precompute a string set from 2^0 to 2^800, then perform matching.

For string matching, KMP probably comes to mind first, but it's not suitable here because we have 801 candidate strings, and it quickly results in a TLE. When matching many strings, you should first consider a trie. A prefix tree stores everything, and each time you just search it.

Construct the case class PrefixTrieNode as follows:

import scala.collection.mutable.{ Map => MMap }

case class PrefixTrieNode(next: MMap[Char, PrefixTrieNode]) {
    var v: Boolean = false
}

Then define a class (I named it PrefixTrieTree) with a put method, as follows:

class PrefixTrieTree {
    val root: PrefixTrieNode = PrefixTrieNode(MMap[Char, PrefixTrieNode]())

    val insertMonitor = new AnyRef

    def put(k: String) = {
      var p = root
      for (c <- k) {
        insertMonitor.synchronized {
          if (!p.next.contains(c)) {
            p.next += (c -> PrefixTrieNode(MMap[Char, PrefixTrieNode]()))
          }
        }
        p = p.next.get(c).get
      }
      p.v = true
    }
}

Because of state transitions, add a next method to PrefixTrieTree:

def next(c: Char, n: PrefixTrieNode): Option[PrefixTrieNode] = n.next.get(c)
def next(c: Char): Option[PrefixTrieNode] = root.next.get(c)

Finally, and most importantly, after constructing a trie tree, how do we use it?

At first, I considered maintaining an array: check whether the root has a next node with the current char as key, and if so, add it to the queue. Then check each element in the queue to see whether it has a next node with the current char as key; if so, transition its state. Continue like this. Check whether v is true in the new queue; if so, increment the counter. Finally we get the total result.

The code is as follows:

def count(s: String) = {
  s.toCharArray.foldLeft((0, Array[PrefixTrieNode]().par)) { (l, c) =>
    val n = l._2.flatMap { p =>
      next(c, p)
    }
    next(c) match {
      case Some(v) =>
        if (v.v) {
          (l._1 + n.count(_.v) + 1, n :+ v)
        } else {
          (l._1 + n.count(_.v), n :+ v)
        }
      case None =>
        (l._1 + n.count(_.v), n)
    }
  }._1
}

It looks quite reasonable—but it still TLEs. The reason is too many state transitions, and they are basically serial, so the parallelization is poor.

To make the program more parallelizable, modify count as follows:

def count(s: String) = {
    val len = s.length
    (0 to (len - 1)).par.foldLeft(0) { (l, c) =>
    {
      next(s(c)) match {
        case Some(v) =>
          var cnt = if (v.v) 1 else 0
          var off = c + 1
          var p = Option[PrefixTrieNode](v)
          def get = {
            if (off < len) {
              p = next(s(off), p.get)
              off += 1
              p match {
                case Some(add) =>
                  if (add.v)
                    cnt += 1
                  true
                case None =>
                  false
              }
            } else {
              false
            }
          }
          while (get) {}
          cnt
        case None =>
          0
      }
    } + l
}

For the complete code, see here.

Scala and C++ are actually quite different. My first count was mainly in a C++ mindset: because you manage memory manually, whenever possible I try to avoid constantly pushing and popping contexts, and instead prefer to maintain a state machine that keeps rolling forward. But in Scala, parallelism can handle context well; what we mainly need to do is reduce dependencies between parts of the program so it can parallelize better.