Given: aabcdddeabb => Expected: [(a,2),(b,1),(c,1),(d,3),(e,1),(a,1),(b,1)] in Scala

Question

I'm really interested in how this algorithm can be implemented. If possible, it would be great to see an implementation with and without recursion. I am new to the language so I would be very grateful for help. All I could come up with was this code and it goes no further:

print(counterOccur("aabcdddeabb"))

def counterOccur(string: String) =
string.toCharArray.toList.map(char => {
  if (!char.charValue().equals(char.charValue() + 1)) (char, counter)
  else (char, counter + 1)
})

I realize that it's not even close to the truth, I just don't even have a clue what else could be used.

Answer 1

You can use a very simple foldLeft to accumulate. You also don't need toCharArray and toList because strings are implicitly convertible to Seq[Char]:

"aabcdddeabb".foldLeft(collection.mutable.ListBuffer[(Char,Int)]()){ (acc, elm) =>
   acc.lastOption match {
     case Some((c, i)) if c == elm => 
       acc.dropRightInPlace(1).addOne((elm, i+1))
     case _ => 
       acc.addOne((elm, 1))
   }
}

Answer 2

Here is a solution using foldLeft and a custom State case class:

def countConsecutives[A](data: List[A]): List[(A, Int)] = {
  final case class State(currentElem: A, currentCount: Int, acc: List[(A, Int)]) {
    def result: List[(A, Int)] =
      ((currentElem -> currentCount) :: acc).reverse
    
    def nextState(newElem: A): State =
      if (newElem == currentElem)
        this.copy(currentCount = this.currentCount + 1)
      else
        State(
          currentElem = newElem,
          currentCount = 1,
          acc = (this.currentElem -> this.currentCount) :: this.acc
        )
  }
  object State {
    def initial(a: A): State =
      State(
        currentElem = a,
        currentCount = 1,
        acc = List.empty
      )
  }
  
  data match {
    case a :: tail =>
      tail.foldLeft(State.initial(a)) {
        case (state, newElem) =>
          state.nextState(newElem)
      }.result
    
    case Nil =>
      List.empty
  }
}

---

You can see the code running here.

Answer 3

One possibility is to use the unfold method. This method is defined for several collection types, here I'm using it to produce an Iterator (documented here for version 2.13.8):

def spans[A](as: Seq[A]): Iterator[Seq[A]] =
  Iterator.unfold(as) {
    case head +: tail =>
      val (span, rest) = tail.span(_ == head)
      Some((head +: span, rest))
    case _ =>
      None
  }

unfold starts from a state and applies a function that returns, either:

• None if we want to signal that the collection ended
• Some of a pair that contains the next item of the collection we want to produce and the "remaining" state that will be fed to the next iteration.

In this example in particular, we start from a sequence of A called as (which can be a sequence of characters) and at each iteration:

• if there's at least one item
  • we split head and tail
  • we further split the tail into the longest prefix that contains items equal to the head and the rest
  • we return the head and the prefix we got above as the next item
  • we return the rest of the collection as the state for the following iteration
• otherwise, we return None as there's nothing more to be done

The result is a fairly flexible function that can be used to group together spans of equal items. You can then define the function you wanted initially in terms of this:

def spanLengths[A](as: Seq[A]): Iterator[(A, Int)] =
  spans(as).map(a => a.head -> a.length)

This can be probably made more generic and its performance improved, but I hope this can be an helpful example about another possible approach. While folding a collection is a recursive approach, unfolding is referred to as a corecursive one (Wikipedia article).

You can play around with this code here on Scastie.

Answer 4

For

str = "aabcdddeabb"

you could extract matches of the regular expression

rgx = /(.)\1*/

to obtain the array

["aa", "b", "c", "ddd", "e", "a", "bb"]

and then map each element of the array to the desired string.¹

def counterOccur(str: String): List[(Char, Int)] = {
  """(.)\1*""".r
    .findAllIn(str)
    .map(m => (m.charAt(0), m.length)).toList
}

counterOccur("aabcdddeabb")
  #=> res0: List[(Char, Int)] = List((a,2), (b,1), (c,1), (d,3), (e,1), (a,1), (b,2))

The regular expression reads, "match any character and save it to capture group 1 ((.)), then match the content of capture group 1 zero or more times (\1*).

^{1. Scala code kindly provided by @Thefourthbird.}