Оригинал: https://kotlinlang.org/docs/competitive-programming.html

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

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

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

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

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

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

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, прямая императивная версия решения задачи может быть записана так, как показано ниже.

Kotlin 1.6.0 и новее

fun main() {
    var n = readln().toInt() // считывание целого числа с входных данных
    val reached = HashSet<Int>() // изменяемый хэш-набор
    while (reached.add(n)) n = f(n) // повторяемая функция f
    println(reached.size) // вывод ответа
}

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

Более ранние версии

fun main() {
    var n = readLine()!!.toInt() // считывание целого числа с входных данных
    val reached = HashSet<Int>() // изменяемый хэш-набор
    while (reached.add(n)) n = f(n) // повторяемая функция f
    println(reached.size) // вывод ответа
}

Обратите внимание на использование оператора утверждения not-null !! после вызова функции readLine(). Функция Kotlin readLine() возвращает nullable-тип String? и возвращает null в конце ввода, явно заставляя разработчика обработать случай отсутствующего ввода.

В спортивном программировании нет необходимости обрабатывать случай неправильно отформатированного ввода: формат всегда точно задан, а фактические входные данные не могут отклоняться от спецификации в условии задачи. Именно это по сути делает оператор утверждения not-null !!: он проверяет, что входная строка присутствует, и иначе выбрасывает исключение. Аналогично ведет себя и функция String.toInt().

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

Kotlin 1.6.0 и новее

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

Более ранние версии

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

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

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

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

Kotlin 1.6.0 и новее

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)
}

Более ранние версии

fun main() {
    // чтение входных данных
    val n = readLine()!!.toInt()
    val s = readLine()!!
    val fl = readLine()!!.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 вполне можно создать дополнительные изменяемые переменные и выразить тот же код в императивном стиле.

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

Kotlin 1.6.0 и новее

private fun readStr() = readln() // строка
private fun readInt() = readStr().toInt() // одно целое число
private fun readStrings() = readStr().split(" ") // список строк
private fun readInts() = readStrings().map { it.toInt() } // список целых чисел

Более ранние версии

private fun readStr() = readLine()!! // строка
private fun readInt() = readStr().toInt() // одно целое число
private fun readStrings() = readStr().split(" ") // список строк
private fun readInts() = readStrings().map { it.toInt() } // список целых чисел

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

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

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

Дополнительные советы и приемы

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

В первой строке входных данных записано два целых числа 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.