Intro

Доброго дня, сьогодні з вами на зв’язку команда EyesUpgGardgian, яка приймала участь у ICFP Programming contest

Для тих, хто не знає, що то є: ICFP Programming Contest - це щорічне командне змагання зі спортивного 🤔 програмування, на 72 години. Зазвичай, можна використовувати будь яку мову програмування, і кількість людей в команді рідко буває обмежена.

Team Up

Зазвичай, у нас є деяка кількість людей, які час від часу приймають участь в цих змаганнях, і ми гуртуємося за декілька місяців, прикидуємо, хто буде, на чому будемо писати, і таке інше. Цього року, як ви всі розумієте, через те, що росія досі знаходиться на території нашої держави, і у людей зараз зовсім інші пріорітети ніж у звичайні роки. Тому активність людей в чаті була на мінімумі. Крім того, самі дати змагання цього року співпали з початком учбового року, що ще зменшило і так невелику потенційну кількість учасників. Це я ще мовчу про те, що за тиждень до початку змагань в мене народилася дитина ¯\_(ツ)\_/¯.

Власне це думка про те, що потенційно в цьому році, могло нічого і не вийти. Але якось вийшло.

Start?

У день початку змагань, я розумію, що потенційно, деякий час я все-таки зможу виділити на “трошки поICFPFшити” ( режим устаканився, всі мої більшість часу сплять, тому чом би й ні).

Я зконтактував з @nobidon (єдиною людиною, хто якось виявляв активність). І ми вирішили, що б хоча б в Lighting Round (перші 24 години), ми участь приймемо.

Language Selection

Цього року довго роздумувати не довелося, тому що, ніяких домовленостей не було, і ми просто використали Kotlin (знову). В цілому, через те що, у нас був тогорічний проект, можна втягувати Java libraries, і… і не знаю чому, але досі, якщо мене запитати, що я виберу між Swift і Kotlin, нажаль?, я виберу Kotlin. (Можливо, наступного року 😏)

В ультра швидкі терміни, я створюю новий репозиторій, вибираю все необхідне з попередньгоо року (куча helper-функцій та методів, які душе пришвидшують роботу в такого роду змаганнях). Затягнува візуалізатор з попереднього року, і зробив можливість писати тести.

visualizer

+1 Player (Github copilot)

До цього часу, я бачив Github Copilot тільки на відосах, і використовувати його не доводилося, але чомусь, при підготовці, я натрапив на посилання про нього, і виявилося, що через те, що свого часу я багато комітив в Open Source, я можу його використовувати Free. (Ось вона, сила Open Source).

Тому, в нашій команді стало на одного учасника більше. (Github Copilot зіграв дуже значну роль цього року, але про це пізніше)

Day 1

15:00 - Команда EyesUpGuardian у складі Олексія (@nobidon), Павла (@TT_Kilew) і Github Copilot починає свою участь у ICFP Contest 2022

Завдання

Якщо дуже спростити, то завдання цього року було у трансформуванні одного зображення в інше за допомогою заданого набору команд. commands

Особливістю цього завдання, що з одного боку, треба було якнайточніше відобразити задане зображення, а з іншого боку, команди, якими мали оперувати команди, мали свою ціну, і чим з меншими блоками доводилося працювати, тим більша була ціна команди. (Наприклад, замалювати всю картинку 400х400 пікселів “коштувало” 1 одиницю, а замальовування блока 40х40 обійшлося б у 100 одиниць. Операції з меншими блоками - були ще дорожчими)

15:03 - ми розбираємо задачі, я беру на себе зробити базову структуру, яка дозволить використовувати команди, а Льоша пише клас, який дозволить серіалізувати нашу програму для подальшої відправки на сервер.

No solution is a solution

Завжди перевіряйте, чи можете ви відправити свої результати.

Просканувавши специфікацію завдання, я не побачив там ніякої інформації про API для завантаження рішень, і вирішив подивитися, що є на сайті. На сайті була форма, яка дозволяла відправити “програму” для кожного завдання, і показувала результат, який ми отримуємо. В формі не можна було відсилати “пусте” значення, відповідно що треба було надсилати правильні команди 😢. Але, звернувши увагу, що програма допускає пусті рядки, і коментарі, я швидко вирішив запостити пусту програму з коментарем. І…. і отримав результат!

<program>               ::= <program-line> | <program-line> <newline> <program>
<program-line>          ::= <newline> | <comment> | <move>
<comment>               ::= "#" <unicode-string>

15:24 - Я швидко пробігся по всім задачам і відправив “пусті рішення”. Це дозволило нашій команді посісти 3-те місце! 🎉 (Я люблю казати, що в цьому змаганні - головне - це вчасно зробити скріншот)

