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
работает крайне медленно. Настолько медленно, что
парсинг 105 или более целых чисел с его помощью может не уложиться в типичный двухсекундный лимит времени, с
которым справится простой Kotlin конструкция split(" ").map { it.toInt() }
.
Написание вывода в Kotlin обычно не вызывает затруднений, если использовать вызовы println(...)
и строковые шаблоны Kotlin. Однако следует быть осторожным, когда вывод содержит
порядка 105 строк или более. Выполнение такого количества вызовов println
будет слишком медленным,
поскольку вывод в Kotlin автоматически очищается после каждой строки. Более быстрый способ записать много строк из
массива или списка - использовать функцию joinToString()
с "\n"
в качестве разделителя, например, так:
println(a.joinToString("\n")) // каждый элемент массива/списка отдельной строкой
Изучение Kotlin
Kotlin прост в изучении, особенно для тех, кто уже знает Java. Краткое введение в базовый синтаксис Kotlin для разработчиков программного обеспечения можно найти непосредственно в статье Основной синтаксис.
В IDEA есть встроенный конвертер Java в Kotlin. Он может быть использован людьми, знакомыми с Java, для изучения соответствующих синтаксических конструкций Kotlin, но он не совершенен, и все же вам самим стоит ознакомиться с Kotlin и изучить идиомы Kotlin.
Отличным ресурсом для изучения синтаксиса Kotlin и API стандартной библиотеки Kotlin являются Kotlin Koans.