Kotlin похож на C#, но более удобный и достаточно быстрый

Для решения задач в последние годы использую Kotlin. Похож на C#, но еще более удобный и достаточно быстрый. ИИ почти не пользовался, проверял через него наличие более простых вариантов решения для пары сложных задач последних дней, (но не просил писать код).

Самая интересная и сложная для меня, пожалуй, вторая задача 10-го дня. Если отбросить сказочную историю, требовалось решить задачу целочисленного линейного программирования Ax=b, минимизировав сумму x_i, где A - матрица из 0 и 1, не обязательно квадратная, а x_i и b_j целые неотрицательные.

Многие решившие использовали ИИ, готовые библиотеки для решения задач ЛП или даже Z3 Theorem Prover. Я решаю AoC для развлечения и тренировки своих мозгов, поэтому решил написать метод Гаусса-Жордана. Это такая вариация метода Гаусса, которая пытается решить систему уравнений, но не ломается в случае если система имеет множество решений, а находит все независимые переменные и позволяет легко выразить зависимые переменные через независимые.

По счастливому совпадению во всех тест-кейсах число независимых переменных варьируется от 0 до 3, поэтому можно просто перебрать все комбинации целочисленных значений независимых переменных, вычислить значения зависимых переменных, отбросить нецелые решения и взять оптимальный ответ. Здесь главное не перепутать минимум с максимумом при получении ответа и не потратить 30 минут на поиски ошибки в методе Гаусса :)

🍒 Вишенка на торте: оказалось, что у второй части задачи есть элегантное решение, использующее идею из первой части и не требующее перебора совсем.

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