Removing repeating rows and columns from 2d array

Question

This is a real problem I had to fix recently. Imagine having generic array where you can have duplicate columns and rows. You want to remove those duplicates as long as they are next to each other.

inline fun <reified T : Any?> Array<Array<T>>.toSimplified(): Array<Array<T>> {
 return simplifyColumns().simplifyRows()
}
inline fun <reified T : Any?> Array<Array<T>>.simplifyColumns(): Array<Array<T>> {
 val uc = uniqueColumnIndexes()
 return Array(uc.size) { x ->
 Array(height) { y ->
 this[uc[x]][y]
 }
 }
}
inline fun <reified T : Any?> Array<Array<T>>.simplifyRows(): Array<Array<T>> {
 val ur = uniqueRowIndexes()
 return Array(width) { x ->
 Array(ur.size) { y ->
 this[x][ur[y]]
 }
 }
}
fun <T : Any?> Array<Array<T>>.uniqueColumnIndexes(): List<Int> {
 val uniqueColumns = mutableListOf<Int>()
 var x = 0
 while (x < width) {
 uniqueColumns.add(x)
 val column = column(x)
 val sameColumns = countIdenticalColumns(x, column)
 x += if (sameColumns > 0) {
 sameColumns
 } else {
 1
 }
 }
 return uniqueColumns
}
inline fun <reified T : Any?> Array<Array<T>>.uniqueRowIndexes(): List<Int> {
 val uniqueRows = mutableListOf<Int>()
 var y = 0
 while (y < height) {
 uniqueRows.add(y)
 val row = row(y)
 val sameRows = countIdenticalRows(y, row)
 y += if (sameRows > 0) {
 sameRows
 } else {
 1
 }
 }
 return uniqueRows
}
inline fun <reified T : Any?> Array<Array<T>>.countIdenticalRows(
 rowIndex: Int,
 row: Array<T>
): Int {
 val sameColumns = (rowIndex until height).indexOfFirst { yOffset ->
 !(row(yOffset) contentEquals row)
 }.takeIf { it >= 0 } ?: (height - rowIndex)
 return sameColumns
}
fun <T : Any?> Array<Array<T>>.countIdenticalColumns(
 columnIndex: Int,
 column: Array<T>
): Int {
 val sameColumns = (columnIndex until width).indexOfFirst { xOffset ->
 !(column(xOffset) contentEquals column)
 }.takeIf { it >= 0 } ?: (width - columnIndex)
 return sameColumns
}
inline fun <reified T : Any?> Array<Array<T>>.row(y: Int): Array<T> {
 return (0 until width).map { x ->
 this[x][y]
 }.toTypedArray()
}
fun <T : Any?> Array<Array<T>>.column(x: Int): Array<T> {
 return this[x]
}
val <T : Any?> Array<Array<T>>.width
 get() = size
val <T : Any?> Array<Array<T>>.height
 get() = firstOrNull()?.size ?: 0

And here are some unit tests showing it on Array<Array<Char>> so that it's easy to print and show the differences:

