Advent of Kotlin Solutions

Everything good must come to an end, it is time to end Advent of Kotlin 2021 as well. See how those problems could be solved.

Week 1: JSON stringify

Our first challenge, was to stringify an object representing JSON.

xxxxxxxxxx
 
sealed class JsonElementdata class JsonObject(val fields: Map<String, JsonElement>) : JsonElement() {    constructor(vararg fields: Pair<String, JsonElement>) : this(fields.toMap())}​data class JsonArray(val elements: List<JsonElement>) : JsonElement() {    constructor(vararg elements: JsonElement) : this(elements.toList())}​data class JsonNumber(val value: Double) : JsonElement()data class JsonString(val value: String) : JsonElement()data class JsonBoolean(val value: Boolean) : JsonElement()object JsonNull : JsonElement()

This is a typical exercise to practice using when with type smart-casting. This pattern is really popular in Kotlin (sometimes referred as Kotlin pattern matching). So I expected implementing stringify function as a single-expression function with when and a separate handling for each child of the JsonElement sealed class.

xxxxxxxxxx
 
fun JsonElement.stringify(): String = when (this) {    JsonNull -> TODO()    is JsonBoolean -> TODO()    is JsonString -> TODO()    is JsonNumber -> TODO()    is JsonArray -> TODO()    is JsonObject -> TODO()}

Now think, what should there be in each case.

JsonNull is always null.

JsonBoolean value just needs to be transformed to String.

JsonString value just needs to be wrapped with quotes.

JsonNumber is a bit more tricky, because a value 1.0 should be presented as 1. This means, that such values need to be transformed to Int first. I decided to recognize numbers with no decimal part by chaching if they are changed by floor.

JsonArray is just a collection of elements of type JsonElement. Each of them should be stringified with stringify function (so we use recursion). They should be separated with comma, and the array should start and end with box bracket. This is a perfect case for using joinToString function.

JsonObject is quite similar, but each value has a name. Since Map does not have joinToString function, we first need to transform it to List with toList (transforms Map<K, V> to List<Pair<K, V>>).

xxxxxxxxxx
 
fun JsonElement.stringify(): String = when (this) {    JsonNull -> "null"    is JsonBoolean -> "$value"    is JsonString -> "\"$value\""    is JsonNumber -> if (value == floor(value)) "${value.roundToInt()}" else "$value"    is JsonArray -> elements        .joinToString(prefix = "[", postfix = "]", separator = ",") { value ->            value.stringify()        }    is JsonObject -> fields.toList()        .joinToString(prefix = "{", postfix = "}", separator = ",") { (name, value) ->            "\"$name\":${value.stringify()}"        }}

Week 1: Possible well-formed parentheses

The task is to create a function, that for a given n, generates all combinations of n well-formed pairs of parentheses. Here are a few usage examples:

xxxxxxxxxx
 
fun generateParenthesisCombinations(num: Int): List<String> = TODO()​assertEquals(listOf("()"), generateParenthesisCombinations(1))assertEquals(listOf("(())", "()()"), generateParenthesisCombinations(2).sorted())assertEquals(   listOf("((()))", "(()())", "(())()", "()(())", "()()()"),   generateParenthesisCombinations(3).sorted())assertEquals(   listOf(       "(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()",       "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"   ),   generateParenthesisCombinations(4).sorted())

There are planty of ways, how this problem can be solved. One might generate all possible combinations, and filter out those that are not correct. Another one might insert parenthesis at different positions. But the most efficient and simple solution I know is quite simple. Let's build possible strings character by character. At the beginning, we have a number of parentheses to open, and no opened ones. In such case, we need to place "(". Now we have one open parenthesis, and one less to open. If the number of parenthesis to open is bigger than zero, then we can place either "(" or ")". Otherwise, we need to close those that are opened with ")". All the possible combinations can be implemented recursively in the following way:

xxxxxxxxxx
 
