Второй тур

Сегодня в МФТИ турнир по информатике в формате CodeForces. Мишка решил четыре задачи на Python, но две из них превысили ожидаемое время. Я захотел ему помочь, попытавшись переписать его алгоритмы на Котлин, но меня подвела последняя IDEA.

Я минут 15 убил на попытки создать простой Котлин-проект, чтобы можно было вызывать main, но двумя разными способами у меня сделать это не получилось. А ведь полгода назад это работало как часы. Пришлось плюнуть и переписать на Java. Хорошо, что простые Java-проекты там ещё не сломаны.

Задачи заковыристые, с подвохом. Имея набор тестов можно было бы додебажиться до правильного решения, но их не дают - приходится черепанить. Первая задача - самая прикольная, ибо куча слов в описании математически сводится до варианта:
print(n == 1 ? 1 : 0)

Jetpack Compose

В принципе, уход из JetBrains дал мне возможность поизучать современные UI frameworks. На этой неделе я осознал всю прелесть в описании формочек для android-телефонов на языке Kotlin. Для конечного пользователя всё выглядит компактно и просто. По крайней мере, пока не приспичит написать какой-нибудь более-менее сложный компонент. Но закопавшись в его исходники я обнаружил, что код в Google пишут ужасно. У языка Kotlin и так-то слабая maintainability, но попытка использовать его в качестве чисто функционального языка превратила исходники в кашу. Возможно, до такого они докатились в процессе оптимизации, но разбираться с этим весьма неприятно.

Справедливые числа

У нас с Мишкой на прошедшем соревновании вторая задача прошла претесты, но в зачёт не попала, так как какие-то тесты упали по времени. Сегодня мы с ним её разбирали.

Основные две оптимизации проверки делимости числа:
1. Сначала я собрал все цифры в Set, который ещё дополнительно уменьшил по следующим правилам:

    val set = mutableSetOf<Char>()
    string.forEach { set.add(it) }
    if (set.contains('9')) set.remove('3')
    if (set.contains('8')) set.remove('2' и '4')
    if (set.contains('6')) set.remove('2' и '3')
    if (set.contains('4')) set.remove('2')
    set.remove('1')
    set.remove('0')

2. Потом я оптимизировал проверку делимости BigInteger, используя признаки делимости на 2, 4, 5 и 8. Но эта оптимизация уже не дала сильный прирост, как предыдущая. И всё равно решение задачи не принимали из-за 11-го теста.

Пришлось долго думать над условием, что же я пропустил и понял, что количество проверяемых чисел в одном тесте может быть большим, но туда могут передавать одинаковые или близкие числа. И я добавил кэш Map<Ref>, чтобы не пробегать второй раз для записи в него.

  data class Ref(var value: BigInteger)
  ...
  val dividend = readLine()!!.toBigInteger()
  val applicable = map[dividend] ?: Ref(dividend).also {
    while (true) {
      map[it.value] = it
      if (test(it.value)) break
      it.value = map[++it.value]?.value ?: continue
      break
    }
  }

В результате решение задачи приняли с временем прохождения 1715 мс. Подумав над условием задачи, я понял, что для неё можно не использовать BigInteger, а достаточно использовать Long. Это позволило сократить время исполнения до 1169 мс, а использование памяти - в два раза (с 130000 до 60000 кб)

Код - это сила!

Чтобы проникнуться динамическим программированием, один из друзей порекомендовал сайт CodeForces. Там можно зарегистрироваться с сыном и выполнять различные задачи из архива. Ну и проверять решение тоже можно. Поддерживается куча языков, даже Kotlin! Хорошая возможность прокачать навыки ещё и в нём.

Я не удержался и сходу решил несколько самых лёгких задач, чтобы опробовать возможности системы:


Судя по всему мне придётся привыкать, что всякие проверки - от лукавого. Для олимпиадного програмирования не нужно проверять входные данные, что позволяет писать код короче:

fun main() {
    val index = readLine()!!.split(' ').map { it.toInt() }[1] - 1
    val list = readLine()!!.split(' ').map { it.toInt() }
    val min = list[index].coerceAtLeast(1)
    println(list.filter { it >= min }.count())
}

Это пример решения задачи Следующий раунд. Как можно заметить, я игнорирую нулевой результат readLine(), а из первого массива беру только второе число, так как первое понадобилось бы только для проверки длины второго массива. Не уверен, нужно ли задавать нижнее значение min как 1, но решение приняли:

Подготовка

Мишу из школы направляют на региональную олимпиаду по информатике и выдали примеры задач для подготовки. Он их делает на Питоне, а потом мы сложные случаи разбираем. Задачи проверяются на сервере, который работает с 9 утра до 9 вечера. Ограничения для всех задач: по времени - 2 секунды, по памяти - 256 мегабайт. Задачи очень разные! Есть элементарные:

Задано четыре числа. Требуется разбить их на две пары, чтобы сумма произведений в этих парах была максимальной. Например, для чисел 2,3,4,5 надо вывести 26 (2*3+4*5).

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

Для целого положительного числа от 1 до 1000 требуется найти число способов представить его в виде суммы нечётных слагаемых. Порядок слагаемых неважен. Например, для числа 6 надо вывести 4. Сами разбиения выводить не надо:
[1+1+1+1+1+1], [3+1+1+1], [3+3], [5+1]

Я сначала решил "в лоб" - прямым перебором, используя Set для фильтрации. Потом ускорил в несколько сотен раз, отказавшись от Set. Это позволило мне обнаружить, что происходит переполнение для больших чисел. Посему мне пришлось заменить long на BigInteger, замедлив программу раза в два.