standings

15:51 - У нас є код, який дозволяє завантажувати проблеми у вигляді, з яким ми можемо нормально працювати. Поки базова ідея - це просто спрочатку якимось чином розбити картинку на декілька блоків, визначеного кольору, і намагатися після іх зафарбувати.

17:21 - Нарешті, ми можемо правильно обчислити, наскільки ми “промахнулися” зі згенерованою картинкою. Оновлюємо базове рішенння. Тепер замість пустої картинки ми просто надсилаємо квадрат, який замальований усередненим кольором того, що треба отримати :) Це дозволяє нам піднятися на 12 місце. Водночас, дивуємося, що іноді “усереднений колір” дає гірші результати, ніж пусте рішення🤔. Я, тим часом, відпадаю на декілька годин.

18:22 - У нас з’являється інтерпертатор, за допомогою якого ми можемо дуже зручно писати код, який потім трансформується в команди. В основному, це дозволяє легко оперувати блоками, які утворються після розрізання картинки

val builder = ISLBuilder()
builder.color(builder.root, Color(100, 100, 100, 255))

21:20 - Льоша дописує інтерптератор, намагаючись перемогти playground, який був предоставлений організаторами - той видає помилки, в залежності від браузера. Але тепер можемо рахувати наскільки важкими виходять наші програми.

21:30 - API для upload’а все ще немає, а заливати рішення руками, якось не дуже хочеться. Тому, підгледівши за допомогою Chrome Dev Tools, що саме, і куди надсилає сервер, ми реверс-інжініримо протокол обміну, і робимо собі можливість надсилати рішення в автоматичному режимі. Для тесту - надсилаємо всі рішення сірим кольором, і вони всі проходять. Треба сказати, що в умовах не було сказано, чи враховуються тільки кращі надіслані рішення, чи останні, і заливка нових рішень дозволила перевірити це питання.

22:07 - Бачимо, що порахована нами вартість дуже сильно розбігається з тим, що рахує сервер. В два підхода, міняємо всі Int на Double і отримуємо правильний результат*. Насправді, результат коливався десь в рамках декількох одиниць, але на фоні вартості у тисячі, це було не дуже принципово.

22:32 - Ми оформлюємо абстрактний “вирішувач” Solver, задача якого по заданій картинці повернути набір команд. Для тесту - розбиваємо основну картинку на дві частини і заливаємо їх усередненим кольором. Наче все працює. Одразу додаємо візуалізацію того, яку картинку ми надсилаємо, і зберігамо рішення, з його оцінкою.

2_23523.solution

22:35 - На разі - єдина ідея, куди рухатися далі - це писати вирішувач, який буде пропонувати розрізи блоку, фарбувати їх усередненим кольором, і дивитися, який розріз призведе до кращого результату.

23:45 - Пробуємо розріати картинку 4х4 і зафарбувати. Вигрібаємо на тому, що осі координат у нас направлені як попало в різних місцях. Через це, ми генеруємо перевернуту картинку, а місцями, наші команди фарбування, розфарбовують не там де треба. В цілому, не проблема - треба просто дивитися на згенеровані картинки - ось так:

Day 2

00:12 - дописуємо можливість робити так, що будь який “вирішувач”, який вирішить задачу з кращим результатом - зберігає свій результат, а всі інші ігноруються. Крім того, додали можливість в один запуск - відправити на сервер всі найкращі рішення, які на цей час згенерували. На майбутнє це дозволяло запустити вирішувачі задач з різними параметрами на деякий час і піти пити чай, а потім повернутися, і просто залити найкращі рішення.

01:18 - додаємо варіант вирішувача, який розбиває картинку на N рівнів і фарбує все що можна.

03:54 - я переписую логіку, як ми генеруємо рішення - ми йдемо в два кроки - спочатку генеруємо можливі варіанти, після цього вибираємо один з найкращих, і так до тих пір, поки у нас є можливість робити дії (розрізи, або фарбування), не збільшуючи вартість програми. Рішень стає забагато, і доводиться ннаписати скріпт, який підчищає не найркащі рішення.

05:40 - запускаємо наші алгоритми, всі що є, і йдемо спати, поки комп’ютери працюють.

sleep

08:40 - після недового сну, бачимо, що ми нарішали на 13 місце, що в принципі, не так погано, зважаючи на обставини.

09:40 - оптимізуємо вирішувач, який дозволяє не фарбувати все підряд, а робити розріз картини на 9 частин;, і фарбувати лише одну. Часу ні в кого з нас немає, тому просто запускаємо рішатори, і йдемо по справах.