class SimplifiedArrayTest {
 @Test
 fun test3x3vs1x1() {
 assertMapsEqual(
 """
 xxx
 xxx
 xxx
 """.trimIndent(),
 "x"
 )
 }
 @Test
 fun test2x1vs1x1() {
 assertMapsEqual(
 """
 xx
 """.trimIndent(),
 "x"
 )
 }
 @Test
 fun test1x2vs1x1() {
 assertMapsEqual(
 """
 x
 x
 """.trimIndent(),
 "x"
 )
 }
 @Test
 fun test1x5vs1x3() {
 assertMapsEqual(
 """
 o
 x
 x
 x
 o
 """.trimIndent(),
 """
 o
 x
 o
 """.trimIndent()
 )
 }
 @Test
 fun test5x1vs3x1() {
 assertMapsEqual(
 """
 oxxxo
 """.trimIndent(),
 """
 oxo
 """.trimIndent()
 )
 }
 @Test
 fun test5x5vs3x3() {
 assertMapsEqual(
 """
 oxxxo
 xxxxx
 xxxxx
 xxxxx
 oxxxo
 """.trimIndent(),
 """
 oxo
 xxx
 oxo
 """.trimIndent()
 )
 }
 @Test
 fun test5x5vs3x3v2() {
 assertMapsEqual(
 """
 xxxxx
 xxxxx
 xxoxx
 xxxxx
 xxxxx
 """.trimIndent(),
 """
 xxx
 xox
 xxx
 """.trimIndent()
 )
 }
 private fun parseArray(map: String): Array<Array<Char>> {
 return map.trimIndent().trim().lines().map {
 it.map { it }.toTypedArray()
 }.toTypedArray()
 }
 private fun arrayToString(array: Array<Array<Char>>): String {
 return (0 until array.height).joinToString("\n") { y ->
 (0 until array.width).joinToString("") { x ->
 array[x][y].toString()
 }
 }
 }
 private fun assertMapsEqual(mapToSimplify: String, map: String) {
 val m1 = parseArray(mapToSimplify).toSimplified()
 val m2 = parseArray(map)
 assertEquals(m1.width, m2.width, message = arrayToString(m1) + "\nvs\n" + arrayToString(m2))
 assertEquals(m1.height, m2.height, message = arrayToString(m1) + "\nvs\n" + arrayToString(m2))
 m1.indices.forEach {
 assertContentEquals(m1[it], m2[it], message = arrayToString(m1) + "\nvs\n" + arrayToString(m2))
 }
 }
}

I find a bit annoying, the the first function is inline with reified generics. The reason is when creating new 2d array, the constructor requires it. Consequence to that is also that some of the inline functions cannot be private. Performance is not as important as readability here. As always I appreciate any kind of feedback :-)

• Simon Forsberg: Would using another data type other than arrays be an option?
• K.H.: It's unlikely, but possible. This 2d array is current input and output in the pipeline. Changing that would require more refactoring of the system.
• Simon Forsberg: Well, I was in this case thinking of something as simple as a 2D list instead, which can be created with generics much easier :) So not much transformations.
• Simon Forsberg: May I ask out of curiosity, what is the context for this? Why do you need it? I find the challenge quite interesting :)
• K.H.: Sure, this array represents models a 1 floor "level" environment. You can say there are corridors and rooms, but as long as the rows/columns are identical, for our current use case it makes no difference that anything is farther/closer. Building this map from the array in our engine is extremely slow so the optimization is worth doing.

Answer 1

Kotlin Array<T> compiles to java T[] so we need to know the type at compile-time, hence the reified parameter. If you want to get the output as an array, it's inevitable.

It's generally a better idea to use lists instead, especially if you're working with non-primitive types. Did you check if it's actually slower in your case?

And most importantly, are you sure you even need generic types here? Judging by your usecase, looks like you can just specify the type: Array<Room (or whatever)>.

---

The code looks fine.

The first line is redundant:

val row = row(y)
val sameRows = countIdenticalRows(y, row)

y += if (sameRows > 0) {
 sameRows
} else {
 1
}

can be replaced with

y += maxOf(1, sameRows)

Instead of doing countIdenticalRows and uniqueRowIndexes and then simplifyRows I would just walk through the array and construct a new one from ground up by appending rows that don't repeat the previous one (same for columns), this seems more straightforward.

• Simon Forsberg: I was originally planning on rewriting the code by appending rows/columns that don't repeat the previous one, but then I felt an urge to go to bed and also realized that because of the columns, it wasn't that straight-forward as I was hoping, as a distinct column would need to be added to every row, and then I just finished my answer and now I'm going to bed. But I do in principle agree that constructing a new list from the ground up by appending row/columns directly instead of first finding the indices is more straight-forward.

Answer 2

First changes:

