Damerau Levenshtein Implementation in Kotlin This is an implementation of the Damerau-Levenshtein distance in Kotlin which I created as an exercise, but might be also useful, if it proves to be correct.

The implementation is based on this Wikipedia article, even though it does not 100% follow the suggested pseudo-code.

fun damerauLevenshteinCount(a: CharSequence, b: CharSequence): Int {
    return damerauLevenshtein(a, b).first
}

/**
 * According to Wikipedia:
 * &lt;cite&gt;Damerau–Levenshtein distance between two words is the minimum number of operations (consisting of insertions,
 * deletions or substitutions of a single character, or transposition of two adjacent characters) required to change one word into the other&lt;/cite&gt;
 */
fun damerauLevenshtein(a: CharSequence, b: CharSequence): Pair&lt;Int, Array&lt;IntArray&gt;&gt; {
    requireNotNull(a) { "First string should not be null. Make sure you specify the first string." }
    requireNotNull(b) { "Second string should not be null. Make sure you specify the second string." }
    val aLength = a.length
    val bLength = b.length
    val d = Array(aLength + 1, { IntArray(bLength + 1) })
    val daMap = hashMapOf&lt;Char, Int&gt;()
    val maxdist = a.length + b.length
    for (i in 0..aLength) {
        d[i][0] = i
    }
    for (j in 0..bLength) {
        d[0][j] = j
    }
    for (i in 1..aLength) {
        var db = 0
        for (j in 1..bLength) {
            val k = daMap.getOrDefault(b[j - 1], 0)
            val l = db
            var cost = 0
            if (a[i - 1] == b[j - 1]) {
                db = j
            } else {
                cost = 1
            }
            val substitution = d[i - 1][j - 1] + cost
            val insertion = d[i][j - 1] + 1
            val deletion = d[i - 1][j] + 1
            val transposition = if (k == 0 || l == 0) maxdist else d[k - 1][l - 1] + (i - k - 1) + 1 + (j - l - 1)
            d[i][j] = intArrayOf(substitution, insertion, deletion, transposition).min() as Int
        }
        daMap[a[i - 1]] = i
    }
    return Pair(d[aLength][bLength], d)
}


Here is a unit test which shows the behaviour of this implementation:

@Test
fun damerauLevenshteinDistanceCount() {
    Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("h1", "h1")).isEqualTo(0)
    Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("gil", "gil")).isEqualTo(0)
    Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("gil", "gill")).isEqualTo(1)
    Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("ca", "abc")).isEqualTo(2) // Differs from optimal string alignment distance distance
    Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("waht", "what")).isEqualTo(1)
    Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("thaw", "what")).isEqualTo(2)
    Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("waht", "wait")).isEqualTo(1)
    Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("Damerau", "uameraD")).isEqualTo(2)
    Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("Damerau", "Daremau")).isEqualTo(2)
    Assertions.assertThat(wagnerDamerau.damerauLevenshteinCount("Damerau", "Damreau")).isEqualTo(1)
    Assertions.assertThat(wagnerDamerau.osaDistanceCount("waht", "whit")).isEqualTo(2)
    Assertions.assertThat(wagnerDamerau.osaDistanceCount("what", "wtah")).isEqualTo(2)
}


I want to check for its correctness as well if I am using Kotlin in the best possible idiomatic manner.
For determining correctness of your implementation I recommend referring to an existing implementation such as Apache commons-lang or the newer commons-text:


commons-lang:


StringUtils.java:7997-8254
StringUtilsTest.java:2378-2479

commons-text


LevenshteinDistance.java
LevenshteinDistanceTest.java
ParameterizedLevenshteinDistanceTest.java
LevenshteinDetailedDistance.java
LevenshteinDetailedDistanceTest.java
LevenshteinResults.java



As far as your Kotlin code goes, here are my comments:


Kotlin already guarantees that a and b are not null as you've used CharSequence for their type instead of CharSequence?. As such, the requireNotnull statements are unnecessary.
I do not believe you gain much from aLength and bLength. a.length and b.length read clearly and are read in constant time so the additional variables seem unnecessary to me.
You can place the last lambda argument in a function call into parentheses  as you have done but I personally find moving it out of the parentheses easier to read and more idiomatic:

val d = Array(a.length + 1, { IntArray(b.length + 1) })


becomes

val d = Array(a.length + 1) { IntArray(b.length + 1) }

In some languages variable names like maxdist are common and expected but in Kotlin (and Java) I find it more common and expected to have variables names avoid abbreviations, use camel casing, etc. I recommend using maxDistance instead of maxdist.
You are returning a Pair&lt;Int, Array&lt;IntArray&gt;&gt;. This is fine but data classes are so much better and Kotlin makes it so easy to define and use them. I recommend creating your own type to return. e.g.:

data class DamerauLevenshteinResult(val count: Int, val d: Array&lt;IntArray&gt;)