Kotlin для спортивного программирования

Простой пример: задача Reachable Numbers

Рассмотрим конкретный пример.

26 апреля состоялся раунд 555 Codeforces для третьего дивизиона, а значит, в нём были задачи, которые мог попробовать решить любой разработчик. Задачи можно прочитать по этой ссылке. Самая простая задача в наборе — задача A: Reachable Numbers. В ней предлагается реализовать простой алгоритм, описанный в условии задачи.

Для начала решения создадим исходный файл Kotlin с произвольным именем. A.kt подойдёт. Сначала нужно реализовать функцию, описанную в условии задачи следующим образом:

Обозначим функцию f(x) следующим образом: прибавим к x единицу, затем удалим все завершающие нули из полученного числа.

Kotlin — прагматичный язык, не навязывающий разработчику определённый стиль программирования: он поддерживает как императивный, так и функциональный подход. Функцию f можно реализовать в функциональном стиле, используя такие возможности Kotlin, как хвостовая рекурсия:

tailrec fun removeZeroes(x: Int): Int =
    if (x % 10 == 0) removeZeroes(x / 10) else x

fun f(x: Int) = removeZeroes(x + 1)

Кроме того, можно написать императивную реализацию функции f с помощью традиционного цикла while и изменяемых переменных, которые в Kotlin обозначаются с помощью var:

fun f(x: Int): Int {
    var cur = x + 1
    while (cur % 10 == 0) cur /= 10
    return cur
}

Во многих случаях типы в Kotlin можно не указывать благодаря повсеместному выводу типов, однако у каждого объявления всё равно есть определённый статический тип, известный во время компиляции.

Теперь осталось написать главную функцию, которая считывает входные данные и реализует оставшуюся часть алгоритма из условия задачи — вычисляет количество различных целых чисел, полученных при многократном применении функции f к начальному числу n, переданному через стандартный ввод.

По умолчанию Kotlin работает на JVM и предоставляет прямой доступ к богатой и эффективной библиотеке коллекций общего назначения и структур данных, таких как динамические массивы (ArrayList), хеш-таблицы и множества (HashMap/HashSet), упорядоченные древовидные таблицы и множества (TreeMap/TreeSet). Используя хеш-множество целых чисел для отслеживания уже достигнутых значений при применении функции f, простое императивное решение задачи можно записать так:

fun main() {
    var n = readln().toInt() // read integer from the input
    val reached = HashSet<Int>() // a mutable hash set 
    while (reached.add(n)) n = f(n) // iterate function f
    println(reached.size) // print answer to the output
}

fun main() {
    var n = readLine()!!.toInt() // read integer from the input
    val reached = HashSet<Int>() // a mutable hash set 
    while (reached.add(n)) n = f(n) // iterate function f
    println(reached.size) // print answer to the output
}

Во всех онлайн-соревнованиях по спортивному программированию разрешено использовать заранее написанный код, поэтому можно создать собственную библиотеку вспомогательных функций для спортивного программирования, чтобы сделать код решения более простым для чтения и написания. Затем этот код можно использовать как шаблон для решений. Например, для чтения входных данных в спортивном программировании можно определить следующие вспомогательные функции:

private fun readStr() = readln() // string line
private fun readInt() = readStr().toInt() // single int
// similar for other types you'd use in your solutions

private fun readStr() = readLine()!! // string line
private fun readInt() = readStr().toInt() // single int
// similar for other types you'd use in your solutions

Обратите внимание на использование здесь модификатора видимости private (модификаторы видимости). Хотя понятие модификатора видимости совершенно не важно для спортивного программирования, он позволяет разместить несколько файлов с решениями на основе одного шаблона, не вызывая ошибок из-за конфликтующих публичных объявлений в одном пакете.

Пример функциональных операторов: задача Long Number

При решении более сложных задач пригодится обширная библиотека Kotlin с функциональными операциями над коллекциями: с её помощью можно сократить объём шаблонного кода и превратить его в последовательный конвейер преобразования данных, читаемый сверху вниз и слева направо. Например, для решения задачи задача B: Long Number достаточно простого жадного алгоритма, который можно записать в этом стиле, не используя ни одной изменяемой переменной:

fun main() {
    // read input
    val n = readln().toInt()
    val s = readln()
    val fl = readln().split(" ").map { it.toInt() }
    // define local function f
    fun f(c: Char) = '0' + fl[c - '1']
    // greedily find first and last indices
    val i = s.indexOfFirst { c -> f(c) > c }
        .takeIf { it >= 0 } ?: s.length
    val j = s.withIndex().indexOfFirst { (j, c) -> j > i && f(c) < c }
        .takeIf { it >= 0 } ?: s.length
    // compose and write the answer
    val ans =
        s.substring(0, i) +
        s.substring(i, j).map { c -> f(c) }.joinToString("") +
        s.substring(j)
    println(ans)
}