fun generateParenthesisCombinations(num: Int): List<String> =    if (num < 1) emptyList()    else generateParenthesisCombinationsIter("", num, 0)​fun generateParenthesisCombinationsIter(text: String, parenthesisLeft: Int, openedToClose: Int): List<String> {    fun openParen() = generateParenthesisCombinationsIter("$text(", parenthesisLeft - 1, openedToClose + 1)    fun closeParen() = generateParenthesisCombinationsIter("$text)", parenthesisLeft, openedToClose - 1)    return when {        parenthesisLeft == 0 && openedToClose == 0 -> listOf(text)        openedToClose == 0 -> openParen()        parenthesisLeft == 0 -> closeParen()        else -> openParen() + closeParen()    }}

Week 2: Tree algorithms

This is a continuation of classic exercises to practive recursive thinking and using Kotlin pattern matching (when expression with smart-casting). My solution is not the fastest, but it is readable and presents the algorithm quite clearly.

xxxxxxxxxx
 
fun Tree<*>.countAll(): Int = when (this) {    is Leaf -> 1    is Node -> 1 + left.count() + right.count()}​fun Tree<*>.height(): Int = when (this) {    is Leaf -> 1    is Node -> 1 + maxOf(left.count(), right.count())}​fun <T : Comparable<T>> Tree<T>.biggest(): T = when (this) {    is Leaf -> value    is Node -> maxOf(left.biggest(), right.biggest())}​fun Tree<Int>.sum(): Int = when (this) {    is Leaf -> value    is Node -> left.sum() + right.sum()}​operator fun <T> Tree<T>.contains(value: T): Boolean = when (this) {    is Leaf -> this.value == value    is Node -> left.contains(value) || right.contains(value)}​operator fun <T> Tree<T>.plus(other: Tree<T>): Tree<T> =    Node(this, other)​fun <T> Tree<T>.toList(): List<T> = when (this) {    is Leaf -> listOf(value)    is Node -> left.toList() + right.toList()}

Week 3: k-means clustering

k-means was a bit more complicated task, and figuring out the algorithm was part of it. Here is my solution:

xxxxxxxxxx
 
fun solve(    points: List<P>,    maxAvgError: Double): List<P> {    var meansNum = 2    while (true) {        val means = solve(points, meansNum)        val error = calculateError(points, means)        if (error / points.size < maxAvgError) return means        meansNum++    }}​fun solve(    points: List<P>,    dictSize: Int,    threshold: Double = 0.0001): List<P> {    var means = createInitialDictionary(points, dictSize)    var prevError: Double = calculateError(points, means)    while (true) {        means = nextMeans(points, means)        val error = calculateError(points, means)        if (error + threshold >= prevError) return means        prevError = error    }}​protected open fun calculateError(points: List<P>, means: List<P>): Double {    val closestMean = points.map { p -> closestMean(p, means) }    val error = (points zip closestMean).sumOf { (p, q) -> distanceBetween(p, q) }    return error}​protected open fun nextMeans(points: List<P>, means: List<P>): List<P> {    val grouped = grouped(points, means)    val newMeans = grouped.map { (_, group) -> calculateAveragePosition(group) }    val meansWithoutPoints: List<P> = (means elementMinus grouped.keys)    return newMeans + meansWithoutPoints.moveToClosestPointUntaken(points, newMeans)}​fun grouped(points: List<P>, means: List<P>) =    points.groupBy { point -> closestMean(point, means) }​protected fun closestMean(point: P, means: List<P>): P =    means.minByOrNull { mean -> distanceBetween(point, mean) }!!​// Improvement: For mean without points, move to closest untaken pointprivate fun List<P>.moveToClosestPointUntaken(points: List<P>, newMeans: List<P>): List<P> {    val untakenPoints = points - newMeans    return map { m -> untakenPoints.minByOrNull { p -> distanceBetween(p, m) }!! }}

Week 4: JSON parsing

