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

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.

CodePudding user response：

First solution with using recursion. I take Char by Char from string and check if last element in the Vector is the same as current. If elements the same I update last element by increasing count(It is first case). If last element does not the same I just add new element to the Vector(second case). When I took all Chars from the string I just return result.

  def counterOccur(string: String): Vector[(Char, Int)] = {
    @tailrec
    def loop(str: List[Char], result: Vector[(Char, Int)]): Vector[(Char, Int)] = {
      str match {
        case x :: xs if result.lastOption.exists(_._1.equals(x)) =>
          val count = result(result.size - 1)._2
          loop(xs, result.updated(result.size - 1, (x, count   1)))
        case x :: xs =>
          loop(xs, result :  (x, 1))
        case Nil => result
      }
    }

    loop(string.toList, Vector.empty[(Char, Int)])
  }

  println(counterOccur("aabcdddeabb"))

Second solution that does not use recursion. It works the same, but instead of the recursion it is using foldLeft.

  def counterOccur2(string: String): Vector[(Char, Int)] = {
    string.foldLeft(Vector.empty[(Char, Int)])((r, v) => {
      val lastElementIndex = r.size - 1
      if (r.lastOption.exists(lv => lv._1.equals(v))) {
        r.updated(lastElementIndex, (v, r(lastElementIndex)._2   1))
      } else {
        r :  (v, 1)
      }
    })
  }

  println(counterOccur2("aabcdddeabb"))

CodePudding user response：

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.

CodePudding user response：

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))
   }
}

CodePudding user response：

For

str = "aabcdddeabb"

you could use extract matches of the regular expression

rgx = /(.)\1*/

to obtain the array

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

Then simply map each element s of the array to the desired string.

In Ruby, for example, you could write

arr = str.gsub(rgx).to_a
  #=> ["aa", "b", "c", "ddd", "e", "a", "bb"]
arr.map { |s| "(#{s[0]},#{s.size})" }  
  #=> ["(a,2)", "(b,1)", "(c,1)", "(d,3)", "(e,1)", "(a,1)", "(b,2)"]

I assume Scala, like most languages, has comparable methods or functions.

Note that I've employed a little-used form of Ruby's string method gsub. Rather than making character substitutions it simply returns an an enumerator that generates matches of the regular expression. Those matches are converted to an array of matches with the the method to_a. Ruby also has a method scan but that does not have the intended effect here because the regular expression contains a capture group.