fun count(array: IntArray, size: Int): BigInteger {
  var count = BigInteger.ONE
  val size2 = size - 2
  if (size > 2 && array[size - 1] == 1 && array[size2] == 1) {
    array[0] += 2
    count = count.plus(count(list, array, size2))
    array[0] -= 2
    var index = 0
    while (++index < size2) {
      if (array[0] == array[index]) continue
      if (array[0] == array[index] + 2) {
        array[index] += 2
        count = count.plus(count(list, array, size2))
        array[index] -= 2
      }
      break
    }
  }
  return count
}

Тут стало очевидно, что после 170 мы перестаём укладываться в две секунды и подсчёт ответа для 400 занял более двух дней:

in: 100; out: 444793; time: 21 ms
in: 200; out: 487067746; time: 7958 ms
in: 300; out: 114872472064; time: 1873429 ms
in: 400; out: 11962163400706; time: 196301147 ms

Написал код для вывода комбинаций и пытаемся анализировать, чтобы для получившейся выше рекурсивной функции вывести формулу, ибо полный перебор - это уже перебор. 8)

IntelliJ IDEA 2020.3

Встречайте новую версию!
А мы начинаем работы над следующим релизом...

Когда люди - дерьмо

Эпический момент на последнем Google I/O на 9'20":

Google I/O

Сидим на седьмом этаже, смотрим конференцию, а там показывают Макса Шафирова и рекламируют Kotlin. Теперь это один из официальных языков для программирования под Android.

Список языков

В этом списке языков программирования даже Котлин есть.

Реверси

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

После небольшой реструктуризации кода всё вылечилось само, а я так и не понял, что всё-таки произошло. Зато понял, что разучился играть в Реверси. Мне так и не получилось обыграть компьютер.

Теперь надо добавить немного рандомизации, чтобы каждая игра немного отличалась от предыдущей, и портировать Пашкин алгоритм, чтобы проводить соревнования.

На следующий год

Kotlin существует только в трёх видах: для JVM, JavaScript и Android; а переносимое приложение написать можно только текстовое через вывод println.

И в этом вопросе язык сильно проигрывает почившему в бозе JavaFX script, в котором существовала Scene с набором 2D-примитивов, анимацией и связыванием переменных. Это позволяло создать переносимое приложение под телефон.

Посему у меня возникла идея для следующего Hackathon: разработать (для начала) библиотеку работы с графикой и реализовать единый интерфейс для всех трёх платформ.

Вот только если для поддержки Swing моих знаний и хватит, то в Android я откровенно слаб, а jquery не знаю вовсе. Да и выполнить всю задачу одному будет непросто. Надо набирать команду...

Неожиданно

В процессе изучения Kotlin я нашёл следующую проблему:

  open class Super(val value: Int) {
      constructor(value: Super) : this(value.value)
  }
  class Sub(value: Int) : Super(value) {
      constructor(value: Sub) : super(value)
  }

Наследник не компилируется, сообщая, что нельзя использовать super в данном контексте, а надо использовать this. Покурив документацию, я всё-таки написал требуемую мне иерархию:

  class SubOK : Super {
      constructor(value: Int) : super(value)
      constructor(value: SubOK) : super(value)
  }

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

PS. Коллеги подсказывают, что похожее поведение у Scala.

Kotlin @ Hackathon

Завершился сорока восьми часовой марафон программирования, на котором я изучал язык Kotlin и писал известно что, а ведь до этого события я его и в глаза не видел.

Первые часов 20 прошли очень результативно, после чего пришлось пойти поспать в комнату отдыха. После обеда работа шла медленно и печально, поэтому я решил поехать домой и выспаться. Сегодня с утра полировал код и пытался найти ошибку в алгоритме подсчёта очков, из-за которой он долго думает, но плохо играет. Ещё не успел портировать Пашкин код.

Язык Kotlin мне понравился. Подобно JavaFX он сильно уменьшает количество boilerplate кода. С другой стороны, код становится плотным и насыщенным, поэтому лучше добавлять комментарии.

  data class Player(val id: Int,
                        name: String?,
                    val solver: Solver? = null) {
      val name = solver?.name ?: name ?: "Player ${id + 1}"
  }

Например, код выше является описанием класса с тремя readonly свойствами id, name и solver, для поддержки которых генерятся методы equals и hashCode.

Конструктор по-умолчанию имеет два обязательных и один опциональный параметр со значением null по умолчанию. String? означает, что параметр типа String может принимать значение null.

Свойство name задаётся не напрямую через конструктор, а на основе выражения, в котором присутствует куча проверок на null. Сначала мы спрашиваем имя solver?.name, которое вернёт null, если сам solver тоже null.

Потом идёт так называемый elvis-оператор, который возвращает левую часть, если она не null, иначе возвращает правую.

Тип свойства name напрямую не задан, а определяется из выражения. С учётом всех проверок на null, типом оказывается String, а не String?, как у соответствующего параметра.

Методы так и подмывает писать однострочными:

  fun count(id: Int) = cells.values().filter { it == id }.size()

Да, λямбды поддерживаются. Кстати, тип объекта внутри if определяется автоматически, если в if этот тип проверялся.

Поддержка range сделана простой и оптимальной в коде:

  x in 1..width && y in 1..height

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

  fun JComponent.getInnerBounds(): Rectangle {
      val bounds = Rectangle(getWidth(), getHeight())
      val insets = getInsets()
      if (insets != null) {
          bounds.x += insets.left
          bounds.y += insets.top
          bounds.width -= insets.left + insets.right
          bounds.height -= insets.top + insets.bottom
      }
      return bounds
  }

После чего можно использовать этот метод, будто он объявлен в классе JComponent. В целом, поддержка Java отличная.

В общем, интересный опыт. Теперь надо готовить презентацию.