Parsing JSON is not a simple task. The below implementation is not perfect, but covers the most essential functionalities. As you might analize, it is parsing elements recursively. A big problem is finding where an element ends. For instance, when you parse a content of an array, you cannot just separate string with comma, because each element might incluse a comma inside (it might be another array or an object). Solving this kind of problems is not easy, but also sharpens our minds. In my implementation, I also used many regexes.

fun parseJson(text: String): JsonObject? { val trimmed = text.trim() if (!trimmed.startsWith("{") || !trimmed.endsWith("}")) return null var content = trimmed.substringAfter("{").substringBeforeLast("}").trim() val fields = mutableMapOf<String, JsonElement>() while (true) { if (content.isEmpty()) return JsonObject(fields) if (!content.startsWith("\"")) return null val (fieldName, rest) = content.substringAfter("\"").split("\":", limit = 2) .also { if (it.size < 2) return null } val (element, restToParse) = parseJsonElement(rest) ?: return null fields[fieldName] = element content = restToParse } } private const val EVERYTHING_REGEX = "[\\s\\S]*" private const val EVERYTHING_NON_GREEDY_REGEX = "[\\s\\S]*?" private const val COMMA_AND_REST_REGEX = "(\\s*,\\s*)?($EVERYTHING_REGEX)" private val NUMBER_REGEX = Regex("^(\\d+([.]\\d+)?)$COMMA_AND_REST_REGEX") private val NULL_REGEX = Regex("^null$COMMA_AND_REST_REGEX") private val BOOLEAN_REGEX = Regex("^(true|false)$COMMA_AND_REST_REGEX") private val STRING_REGEX = Regex("^\"($EVERYTHING_NON_GREEDY_REGEX)\"$COMMA_AND_REST_REGEX") private val OBJECT_REGEX = Regex("^(\\{$EVERYTHING_NON_GREEDY_REGEX})$COMMA_AND_REST_REGEX") private val ARRAY_REGEX = Regex("^\\[($EVERYTHING_REGEX)]$COMMA_AND_REST_REGEX") private data class ParsingResult(val element: JsonElement, val restToParse: String) private fun parseJsonElement(text: String): ParsingResult? = when { text.contains(NUMBER_REGEX) -> NUMBER_REGEX.find(text)!!.groupValues .let { ParsingResult(JsonNumber(it[1].toDouble()), it[4]) } text.contains(NULL_REGEX) -> NULL_REGEX.find(text)!!.groupValues .let { ParsingResult(JsonNull, it[2]) } text.contains(BOOLEAN_REGEX) -> BOOLEAN_REGEX.find(text)!!.groupValues .let { ParsingResult(JsonBoolean(it[1].toBoolean()), it[3]) } text.contains(STRING_REGEX) -> STRING_REGEX.find(text)!!.groupValues .let { ParsingResult(JsonString(it[1]), it[3]) } text.contains(OBJECT_REGEX) -> OBJECT_REGEX.find(text)!!.groupValues .let { val (objectText, restToParse) = extractObjectText(it[0]) ?: return null val element = parseJson(objectText) ?: return null ParsingResult(element, restToParse) } text.contains(ARRAY_REGEX) -> ARRAY_REGEX.find(text)!!.groupValues .let { var content = it[1] val elements = mutableListOf<JsonElement>() while (content.isNotEmpty()) { val (element, rest) = parseJsonElement(content) ?: return null elements += element content = if(rest.startsWith(",")) rest.drop(1) else rest } ParsingResult(JsonArray(elements), it[2]) } else -> null } private data class ObjectTextAndRest(val objectText: String, val restToParse: String) private fun extractObjectText(text: String): ObjectTextAndRest? { var index = 1 var openedBrackets = 1 while (openedBrackets > 0) { when (text.getOrNull(index)) { null -> return null '{' -> openedBrackets++ '}' -> openedBrackets-- } index++ } return ObjectTextAndRest(text.take(index), text.drop(index)) }

