Complementing Silvio's great answer.
I would like to present different approaches to solve this problem.
First, a solution using a tail-recursive algorithm:
object UsingTailRecursion {
def apply(str: String): String = {
@annotation.tailrec
def loop(remaining: List[Char], currentChar: Char, currentCount: Int, acc: List[(Char, Int)]): String =
remaining match {
case char :: tail =>
if (char == currentChar)
loop(
remaining = tail,
currentChar,
currentCount + 1,
acc
)
else
loop(
remaining = tail,
currentChar = char,
currentCount = 1,
(currentChar -> currentCount) :: acc
)
case Nil =>
((currentChar -> currentCount) :: acc).reverseIterator.map {
case (char, count) =>
s"${count}${char}"
}.mkString
}
str.toList match {
case char :: tail =>
loop(
remaining = tail,
currentChar = char,
currentCount = 1,
acc = List.empty
)
case Nil =>
""
}
}
}
This one is pretty close to the imperative version of the algorithm, the focus here was just to remove mutability and ensure we do not blow up the stack if the string is too big.
Second, using foldLeft and some helper classes and methods to reduce boilerplate.
object UsingFoldLeft {
private final case class MyState(currentChar: Char, currentCount: Int, acc: List[(Char, Int)]) {
def nextState(nextChar: Char): MyState =
if (nextChar == currentChar)
this.copy(currentCount = this.currentCount + 1)
else
MyState(currentChar = nextChar, currentCount = 1, acc = (this.currentChar -> this.currentCount) :: this.acc)
def result: String =
((currentChar -> currentCount) :: acc).reverseIterator.map {
case (char, count) =>
s"${count}${char}"
}.mkString
}
def apply(str: String): String = {
val result = str.foldLeft(Option.empty[MyState]) {
case (Some(state), char) =>
Some(state.nextState(nextChar = char))
case (None, char) =>
Some(MyState(currentChar = char, currentCount = 1, acc = List.empty))
}
result.fold(ifEmpty = "")(_.result)
}
}
As you can see this is more concise and didn't require us to worry about things like iterating with the remaining elements.
(Note: For this particular problem I would say this is the solution with the best trade-off between learning-curve and advantages; however I present the next one for completeness).
Finally, a version using the cats library; precisely the State Monad and the traverse method.
object UsingStateMonad {
import cats.data.{State, NonEmptyList}
import cats.syntax.all._
private final case class MyState(currentChar: Char, currentCount: Int, acc: List[(Char, Int)])
private def nextState(nextChar: Char): State[MyState, Unit] = State.modify { s =>
if (nextChar == s.currentChar)
s.copy(currentCount = s.currentCount + 1)
else
MyState(currentChar = nextChar, currentCount = 1, acc = (s.currentChar -> s.currentCount) :: s.acc)
}
def stateToResult(state: MyState): String =
((state.currentChar -> state.currentCount) :: state.acc).reverseIterator.map {
case (char, count) =>
s"${count}${char}"
}.mkString
def apply(str: String): String =
str.toList.toNel.fold(ifEmpty = "") {
case NonEmptyList(char, tail) =>
val initialState = MyState(currentChar = char, currentCount = 1, acc = List.empty)
tail.traverse_(nextState).runS(initialState).map(stateToResult).value
}
}
As you can see, I am using things like NonEmptyList and State to better represent each operation's intention and allow me to scale the solution if needed.
As you can see, each step tries to reduce mechanical steps and rather focus more on the description of the problem.
The second and most important advantage of each following version is the ability to split the problem into more independent steps that can be understood independently and can be moved to independent functions that can be tested in isolation.
Feel free to ask any questions you may have.
You can see the code running here.