13:40 - залишається менше ніж дві години до кінця Ligting Roundу (окремий залік, коли враховуються рішення, які були дані в перші 24 години). Єдина оптимізація, до якої в мене доходить голова - це після того, як сформована програма, перевірити, а чи не можна, часом підтюнити кольори, якими ми фарбували картину. Логіка полягала в тому, що якщо ми фарбуємо блоки наприклад у колір Х, а потім частину цього блоку знову їх перефарбовуємо у новий колір Y, то нам вже не суть важливі ті пікселі, які перетерлися новим кольором. І можна перерахувати колір Х в Х’, так, щоб отримати краще значення, обраховуючи лише ті пікселі, які залишилися.

doges

15:00 - Кінець Lighting Round’у. Ми підтягнули свої результати, і отримали зрізали пару тисяч балів, за допомогою різних оптимізацій. Набагто пізніше, ми дізнаємося, що зайняли 29 місце.

P.S. Вважаю, зайняте 29 місце, скоріше перемогою, ніж зрадою :). Часу було обмаль, нас було двоє + Github Copilot. Звичайно, приємно було б попасти хоча б в топ 10, але, маємо що маємо :)

Day N

New Tasks

Далі були ще два дні контеста, в яких ми приймали участь виключно епізодично, і просто підтримували код, щоб він міг працювати з новими типами завдань. Так, спочатку додалися завдання, які були розділені на багато частин. Тому спочатку треба було частинки об’єднати, і вже потім фарбувати.

В теорії, організатори розраховували на те, що учасники будуть використовувати початкові кольори і блоки, але, наскільки мені відомо, всі команди пішли шляхом - спочатку об’єднуємо всі блоки за найменшу вартість, а потім вирішуємо попередню задачу.

Moar optimizations

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

Так, багато часу займали операції з картинками, і роботою з пікселями, тому базові функції бібліотеки просто довелося заінлайнити

red += color shr 16 and 0xFF        //    red += color.red() 
green += color shr 8 and 0xFF       //    green += color.green()
blue += color and 0xFF              //    blue += color.blue()
alpha += color shr 24 and 0xFF      //    alpha += color.alpha()

Дуже вчасно ми згадали, що порядок обходу у картинках дуже важливий, і просто помінявши порядок обходу пікселів, ми пришвидишили функцію в три з гаком рази

// Fast Version (3x speedup)
val imageData = (image.awt().raster.dataBuffer as DataBufferInt).data
for (y in block.minY.value until block.maxY.value) {
    for (x in block.minX.value until block.maxX.value) {

// Slow Version
val imageData = (image.awt().raster.dataBuffer as DataBufferInt).data
for (x in block.minX.value until block.maxX.value) {
    for (y in block.minY.value until block.maxY.value) {

Github Copilot

Окремо хочеться сказати про Copilot. Я був приємно вражений тим, наскільки швидко за допомогою нього можна писати код. Без нього, не факт, щоб нам вдалося наблизитися до тих результатів, які ми отримали. Часто я просто перестав перевіряти те, що він пропонує і просто давав змогу згенерувати код.

Ось такого коментаря було майже достатньо, щоб зробити те, що я хотів

// parse list of initial blocks from json file

А коли я зрозумів, що для того, щоб правильно розпарсити JSON, йому не вистачає контексту, то просто додавши приклад JSONу, моментально отримав код, який розпарсив його і розклав в мої модельки

// {"width": 400, "height": 400, "blocks": [{"blockId": "0", "bottomLeft": [0, 0], "topRight": [
val blockId = block.jsonObject["blockId"]!!.jsonPrimitive.int
val bottomLeft = block.jsonObject["bottomLeft"]!!.jsonArray.map { it.jsonPrimitive.int }
val topRight = block.jsonObject["topRight"]!!.jsonArray.map { it.jsonPrimitive.int }
val color = block.jsonObject["color"]?.jsonArray?.map { it.jsonPrimitive.int }

Магія ✨. Всім раджу хоча б спробувати.

Results

Ми, команда EyesUpGuardian, заняли десь

29 місце за перші 24 години
47 місце в результаті, за 72 години.

Чи ми задоволені? І так і ні :) Завжди хочеться бути вище, сильніше і краще. Але свою частину веселощів ми отримали, ну то й добре.

P.S.

Окремо хочеться подякувати ЗСУ і всім Українцям, які зараз дають можливість мирно робити свої справи під час війни.

Для того, щоб наступного разу ми, як команда виступили краще, треба задонатити сюди :)

savelife.in.ua

Слава Україні! 🇺🇦