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.
Our first challenge, was to stringify an object representing JSON.
sealed class JsonElement
data 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.
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>>).
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()}"
}
}
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:
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:
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()
}
}
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.
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()
}
k-means was a bit more complicated task, and figuring out the algorithm was part of it. Here is my solution:
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 point
private 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) }!! }
}
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))
}
All the solutions, together with passing unit tests, can be found on GitHub:
Marcin Moskala is a highly experienced developer and Kotlin instructor as the founder of Kt. Academy, an official JetBrains partner specializing in Kotlin training, is known for his significant contributions to the Kotlin community. Moskala is the author of several widely recognized books, including "Effective Kotlin," "Kotlin Coroutines," "Functional Kotlin," "Advanced Kotlin," "Kotlin Essentials," and "Android Development with Kotlin."
Beyond his literary achievements, Moskala is the author of the largest Medium publication dedicated to Kotlin. As a respected speaker, he has been invited to share his insights at numerous programming conferences, including events such as Droidcon and the prestigious Kotlin Conf, the premier conference dedicated to the Kotlin programming language.
