My Avatar

Shilong ZHAO

[s 99] p10 run Length encoding of a list

2020-06-23 00:00:00 +0200

In case you have any questions or suggestions, you can leave comments HERE . Thanks!

Run-length encoding of a list.

Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as tuples (N, E) where N is the number of duplicates of the element E. Example:

scala> encode(List(‘a, ‘a, ‘a, ‘a, ‘b, ‘c, ‘c, ‘a, ‘a, ‘d, ‘e, ‘e, ‘e, ‘e)) res0: List[(Int, Symbol)] = List((4,’a), (1,’b), (2,’c), (2,’a), (1,’d), (4,’e))

We can reuse the pack function defined in P09 and combine it with a map operation

def pack[T](lists: List[List[T]], list: List[T], rem: List[T]): List[List[T]] = rem match {
    case Nil => lists :+ list
    case x::xs if (list.isEmpty || list.contains(x)) => pack(lists, list :+ x, xs)
    case _ => pack(lists :+ list, List(), rem)
}

def encode[T](symbols: List[T]): List[(Int, T)] = pack(List[List[T]](), List[T](), symbols).map(l => (l.size, l.head))

encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))