xxxxxxxxxx
 
fun parseJson(text: String): JsonObject? {    val trimmed = text.trim()    if (!trimmed.startsWith("{") || !trimmed.endsWith("}")) return null    var content = trimmed.substringAfter("{").substringBeforeLast("}").trim()    val fields = mutableMapOf<String, JsonElement>()    while (true) {        if (content.isEmpty()) return JsonObject(fields)        if (!content.startsWith("\"")) return null        val (fieldName, rest) = content.substringAfter("\"").split("\":", limit = 2)            .also { if (it.size < 2) return null }        val (element, restToParse) = parseJsonElement(rest) ?: return null        fields[fieldName] = element        content = restToParse    }}​private const val EVERYTHING_REGEX = "[\\s\\S]*"private const val EVERYTHING_NON_GREEDY_REGEX = "[\\s\\S]*?"private const val COMMA_AND_REST_REGEX = "(\\s*,\\s*)?($EVERYTHING_REGEX)"private val NUMBER_REGEX = Regex("^(\\d+([.]\\d+)?)$COMMA_AND_REST_REGEX")private val NULL_REGEX = Regex("^null$COMMA_AND_REST_REGEX")private val BOOLEAN_REGEX = Regex("^(true|false)$COMMA_AND_REST_REGEX")private val STRING_REGEX = Regex("^\"($EVERYTHING_NON_GREEDY_REGEX)\"$COMMA_AND_REST_REGEX")private val OBJECT_REGEX = Regex("^(\\{$EVERYTHING_NON_GREEDY_REGEX})$COMMA_AND_REST_REGEX")private val ARRAY_REGEX = Regex("^\\[($EVERYTHING_REGEX)]$COMMA_AND_REST_REGEX")​private data class ParsingResult(val element: JsonElement, val restToParse: String)​private fun parseJsonElement(text: String): ParsingResult? = when {    text.contains(NUMBER_REGEX) -> NUMBER_REGEX.find(text)!!.groupValues        .let { ParsingResult(JsonNumber(it[1].toDouble()), it[4]) }    text.contains(NULL_REGEX) -> NULL_REGEX.find(text)!!.groupValues        .let { ParsingResult(JsonNull, it[2]) }    text.contains(BOOLEAN_REGEX) -> BOOLEAN_REGEX.find(text)!!.groupValues        .let { ParsingResult(JsonBoolean(it[1].toBoolean()), it[3]) }    text.contains(STRING_REGEX) -> STRING_REGEX.find(text)!!.groupValues        .let { ParsingResult(JsonString(it[1]), it[3]) }    text.contains(OBJECT_REGEX) -> OBJECT_REGEX.find(text)!!.groupValues        .let {            val (objectText, restToParse) = extractObjectText(it[0]) ?: return null            val element = parseJson(objectText) ?: return null            ParsingResult(element, restToParse)        }    text.contains(ARRAY_REGEX) -> ARRAY_REGEX.find(text)!!.groupValues        .let {            var content = it[1]            val elements = mutableListOf<JsonElement>()            while (content.isNotEmpty()) {                val (element, rest) = parseJsonElement(content) ?: return null                elements += element                content = if(rest.startsWith(",")) rest.drop(1) else rest            }            ParsingResult(JsonArray(elements), it[2])        }    else -> null}​private data class ObjectTextAndRest(val objectText: String, val restToParse: String)​private fun extractObjectText(text: String): ObjectTextAndRest? {    var index = 1    var openedBrackets = 1    while (openedBrackets > 0) {        when (text.getOrNull(index)) {            null -> return null            '{' -> openedBrackets++            '}' -> openedBrackets--        }        index++    }    return ObjectTextAndRest(text.take(index), text.drop(index))}

All the solutions, together with passing unit tests, can be found on GitHub:

https://github.com/MarcinMoskala/advent-2021/tree/solution