https://kotlinlang.org logo
#getting-started
Title
# getting-started
h

holgerbrandl

12/05/2021, 10:51 PM
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
Copy code
listOf("A", "A", "B", "C", "C", "C", "C", "A", "A")
// to
listOf("A" to 2, "B" to 1, "C" to 4, "A" to 2)
e

ephemient

12/05/2021, 11:15 PM
Copy code
fun <T> Collection<T>.runLengths() = buildList {
    val last = this@runLengths.withIndex().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 this@runLengths.size - it.index) }
}
h

holgerbrandl

12/06/2021, 10:51 AM
Awesome. Thanks @ephemient for working it out.
s

Szymon Jeziorski

12/08/2021, 7:36 PM
I know it's a little late now, but this could also be quite elegant and efficient
Copy code
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()
h

holgerbrandl

12/08/2021, 7:47 PM
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 😉?
e

ephemient

12/08/2021, 7:51 PM
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)
✔️ 1
h

holgerbrandl

12/08/2021, 7:55 PM
Thanks for the prompt and in-depth analysis.
15 Views