StringDistanceChallenge.kt

import kotlin.math.abs
import kotlin.time.ExperimentalTime
import kotlin.time.measureTime

@ExperimentalTime
fun simpleBench(testIterations: Int = 1000, warmUpIterations: Int = 5, printSteps: Boolean = false, action: ()-> Unit): Double {
    val results = ArrayList<Double>()
    println("Running Simple Bench")

    for (iterationCount in 1..(testIterations + warmUpIterations)) {
        val timePassed = measureTime { action() }

        if (iterationCount <= warmUpIterations) {
            if (printSteps) println("Warm up $iterationCount out of $warmUpIterations")
        } else {
            if (printSteps) println("Test ${iterationCount - warmUpIterations} out of $testIterations")
            results.add(timePassed.inMilliseconds)
        }
    }
    val average = results.average()
    val median = results[results.size / 2]

    println("Average: $average ms | Median: $median ms (highest: ${results.max()} lowest: ${results.min()})")
    println("Average: ${average / 1000} s | Median: ${median / 1000} s (highest: ${results.max()?.div(1000)} lowest: ${results.min()?.div(1000)})")

    return average
}

@ExperimentalTime
fun main() {

    // This is our use case:
    // We would like to find the absolute distance between two words in a given string
    // for example:
    //
    // dist("this is an example", "example", "example") // should return 0
    // dist("this is an example", "an", "example") // should return 1
    // dist("this is an example", "is", "example") // should return 2
    // dist("this is an example", "doesnt exist", "example") // should return -1
    //
    // the following solution is the easiest and slowest one.

    fun slowDist(source: String, w1: String, w2: String): Int {
        if (w1 == w2) return 0
        val split = source.toLowerCase().split(' ', '\r', '\n', 't')
        val w1Index = split.indexOf(w1)
        val w2Index = split.indexOf(w2)
        if (w1Index == -1 || w2Index == -1) return -1

        return abs(w1Index-w2Index)
    }

    println(slowDist("this is an example", "example", "example") == 0)
    println(slowDist("this is an example", "an", "example") == 1)
    println(slowDist("this is an example", "is", "example") == 2)
    println(slowDist("this is an example", "doesnt exist", "example") == -1)

    val sentences = listOf(
        "It turns out you don't need all that stuff you insisted you did.",
        "The fact that there's a stairway to heaven and a highway to hell explains life well.",
        "The plan will cost three trillion, almost the entire federal budget, including social security and medicare"
    )

    val words = sentences.flatMap { it.toLowerCase().filter { char -> char.isLetter() }.split(" ") }

    val slowDistSpeedTest = simpleBench(50_000, 20, false) {
        val sentence = sentences.random()
        val w1 = words.random()
        val w2 = words.random()
        slowDist(sentence, w1, w2)
    }

    println(slowDistSpeedTest)
}

// This one is quite fast but has an issue with string boundries
// i.e. when searching for "is" it will be matched with "this"

fun fastFailingNonSplittingDist(source: String, w1: String, w2: String): Int {
if (w1 == w2) return 0
val w1FirstIndex = source.indexOf(w1)
if (w1FirstIndex == -1) return -1
val w2FirstIndex = source.indexOf(w2)
if (w2FirstIndex == -1) return -1

    val w1Boundary = if (w1FirstIndex < w2FirstIndex) w1FirstIndex + w1.length else w1FirstIndex
    val w2Boundary = if (w1FirstIndex > w2FirstIndex) w2FirstIndex + w2.length else w2FirstIndex

    var nonContinuesSpaceCount = 0
    var foundWhiteSpace = false

    for (index in w1Boundary until w2Boundary) {
        if (!foundWhiteSpace && source[index].isWhitespace()) {
            nonContinuesSpaceCount += 1
        } else if (foundWhiteSpace && !source[index].isWhitespace()) {
            foundWhiteSpace = false
        }
    }

    return nonContinuesSpaceCount
}