# Run-length encoding (RLE) Decoder

## Algorithm goal

Run-length encoding is one of the most basic compression methods, which is especially useful where there long runs of a particular character or a group of characters. It could be particularly useful for example in column-based databases which have potentially many repeating values.

Run-length turns a sequence of characters into effectively a sequence of count-character pairs. For example, WWWAAW becomes 3W2A1W.

See RunLengthEncoding for the Encoder.

## Explanation

While this can be implemented in Tail Recursion, we will implement in a streaming style because:

• It it is not possible to make it work in a streaming fashion (because who wants to run out of memory?).

In a functional/immutable style approach, we must think in terms of transformations , and in this particular algorithm, because we need to parse the input, we need to consider that either an input is a digit or a non-digit, then fuse any digits into numbers of occurrences (because we do wish to be able to handle inputs like 13Y); and finally, combine digit-char pairs and emit them as a String. (this is © from www.scala-algorithms.com)

## Scala Concepts & Hints

Collect

'collect' allows you to use Pattern Matching, to filter and map items.

assert("Hello World".collect {
case character if Character.isUpperCase(character) => character.toLower
} == "hw")


Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

assert("Hello World".collect {
case character if Character.isUpperCase(character) => character.toLower
} == "hw")


scanLeft and scanRight

Scala's scan functions enable you to do folds like foldLeft and foldRight, while collecting the intermediate results

assert(List(1, 2, 3, 4, 5).scanLeft(0)(_ + _) == List(0, 1, 3, 6, 10, 15))


Sliding / Sliding Window

Get fixed-length sliding sub-sequences (sliding windows) from another sequence

Stack Safety

Stack safety is present where a function cannot crash due to overflowing the limit of number of recursive calls.

This function will work for n = 5, but will not work for n = 2000 (crash with java.lang.StackOverflowError) - however there is a way to fix it :-)

In Scala Algorithms, we try to write the algorithms in a stack-safe way, where possible, so that when you use the algorithms, they will not crash on large inputs. However, stack-safe implementations are often more complex, and in some cases, overly complex, for the task at hand.

def sum(from: Int, until: Int): Int =
if (from == until) until else from + sum(from + 1, until)

def thisWillSucceed: Int = sum(1, 5)

def thisWillFail: Int = sum(1, 300)


View

The .view syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.

## Algorithm in Scala

21 lines of Scala (version 2.13), showing how concise Scala can be!

## Test cases in Scala

assert(decodeString("1W") == "W")
assert(decodeString("3W") == "WWW")
assert(decodeString("3W1A1W") == "WWWAW")
assert(decodeString("3W1A2B2W") == "WWWABBWW")
assert(
decodeString("x3W1A2B2W") == "WWWABBWW",
"Invalid character in front is ignored"
)
assert(
decodeString("3W1A2B2") == "WWWABB",
"Invalid character at the back is ignored"
)
assert(
decodeString("13Y") == "YYYYYYYYYYYYY",
">10-strong RLE is emmitted correctly"
)

def decodeString(string: String): String = ???