3
\$\begingroup\$

I am trying to create an evaluator in Kotlin for the Mastermind game which compares two strings and tells how many letters and letters on the right position they share.

I was hoping to get some comments on how I can improve the code below in any way. Many thanks in advance!

fun String.masterCompare(otherString:String): Pair<Int, Int>? {

    // If the two strings are not equal in size, return null
    if (length != otherString.length)
        return null

    var letters : Int = 0  // The number of letters the two strings have in common
    var positions: Int = 0 // The number of shared letters that are in the same index
    var other = otherString // A mutable string copy of the argument string

    // Get number of shared indexes (positions)
    for ((index, c) in withIndex()){
        if (c == otherString[index]) {
            positions++
        }
    }

    // Check if a char in this string exists in the other. If so, increment letters and delete the char from the other string (so that it's not rechecked)
    for (c in toList()){
        if (other.contains(c)){
            letters++
            other = other.replace(c.toString(), "")
        }
    }

    return letters to positions
}

fun main(args: Array<String>) {
    println("ABCD".masterCompare("AFCH"))    // 2,2
    println("AAAA".masterCompare("AFCH"))    // 1,1
    println("ABCD".masterCompare("ABCD"))    // 4,4
    println("ABCD".masterCompare("DCBA"))    // 4,0
    println("ABCDP".masterCompare("DCBA"))   // null
}
\$\endgroup\$
4
\$\begingroup\$

You could go for a more functional (rather than imperative) approach.

Such as:

fun String.masterCompare(otherString: String): Pair<Int, Int>? =
        when {
            length != otherString.length -> null
            else -> {
                // this part is really easy
                val commonAtSameIndex = zip(otherString).count {
                    (one, another) -> one == another
                }

                /* calculates the frequency map of characters in a given string.
                 * not the best solution in terms of performance - if you were to expect
                 * really large strings, you might be better off keeping the imperative approach.
                 * possibly with a bitmask instead of reassigning the mutable string. */
                fun String.toFrequency() = groupBy { it }
                        .mapValues { it.value.size }
                        .toMap()

                val thisFrequencyMap = toFrequency()
                val otherFrequencyMap = otherString.toFrequency()

                val commonOverall = thisFrequencyMap
                        .map { (letter, count) ->
                            min(count, otherFrequencyMap[letter] ?: 0)
                        }
                        .sum()
                commonOverall to commonAtSameIndex
            }
        }

I would also suggest avoiding nulls out of principle, and possibly returning (0, 0) if strings aren't of the same length.

If you do need to differentiate between this case and strings of the same length that don't share any characters, I'd consider coming up with dedicated types instead of a nullable Pair, which is too generic (and makes it easy to confuse which field stands for what).

Eg. the result type might be:

sealed class MasterComparisonResult {
    object DifferentLength : MasterComparisonResult()

    data class SameLength(val commonAtSameIndex: Int, val commonOverall: Int) : MasterComparisonResult()
}

And then the function returns a MasterComparisonResult instance.

Here's a version that combines the functional way - in my opinion much clearer - of calculating the number of identical characters in the same positions with the loop that calculates the other value.

A bit array is used for better performance.

fun String.masterCompare(otherString: String): Pair<Int, Int>? =
        when {
            length != otherString.length -> null
            else -> {
                // this part is really easy
                val commonAtSameIndex = zip(otherString).count {
                    (one, another) -> one == another
                }

                var commonOverall = 0
                val countedAlready = BooleanArray(length)   

                /* this is yet another detail: there's no need for toList() allocation.
                 * you can iterate over this (String) straight away. */
                for (c in this) {
                    /* find the first occurrence of the c character in otherString
                     * that wasn't counted already */
                    val index = countedAlready
                            .asSequence()
                            .withIndex()
                            .filterNot { it.value }
                            .indexOfFirst { otherString[it.index] == c }
                    if (index >= 0) {
                        countedAlready[index] = true
                        commonOverall++
                    }
                }
                commonOverall to commonAtSameIndex
            }
        }
\$\endgroup\$
  • 2
    \$\begingroup\$ I appreciate you noting the efficiency concerns for large input-sizes. I don't necessarily agree with your assessment that a functional is inherently "better", and the code seems less clear and more complex in your current approach; I don't really see the benefit. \$\endgroup\$ – Graham Nov 17 '18 at 17:52
  • 2
    \$\begingroup\$ For the first part of the task (counting identical letters at the same indices) the functional approach is definitely more concise and readable. For the other part it might indeed be overkill - I just wanted to demonstrate the possibility. \$\endgroup\$ – Konrad Morawski Nov 17 '18 at 18:00
  • 1
    \$\begingroup\$ I also added a version that tries to combine both approaches (while introducing minor optimizations). Thank you for your input @Graham \$\endgroup\$ – Konrad Morawski Nov 17 '18 at 18:09
  • 1
    \$\begingroup\$ Thank you @Konard. The functional approach may indeed be an overkill but I did learn some things from it. The second optimized version is definitely more efficient! \$\endgroup\$ – Dawit Abraham Nov 18 '18 at 21:19
  • \$\begingroup\$ Glad I could be of help! Thanks for accepting the answer. @DawitAbraham \$\endgroup\$ – Konrad Morawski Nov 18 '18 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.