Advent of Code 2018: Day 5

Ooh that's better. Kotlin is a much better match for Advent of Code than Java. I've never really used Kotlin in any meaningful way so would love to hear feedback if there's a better way I could be using it.

Part 1

Part 1 of today's task involves us being given a string of characters, inside which we should replace every pair of characters which are adjacent, and are the same character but different case. We must do this iteratively until no matches remain.

For example, in the string "dabAcCaCBAcCcaDA" the following steps would be taken:

dabAcCaCBAcCcaDA  The first 'cC' is removed.
dabAaCBAcCcaDA    This creates 'Aa', which is removed.
dabCBAcCcaDA      Either 'cC' or 'Cc' are removed (the result is the same).
dabCBAcaDA        No further actions can be taken.

Leaving 10 characters, which is our answer.

For my solution a String isn't ideal as it is not mutable, so I first convert it to a StringBuilder. From there it's just a matter of iterating through each pair, and removing any matches - moving back each time there is to check if that creates a new match. This is O(n) complexity.

import java.lang.StringBuilder

fun main(args: Array<String>) {
    if (args.isEmpty()) {
        System.err.print("First argument should be polymer string")
        System.exit(-1)
    }

    val polymerString = args[0]
    val reducedPolymerString = reducePolymerString(polymerString)
    println("Part 1: " + reducedPolymerString.length)
}

fun reducePolymerString(polymerString: String): String {
    val reducedPolymerBuilder = StringBuilder(polymerString)

    var ptr = 0

    while (ptr < reducedPolymerBuilder.length - 1) {
        if (polymerMatches(reducedPolymerBuilder[ptr], reducedPolymerBuilder[ptr + 1])) {
            // Match - reduce
            reducedPolymerBuilder.delete(ptr, ptr + 2)

            if (ptr > 0) {
                // We need to check if this creates a match with the previous character
                ptr--
            }
        } else {
            ptr++
        }
    }

    return reducedPolymerBuilder.toString()
}

fun polymerMatches(a: Char, b: Char): Boolean {
    return a.toLowerCase() == b.toLowerCase() && a != b
}

Part 2

For Part 2 we need to remove a single "unit type" (character pair) and find create the shortest reduced form. To do this, I generate a regular expression to match each pair, do the replacement and generate the reduced string - recording the shortest.

Kotlin is a really nice language for this sort of script.

val alphabet = CharArray(26) { (it + 97).toChar() }
val replaceRegex = alphabet.map { Regex("[" + it + it.toUpperCase() + "]") }

var minLength = polymerString.length
for (r in replaceRegex) {
    val reduced = reducePolymerString(polymerString.replace(r, ""))
    if (reduced.length < minLength) {
        minLength = reduced.length
    }
}

print("Minimum achieved my removing one character: " + minLength)

Advent Of Code runs until December 25. You should get involved!

Show Comments

Get the latest posts delivered right to your inbox.