• Array can be List instead to get rid of the generics problem.
• This means that functions does not need to be inline and type parameters do not need to be reified.
• Additionally, specifying T : Any? does not give any information, simply T is enough.
• Order of parameters for assertEquals is expected, then actual. You have passed the arguments the other way around, which makes error messages confusing when test fail.

Rewriting the core part using Kotlin's built-in methods:

What you are really doing is to check if two consecutive rows are the same or not. Using Kotlin's windowed function, we can simplify(?) (well, at least shorten... simplify may be a bit opinion-based) the code to check for unique indices a bit.

fun <T> Sequence<T>.uniqueIndices(): List<Int> {
 return this.withIndex().windowed(size = 2, partialWindows = true)
 .filter { it.size == 1 || it[0].value != it[1].value }
 .map { it.first().index }.toList()
}
fun <T> List<List<T>>.uniqueColumnIndexes(): List<Int> = (0 until width).asSequence()
 .map { column(it) }.uniqueIndices()
fun <T> List<List<T>>.uniqueRowIndexes(): List<Int> = (0 until height).asSequence()
 .map { row(it) }.uniqueIndices()

Using distinctUntilChanged of Flows:

Kotlin Flows are an amazing feature and I would really recommend learning them. One thing they have that Sequences and Lists do not is a distinctUntilChanged function.

Using that you can get the actual values of the consecutive rows/columns directly:

(this here is a List<T> or Sequence<T>)

this.withIndex().asFlow().distinctUntilChanged { old, new -> old.value == new.value }.map { it.index }.toList()

Other suggestions:

• simplify has an ambiguous meaning. I would call it "removeConsecutive".
• Consider making a Grid class and expose only the methods and fields necessary, instead of passing around a two-dimensional array.

• QuasiStellar: Use of distinctUntilChanged is clever. Worth mentioning that Flow.toList() suspends, so you need to wrap it in runBlocking {} or something similar. You also need to add a dependency on kotlinx-coroutines-core to your project.

Answer 3

A simple solution could be to filter for duplicate rows, transpose the matrix, then filter for duplicate rows again, and transpose back:

inline fun <reified T> Array<Array<T>>.transpose(): Array<Array<T>> {
 return Array(this[0].size) { j -> Array(size) { i -> this[i][j] } }
}
inline fun <reified T : Any> Array<Array<T>>.filterConsecutiveDuplicateRows(): Array<Array<T>> {
 return this
 .filterIndexed { index, item -> if (index < size - 1) !this[index + 1].contentEquals(item) else true }
 .toTypedArray()
}
inline fun <reified T : Any> Array<Array<T>>.filterConsecutiveDuplicateRowsAndColumns(): Array<Array<T>> {
 return this
 .filterConsecutiveDuplicateRows()
 .transpose()
 .filterConsecutiveDuplicateRows()
 .transpose()
}

Or with lists instead of arrays:

fun <T : Any> List<List<T>>.filterConsecutiveDuplicateRowsAndColumns(): List<List<T>> {
 fun <T> List<List<T>>.transpose(): List<List<T>> {
 return List(this[0].size) { j -> List(size) { i -> this[i][j] } }
 }
 fun <T : Any> List<List<T>>.filterConsecutiveDuplicateRows(): List<List<T>> {
 return this.filterIndexed { index, item -> if (index < size - 1) this[index + 1] != item else true }
 }
 return this
 .filterConsecutiveDuplicateRows()
 .transpose()
 .filterConsecutiveDuplicateRows()
 .transpose()
}

What is generally not clear to me about this: can removing all duplicate rows and then all duplicate columns result in a matrix that has new duplicate rows or columns?

I tried to find a matrix where there are new duplicates after the first row and column pass, and I didn't find any.

• K.H.: While this simple solution can make code shorter, it is very ineffective and will consume unnecessarily huge amount of resources when having big arrays. I don't think removing duplicate rows can then change amount of duplicate columns so the order doesn't matter and rows/columns need to be always done only once :)