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

Это руководство предназначено как для Kotlin-разработчиков, которые ранее не участвовали в соревнованиях, так и для людей, имеющих опыт в спортивном программировании, но не использовавших ранее Kotlin. Так же это руководство предполагает, что вы имеете соответствующие навыки программирования.

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

Подробнее о том, как настроить среду разработки для Kotlin, смотрите в разделе Начало работы с Kotlin/JVM. В спортивном программировании обычно создается один проект, и решение каждой задачи записывается в одном исходном файле.

Простой пример: задача достижимых чисел

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

Codeforces Round 555 состоялся 26 апреля для 3-го дивизиона, это значит, что в нем были задачи, которые мог бы решить любой разработчик. Вы можете воспользоваться этой ссылкой, чтобы ознакомиться с ними. Самая простая задача в наборе - это задача A. Достижимые числа. В ней предлагается реализовать простой алгоритм, описанный в условии.

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

Давайте объявим функцию f(x) следующим образом: добавим 1 к 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 и изменяемые переменные, обозначаемые с помощью 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() // считывание целого числа с входных данных
    val reached = HashSet<Int>() // изменяемый хэш-набор
    while (reached.add(n)) n = f(n) // повторяемая функция f
    println(reached.size) // вывод ответа
}

Функция readln() доступна начиная с версии Kotlin 1.6.0.

В спортивном программировании нет необходимости обрабатывать случай неправильно отформатированного ввода. Формат ввода всегда точно задан и не может отклоняться от спецификации ввода в условии задачи. Поэтому можно использовать функцию readln(). Она выбрасывает исключение, если входная строка отсутствует. Аналогично, функция String.toInt() выбрасывает исключение, если входная строка не является целым числом.

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

private fun readInt() = readln().toInt()
private fun readStr() = readln().toString()
// и так далее для других типов, которые вы будете использовать в своих решениях

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

Пример функциональных операторов: Задача длинного числа

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

fun main() {
    // чтение входных данных
    val n = readln().toInt()
    val s = readln()
    val fl = readln().split(" ").map { it.toInt() }
    // определение локальной функции f
    fun f(c: Char) = '0' + fl[c - '1']
    // жадное нахождение первого и последнего индекса
    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
    // компоновка и вывод ответа
    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 readInt() = readln().toInt() // одиночный int
private fun readStrings() = readln().split(" ") // список string
private fun readInts() = readStrings().map { it.toInt() } // список int

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

    // чтение входных данных
    val n = readInt()
    val s = readln()
    val fl = readInts()

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

More tips and tricks

Проблемы конкурентного программирования часто имеют следующий ввод:

В первой строке входных данных записано два целых числа n и k.

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

val (n, k) = readInts() 

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

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

println(a.joinToString("\n")) // каждый элемент массива/списка отдельной строкой

Изучение Kotlin

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

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

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