fun main() {
    // read input
    val n = readLine()!!.toInt()
    val s = readLine()!!
    val fl = readLine()!!.split(" ").map { it.toInt() }
    // define local function f
    fun f(c: Char) = '0' + fl[c - '1']
    // greedily find first and last indices
    val i = s.indexOfFirst { c -> f(c) > c }
        .takeIf { it >= 0 } ?: s.length
    val j = s.withIndex().indexOfFirst { (j, c) -> j > i && f(c) < c }
        .takeIf { it >= 0 } ?: s.length
    // compose and write the answer
    val ans =
        s.substring(0, i) +
        s.substring(i, j).map { c -> f(c) }.joinToString("") + 
        s.substring(j)
    println(ans)
}

В этом компактном коде, помимо преобразований коллекций, можно увидеть такие удобные возможности Kotlin, как локальные функции и оператор Элвиса ?:. Они позволяют лаконично и наглядно выражать идиомы вроде «взять значение, если оно положительное, иначе использовать длину» с помощью выражений, таких как .takeIf { it >= 0 } ?: s.length. Впрочем, в Kotlin вполне допустимо создавать дополнительные изменяемые переменные и выражать тот же код в императивном стиле.

Чтобы сделать чтение входных данных в подобных задачах спортивного программирования более лаконичным, можно использовать следующий набор вспомогательных функций:

private fun readStr() = readln() // string line
private fun readInt() = readStr().toInt() // single int
private fun readStrings() = readStr().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints

private fun readStr() = readLine()!! // string line
private fun readInt() = readStr().toInt() // single int
private fun readStrings() = readStr().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints

С этими вспомогательными функциями код чтения входных данных становится проще и точно следует спецификации из условия задачи, строка за строкой:

// read input
val n = readInt()
val s = readStr()
val fl = readInts()

Обратите внимание: в спортивном программировании принято давать переменным более короткие имена, чем обычно принято в промышленной разработке, поскольку код пишется только один раз и впоследствии не сопровождается. Однако такие имена, как правило, всё же помогают вспомнить назначение переменных: a для массивов, i, j и другие — для индексов, r и c — для номеров строк и столбцов в таблицах, x и y — для координат и так далее. Для входных данных удобнее сохранять имена, указанные в условии задачи. Однако в более сложных задачах требуется больше кода, поэтому приходится использовать более длинные, но понятные имена переменных и функций.

Дополнительные советы и рекомендации

Во входных данных задач по спортивному программированию часто встречается такой формат:

Первая строка входных данных содержит два целых числа n и k

В Kotlin эту строку можно лаконично разобрать с помощью следующего оператора, используя деструктурирующее объявление для списка целых чисел:

val (n, k) = readInts()

Может показаться заманчивым использовать класс java.util.Scanner из JVM для разбора менее структурированных входных данных. Kotlin хорошо взаимодействует с библиотеками JVM, поэтому работать с ними в Kotlin удобно. Однако имейте в виду, что java.util.Scanner работает чрезвычайно медленно. Настолько медленно, что разбор 10⁵ или более целых чисел с его помощью может не уложиться в типичный лимит времени в 2 секунды, тогда как простой split(" ").map { it.toInt() } в Kotlin справится с этой задачей.

Вывод данных в Kotlin обычно не вызывает затруднений: достаточно вызвать println(...) и воспользоваться шаблонами строк Kotlin. Однако следует проявлять осторожность, если вывод содержит порядка 10⁵ строк или больше. Выполнение такого количества вызовов println слишком медленно, поскольку в Kotlin вывод автоматически сбрасывается после каждой строки. Чтобы быстрее вывести множество строк из массива или списка, используйте функцию joinToString(), указав "\n" в качестве разделителя, например:

println(a.joinToString("\n")) // each element of array/list of a separate line

Изучение Kotlin

Kotlin легко изучить, особенно тем, кто уже знает Java. Краткое введение в базовый синтаксис Kotlin для разработчиков программного обеспечения можно найти в справочном разделе сайта, начиная со страницы базовый синтаксис.

В IDEA встроен конвертер Java в Kotlin. Он может помочь тем, кто знаком с Java, изучить соответствующие синтаксические конструкции Kotlin, но конвертер не идеален, поэтому стоит самостоятельно познакомиться с Kotlin и изучить его идиомы.

Отличным ресурсом для изучения синтаксиса Kotlin и API стандартной библиотеки Kotlin служат Kotlin Koans.