Hey, how could I calculate a run length encoding e...

# getting-started

[holgerbrandl]

Hey, how could I calculate a run length encoding elegantly for arbitrary types (not just strings but based on equals). E.g. how to transform

listOf("A", "A", "B", "C", "C", "C", "C", "A", "A")
// to
listOf("A" to 2, "B" to 1, "C" to 4, "A" to 2)

[ephemient]

fun <T> Collection<T>.runLengths() = buildList {
    val last = [e-mail]().fold(null) { prev: IndexedValue<T>?, cur ->
        when {
            prev == null -> cur
            prev.value == cur.value -> prev
            else -> {
                add(prev.value to cur.index - prev.index)
                cur
            }
        }
    }
    last?.let { add(it.value to [e-mail] - it.index) }
}

[ephemient]

see also https://youtrack.jetbrains.com/issue/KT-8280

[holgerbrandl]

Awesome. Thanks @ephemient for working it out.

[Szymon Jeziorski]

I know it's a little late now, but this could also be quite elegant and efficient

fun <T> Collection<T>.runLengths() = takeIf { isNotEmpty() }?.let {
    buildList {
        it.fold(it.first() to 0) { (prev, count), cur ->
            if (cur == prev) (prev to count + 1) else {
                add(prev to count)
                cur to 1
            }
        }.run(::add)
    }
}.orEmpty()

[holgerbrandl]

It's never too late for an elegant implementation. Thanks for sharing. To me it looks equally great with the fold over the counter instead of null as in the solution one above. What's your take @ephemient (as you seem the other RLE specialist here 😉?

[ephemient]

I don't like that it effectively performs 3 different checks: isNotEmpty(), first(), and fold() might be working on different underlying arrays of a CopyOnWriteArrayList if it's being mutated underneath. but that probably isn't a issue in most programs, and it's not like mine is completely correct either (due to the .size at the end… could be addressed with a simple counter added, though)

[holgerbrandl]

Thanks for the prompt and in-depth analysis.