Ктулхи у банку: як ми вирішували ICFPC 2015

Невеликий звіт про те, як ми вирішували ICFP Contest 2015. Ми брали участь в даному змаганні вперше, однак результат вийшов досить непоганий. Можна пошукати нас в таблиці проміжних результатів під ім'ям «WILD BASHKORT MAGES». Фінальні результати очікуються протягом декількох найближчих тижнів, коли організатори протестують всі рішення на повному наборі тестів.



В цьому році в якості завдання пропонувалося написати решалку (або ІІ, кому як зручніше) для гексагонального тетрису. Все як у звичайному тетрисе — укладаємо фігурки, прибираємо заповнені рядки, отримуючи за це окуляри. Рішення повинно працювати для різних розмірів ігрового поля і укладаються фігурок довільної конфігурації. Команди дій з фігурками (переміщення і повороти) кодуються звичайними символами, в результаті рішенням є рядок команд. За спеціальні секретні послідовності символів в рядку-рішенні, звані power words, даються додаткові бонусні очки. За сюжетом — дані рядка іменувалися даваром, і організатори збирали його для того, щоб відстрочити пробудження Ктулху.

Введення
Нас в команді було троє, якщо не вважати двох кішок — Дамір, Максим і я. Ми з Даміром — олімпіадники на пенсії, Максим має багато досвіду в написанні компіляторів. В якості попередньої підготовки ми підняли git-репозиторій, трохи почитали інформації про криптографії (бо в анонсі про це навіщось згадувалося), я перевірив, що моя Ubuntu на виртуалке працює (я виндузятник, на відміну від партнерів по команді). Ну і, звичайно ж, ми гарненько проспались перед виступом.

Хоча змагання тривало три доби, в даному оповіданні все буде розбито на 4 дні у зв'язку з нашим годинним поясом. По нашому місцевому часу контест починався у п'ятницю о 17:00, закінчувався у понеділок о 17:00. Тобто, день 1 день 4 дещо спрощеними, що в підсумку дасть рівно три доби. Час в оповіданні приблизне, спеціально його ніхто не записував, воно було відновлено з git-репозиторію.
Технічні деталі нашого рішення виділені такий рамочкою.
Якщо ви не хочете вникати в технічні тонкощі — можете сміливо пропускати, якщо ж вам цікаві саме деталі реалізації — їх буде так простіше знайти. Це все справа не було заховано в спойлери через картинок, на які все ж має сенс мигцем звернути увагу.

День 1. Початок
Отже, контест почався в 17:00. Хлопці вже зібралися, я в цей час ще на роботі, вже збираюся йти. Перед відходом пробіг очима умова задачі. Спочатку не дійшло, що мова йшла про тетріс, було хіба що зрозуміло, що ми маємо справу з гексакональным полем, по якому рухаються якісь юніти. «ШІ для стратежки що-чи треба писати?» — подумав я. До команди підтягнувся приблизно в 18:00, заглянувши по дорозі в магазин за провізією і таким стратегічно важливим ресурсом, як кава.

Близько години ми обговорюємо умову задачі, Дамір паралельно пише візуалізатор на Python. Зрозуміло, що Python може бути занадто загальмованим для підсумкового рішення, тому я починаю писати базові операції з полем і фігурками на C++.

Максим вирішує писати те ж саме, тільки на OCaml. Передбачалося піти відразу в декількох напрямках, після чого відсіяти явно неперспективні. Та й робити що-небудь інше особливо було нічого на початку контесту. Як утопічний варіант — можна було потім об'єднати кілька евристик на різних мовах, запускати всі на кожному тесті, а потім вибирати кращий варіант.

Близько 19:30 готова перша версія візуалізатора, можна подивитися які тести заготовили там організатори. На полі в деяких з них видно дивні послання, вже не power word'и це?



Ще ми там знайшли це:



А я тим часом збираю з виконанням базових команд над фігурками. Зрушувати-то фігурки з гексагональної сітки може і просто, а от повертати — не зовсім тривіально.
У підсумку після деякого праці над папірцем і розбору випадків вийшов наступний код:

void move_pnt( PAR & p, int dir, int d )
{
if (d < 0)
{
d *= -1;
dir += 3;
if (dir>=6) dir -= 6;
}
if ((p.Y & 1)==0)
{
if (dir==0) { p.X -= d; }
else if (dir==1) { p.X - = ((d+1)>>1); p.Y += d; }
else if (dir==2) { p.X + = (d>>1); p.Y += d; }
else if (dir==3) { p.X += d; }
else if (dir==4) { p.X + = (d>>1); p.Y -= d; }
else if (dir==5) { p.X - = ((d+1)>>1); p.Y -= d; }
}
else
{
if (dir==0) { p.X -= d; }
else if (dir==1) { p.X - = (d>>1); p.Y += d; }
else if (dir==2) { p.X + = ((d+1)>>1); p.Y += d; }
else if (dir==3) { p.X += d; }
else if (dir==4) { p.X + = ((d+1)>>1); p.Y -= d; }
else if (dir==5) { p.X - = (d>>1); p.Y -= d; }
}
}


Це дуже важлива функція. Вона зрушує точку, яку їй підсунули, d клітинок у напрямку dir. Після цього операції паралельного зсуву стають зовсім тривіальними, а повороти зробити дуже просто. Для цього для кожної клітинки у фігурці треба обчислити її зрушення щодо точки обертання по двох неколлинеарным напрямами, після чого знайти клітинку, зміщену відносно точки обертання на ті ж самі зміщення, тільки з трохи іншим напрямами:


Код довелося трохи подебажить, до 22:00 все було протестовано, заодно була додана функція вставки і позиціювання нових фігурок на полі, а також перевірка на перетин зі стінами і зайнятими клітинами. Дамір бере мій код і переписує його на Python для вставки в візуалізатор. Максим теж переписує мій код на OCaml для використання у своїй версії рішення.

Вечері, як такого, не було. Перебивалися бутербродами з ковбасою і чаєм/кавою не відходячи від робочих місць. Максим згадав, що в холодильнику лежить курка і її треба приготувати і з'їсти, поки вона не зіпсувалася. Але ми вирішили, що нічого з нею до ранку не трапиться.

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

До 03:00 я дописав код знаходження всіх позицій, куди можна приткнути фігурку перед тим як «заморозити». Разом з послідовністю команд, яка до даної позиції призводить. Максим реалізував усі базові операції на OCaml'е, попутно виправивши пару багів в моєму коді. Дамір додав в візуалізатор можливість керувати фігурками з клавіатури: в цей тетріс можна натурально грати! І зберігати рішення.

На жаль, на ігри вже сил не вистачає — пора спати. В цей день на сні ми вирішили не економити.

День 2. Епізод 1: Lightning Division
Прокидаємося в районі 11 години ранку. Ранковий кава — і знову за роботу.

Дамір дістає із засіків С++ бібліотечку для роботи з JSON, я її прикручую, додаю генератор псевдовипадкових чисел, тупу евристику вибору ходу (вибираю той, де фігурка в підсумку виявиться нижче). І ось воно — готове рішення, яке робить хоч щось! Трохи тестування, дебага і прогін по тестам кваліфікації — і до 14:00 у нас є перший давар.

За цей час Дамір теж без діла не сидить — прокачує візуалізатор, фиксит баги. Тепер в ньому можна прокручувати рішення вперед і назад, у тому числі і покроково. Максим все це час длубається в своєму OCaml рішенні.

Час обіду. На обід курку готувати ліньки, тому замовляємо дві піци. Та й часу, насправді, особливо немає — в 17:00 закінчується так званий Lightning Division. Це особлива номінація, в якій приймалися рішення, написані всього за добу, які вже щось вирішують без урахування power-word'ів. І дуже хотілося туди заслати, тим більше що то вже було на руках.

Як тільки перші рішення були отримані, Максим почав розбиратися з питанням «А як тут взагалі давар і рішення відправляти?», а ми з Даміром на візуалізатор переглядаємо що там наш тупий солвер нам нарешал. В принципі, веде себе цілком адекватно, деякі окуляри навіть отримує. На деяких тестах спостерігаються забавні квантові тунельні ефекти для фігурок, у яких точка повороту відстоїть далеко від, власне, самої фігурки:



До 15:45 паралельно з поглинанням піци було зроблено: я додав до рішення евристику, яка додатково враховує зникання лінії, Дамір пригвинтив до мого рішення роботу з командним рядком згідно специфікації, Максим написав автоматизовану отправлялку рішень пачками прямо на сервер.

Пора готувати архів для Lightning Division. Максим пише Makefile і README, збирає тарбол. Ми з Даміром переглядаємо давар, отриманий з останнього рішення. Начебто помилок особливо немає, тарбол зібраний і випробуваний і у 16:47 ми відправляємо архів на сервер організаторів разом з останніми рішеннями.

Тут Дамір знаходить явно неадекватний давар. Починаючи з деякого моменту рішення починає вести себе дуже дивно — промахуватися повз дірок і ліпити фігурки на стелю. І це неподобство відбувається після того, як повністю заповнюються і видаляються дві сусідні рядки! Майже відразу стало ясно, що це ніщо інше як баг в моєму C++ коді в тому місці, де відбувається видалення заповнених рядків. Тобто в візуалізатор воно видаляє всі рядки правильно, а в моїй реалізації одна із рядків залишається — звідси і асинхронність.

Далі все відбувається як у голлівудському кіно (таймінги приблизні):
16:50 я швидко, але акуратно правлю баг, перетестирую новою версією всі завдання.
16:54 коммичу зміни в git, Дамір намагається тягнути мої виправлення, щоб перевірити в візуалізатор. Але він зробив деякі зміни й по запарці забув їх закоммитить, у підсумку після pull'а у нього виходить якась каша і треба розрулювати страшний merge. Просто Дамір все життя сидів на hg, і на git руку не набив.
16:55 Максим поспішає на допомогу Даміру, розуміє, що у нього там якась жесть, поспішає назад до свого компу. Я тим часом проганяю проблемний тест у себе — ніби більше глюків немає.
16:56 Максим тягне мої правки і швидко збирає новий тарбол.
16:58 запускає скрипт відправки давара останнього рішення на сервер.
16:59 завантажує тарбол на сервер, я тим часом слідкую за часом ось тут. В скрипті відправки давара у нас затримка між окремими тестами, щоб нас ненароком не забанили (попсувала вона нам нерви!), тому відправка гальмує. Рахунок уже йде на секунди: 5, 4, 3...
Ух, встигли! За 3 секунди до дедлайну. Мораль: використання малознайомих інструментів може створити проблеми на рівному місці, в самий відповідальний момент.

Трохи пізніше ми все-таки поцікавилися у організаторів, встигли ми чи ні. Прийшла відповідь:
<galois_kiniry> We see two tarballs submitted by your team, at 11:47 and 11:59. Both are well-formed.
<galois_kiniry> But is C++ really the programming language of choice for discriminating hackers? ;)


День 2. Епізод 2: Змійки, циліндри та кінцевий автомат
Ну, один з найбільш напружених моментів позаду, пора придумувати нормальне рішення. Наприклад, яка враховує використання power-word'ів. Насправді, ідея вже давно витала в повітрі, мало не в перші години контесту, але ми вирішили розвивати її після Lightning раунду — для нього використання power-word'ів було не потрібно. Ми засіли на годинку, формалізували ідею, в підсумку вийшло наступне:
Нехай ми якимось чином ставимо фігурку в кінцеву позицію і «заморожуємо». До цієї позиції можна дійти дуже великим числом способів — ми можемо спочатку хоч по всьому полю протаскать нашу фігурку, набиваючи power-word'и перед тим, як поставити її на потрібне місце. Цей оптимальний шлях ми можемо пошукати за допомогою динамічного програмування.

Нам в стан динаміки треба запхати всю інформацію про становище фігурки. А саме: положення точки повороту, поточний поворот, а також інформацію про те, які команди ми вже вводили, щоб ловити появи нових power-word'ів в послідовності команд.

З другою частиною стану відмінно впорається кінцевий автомат, побудований наступним чином. Нехай маємо n power-word'ів, тоді стан автомата можна представити у вигляді вектора довжини n, i-ий елемент якого позначає довжину префікса i-го power-word'а, який ми вже набрали. Переходи між станами трапляються, коли ми додаємо до рядку команд яку-небудь нову букву. При цьому деякі вже набрані префікси подовжуються на одиничку, інші зменшуються або навіть скидаються на нульову довжину. Коли power-word набирається повністю, ми також відзначаємо цю інформацію в автоматі, а в якості префікса вказуємо найдовший, який збігається з суфіксом.

Приклад побудови автомата можна бачити на картинці трохи нижче. Тут використані три слова: aba, acac та bc. На ребрах вказані символи, за якими ми переходимо, в дужках позначається номер слова, яке ми тільки що набрали.



Power-word'ів у нас мало, літер у них теж не дуже багато, тому автомат можна будувати в лоб, не особливо дбаючи про ефективність рішення — все одно буде швидко.

З першої ж частиною стану динаміки довелося попотіти. Справа в тому, що коли ми рухаємо фігурку до пункту її призначення, нам не можна приходити в одні і ті ж стану. Всього у нас 6 варіантів дій з фігуркою: зрушити вліво, посунути праворуч, посунути вниз і вліво, зрушити вниз і вправо, повернути за годинниковою стрілкою, повернути проти годинникової стрілки. З «зрушити вниз-і-вліво» і «зрушити вниз-і-вправо» все зрозуміло — як тільки ми посунули фігурку вниз, вгору назад її затягнути вже не можемо. Повторення можуть бути коли ми рухаємо фігурку вліво-вправо в одній і тій же рядку і при цьому обертаємо.

Виходить наступна річ. Всі положення фігурки в рядку можна представити у вигляді прямокутної таблиці. Її ширина — ширина поля, а висота — кількість можливих поворотів (1, 2, 3 або 6 — залежно від симетрії фігурки). При цьому верхня сторона таблиці склеєна з нижньої — виходить такий циліндр. І ми своїми ходами переміщаємося з сусідні по ребру клітинки. У підсумку всі ходи на одному рядку ігрового поля можна представити у вигляді змійки, яка повзає по нашому циліндру і намагається не відкусити собі хвіст:



На жаль, при такому підході нам довелося б зберігати у стані динаміки всі відвідані клітини кожного циліндра. При цьому загальне число станів зростає експоненціально. Треба було щось з цим робити. Ми вирішили обмежити переміщення змійки наступному чином: якщо ми пішли з якоюсь рядки, то більше її ніколи не відвідуємо. Тоді всілякі шляхи змійки вироджуються в закарлюки наступного виду:



Всі вже відвідані рядки утворюють певний відрізок (змійка не може переміщуватися, скажімо, через рядок). Звідси — для того, щоб запам'ятати які ми рядки відвідали, треба максимум 36 станів. Додамо сюди ще один параметр: звідки ми прийшли — ліворуч, праворуч або зверху/знизу/c-інший-рядки-ігрового поля-і цього буде достатньо для того, щоб змійка собі хвіст таки не оттяпала.

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

Отже, стан динаміки:
x, y // позиція фігурки, а точніше її точки обертання
rotation // поточний поворот
rot_seg_left, rot_seg_right // відрізок вже відвіданих поворотів
from // звідки ми прийшли: ліворуч, праворуч або зверху/знизу/c-інший-рядки-ігрового поля
node // номер вершини з кінцевого автомата


У кожному стані ми вважали зважену оціночну функцію за трьома параметрами: оцінка ігрового поля коли ми «заморожуємо» фігурку, максимальну довжину використаного power-слова і сумарну довжину всіх використаних слів. Другий параметр був доданий на майбутнє: щоб можна було змушувати динаміку вибирати шлях з раніше не використаними словами (організатори давали 300 очок за кожну power-слово, якщо воно зустрічається хоча б 1 раз і додаткові окуляри (подвоєна кількість букв в слові) за кожне повторення).

Суть динаміки: для кожного стану ми вважаємо максимум оціночної функції, який ми можемо отримати роблячи якісь ходи з поточного стану до якого-небудь «замораживаемого» стану. Ми пробуємо робити всілякі ходи, рекурсивно їх обробляємо, оновлюємо оціночну функцію якщо поточним ходом ми закінчили якісь слова, вибираємо максимум і зберігаємо. Досить тонкий момент для осмислення: здавалося б, інформацію про те, які слова закінчилися ми отримуємо з прямого проходження по рекурсії, але насправді всю потрібну інформацію зберігає в собі сам стан динаміки. Ну і всі знайдені слова ми враховуємо в зворотному порядку їх закінчення.

Динаміку можна вважати ліниво з використанням мемоизации (ну нарешті хоч якийсь натяк на функциональщину!). Просто запускаємо її з початкового положення фігурки і… нахаляву прораховуємо всі положення фігурки, де її можна «заморозити». Якщо додати до кожного станом символ, за яким треба переходити для досягнення оптимуму, то можна легко відновити потрібну послідовність команд.
Десь до 19:00 рішення було формалізовано, залишилося його тільки написати. Дамір засів писати кінцевий автомат, а я пишу саму динаміку (точніше, велика частина часу пішла на облік обмежень, які дає нам стан динаміки). Максим продовжує колупати свою реалізацію на OCaml'е.

До 20:45 Дамір дописує автомат, а я пару хвилинами пізніше дописують динаміку. Мержим код, дивимося що вийшло. Вийшов Stack Overflow. Ну накосячілі я десь в динаміці, тому вона циклится. На пошук бага убилось досить багато часу (виявилася дурна помилка). Після цього я почав проганяти всякі тести і перевіряти, що рішення ніде більше не падає. Роблю commit з виправленим рішенням в 23:45 разом з даваром для тіста 0. Засилаємо його на сервер… і виходимо на першу сходинку по даному тесту!

В цей час ми змінюємо назву команди. Насправді, спочатку ми називалися «Team Bashkortostan». А коли вийшли на першу сходинку по тесту 0 подумали, що назва якась некреативное. Перейменувались в «WILD BASHKORT MAGES». Згадали про курку, думаємо що з нею робити. Вирішили: якщо не викинемо її завтра, то викинемо післязавтра.

Поки я тупил з пошуком бага в динаміці, Дамір без діла не сидів: трохи підкрутив побудова автомата, додав підтримку power-word'ів в візуалізатор, написав модуль підрахунку кількості очок, які повинні дати за давар (цей модуль далі використовувався як у візуалізатор, так і ззовні для автоматичного підрахунку очок і генерації табличок для порівняння). Працювати з візуалізатором стало комфортніше нікуди:



Максим продовжував возитися зі своїм рішенням на OCaml рівно до того моменту, коли ми заслали давар тесту 0 на сервер. Після цього він прийняв вольове рішення забити на свою розробку і зосередитися на тестуванні рішень (щоб відслідковувати не зламали ми рішення після яких-небудь «поліпшень»), а також пошуку нових power-word'ів. Не сказати, що написання рішення на OCaml'е було великою втратою часу — скоріше це було страховкою на випадок якщо я затуплю зі своїм рішенням на З++.

Десь в 00:15 я додав у оцінює функцію ще одну евристику. А саме — штрафи за створення «дірок» в заповненій частині поля. Суть евристики дуже проста: вважаємо кількість таких сусідніх клітинок, що одна з них заповнена, а інша — порожня. Тоді самотня «дірка», залишена на полі, дає штраф 6. Після цього рішення стало працювати набагато краще.

Хоча для тіста 0 рішення було хорошим, з іншими тестами виникли деякі труднощі. Справа в тому, що поточне рішення виявилося тормознутое. Для тіста 14 воно працювало 3 години. Кумедний момент: я взагалі-то хотів запустити рішення для тіста 13, який набагато менше за розміром і всього на 100 ходів (а 14 тест — це та пентаграма на картинці вище з 500 ходами), але трохи переплутав номери тестів. Ну і сиджу чекаю коли воно дорахує. А воно все не дораховує. Через півгодини роботи програми вже стало справою принципу дочекатися завершення. А через годину після запуску нарешті дійшло, що я запустив 14 тест, а не 13. Мабуть, уже давалася взнаки втома. Досчитало воно тільки до 03:45.

Поки я чекав завершення нещасливого 14го тесту (сил окрім як чекати у мене більше не залишалося, але і не засипалась), Максим прогнав коректним рішенням ще трохи тестів і спробував заслати їх на сервер. Парочку встигли перевірити, а останній перевірятися не хоче. Точніше не зрозуміло що там з ним — таблиця результатів просто не оновлюється. Крім того, за деякими вже засланим тестів рахунок в таблиці результатів і наш власний трохи не збігався. Дамір сидить шукає помилку в модулі оцінки рахунку. Вже ніби все перевірив ще раз — немає помилки. Після цього таблиця результатів зовсім падає — виявилося, що хтось посилав на сервер некоректний давар (поганий давар, неякісний) і тим самим поламав перевіряє систему. Організатори незабаром виправили баг, відновили таблицю, а учасникам сказали більше поганий давар не надсилати:



Виправлення бага з таблицею сталося приблизно у той же час, коли у мене дорахувався 14ї тест. В оновленій таблиці рахунок по кожному тесту збігся з нашим локально підрахованим — тобто баг був не у нас і ми його даремно шукали.

Заслали 14 тест і він теж дав дуже хороший результат. Після цього ми до 06:00 займалися тим, що засилали свежепосчитанный давар, Максим спробував руками перевірити-пошукати нові power-word'и. Нових, на жаль, не знайшлося, зате всі ті слова, які були знайдені в тестах («Ei!», «Ia! Ia!», «R lyeh» і «Yuggoth») дійсно виявилися power-word'ами.

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

День 3. Оптимізації і поліпшення
Прокинулися приблизно в 15:30. Максим прокинувся трохи раніше і нарешті приготував курку. З картопелькою. Як раз до того моменту, як прокинулися ми з Даміром. Поснідали (хоча напевно краще сказати пообідали (або повечеряли?)).

В 16:00 повертаємося до нашого рішення. Виявилося, що Даміру вчора не спалося, і він ліг далеко не в 6 ранку. Все це час він оптимізував моє рішення. Виніс обчислення значень оцінює функції в окрему процедуру і закэшировал (що сильно скоротило кількість обчислень одного і того ж). Для прискорення порівнянь структур (і пошуку їх у std::map) стиснув всі в один int64. Реалізував евристику в динаміці, щоб вона віддавала пріоритет раніше не використаним power-словами. Ще він в цілях оптимізації переписав мою динаміку, але щось там зламав. У підсумку вийшло рішення, яке працює набагато швидше вчорашнього, але дає набагато менше очок.

Що саме зламалося після оптимізації динаміки ми так і не зрозуміли, вирішили не витрачати на це час і не ламати голову. Просто взяли і акуратно перенесли динаміку старого коду поверх всіх нових оптимізацій. Виправлення було закінчено до 17:00. І тепер той самий 14 тест, що я вчора вважав 3 години, вважається за 5 хвилин!

Запускаємо прогін всіх тестів. Цей масовий прогін тестів фігурував під тегом «apocalypse_1».

Приблизно в цей час приходить розуміння, що тягати посчитанный давар через git страшенно не зручно. Кожен раз треба коммитить поточні зміни, пушити, потім іншим пуллить давар з репозиторію. А в цей час вже є нестабільні зміни, які треба намагатися в репозиторій не пушити. Коротше, одна морока. Тому ми вирішили перевезти зберігання давара з git на Dropbox з домовленістю, яка якось стихійно склалася вже 2 дні тому: називати посчитанный давар у форматі«solution_%PROBLEM_ID%_%TAG%_%TAG_INDEX%.json» і у всіх завжди різні теги (щоб не затирати давар один одного). За годинку все перенастроювали. І все раптом відразу стало набагато зручніше: сидиш, спокійно пишеш код, а в цей час Dropbox в куточку пише «ось такий-то давар порахувався» і кладе його у відповідну папку. Ніяких зайвих рухів!

Ще одна дрібниця на користь Dropbox. Ми якось не подумали орендувати на час контесту кластер і сиділи з трьома ноутбуками. У мене з i5, у Даміра з i3, а у Максима — що-то ще давня. І коли Максим запускав у себе рішення — все інше починало пригальмовувати. І тут Максим дістає із засіків віддалений сервер. Він, звичайно, не кластер, але на ньому можна було організувати тестування поточних рішень без загальмовування наших власних машин. Ну так от, пуллить і пушити на віддаленому сервері з ризиком нарватися на конфлікти — не найкраща ідея (доведеться розрулювати через термінал). А Dropbox там вже стояв. Сказано — зроблено. Після недовгої налаштування віддалений сервер почав тестувати рішення на повному наборі тестів, автоматично через Dropbox закидаючи на наші машини вироблений давар. Краса!

До цього моменту тестування на повному наборі тестів завершено. Засилаємо давар на сервер і потрапляємо в трійку лідерів. Фхтагн!

Тим часом, в нашому рішенні ще є багато чого, що можна поліпшити. Основних напрямів два: замінити std::map на хеш-таблиці і прискорити обчислення оціночної функції (вона обчислювалася за O(розмір поля), хоча її можна обчислювати за O(кількість елементів в фігурці)). Я пишу хеш-таблицю, прикручую до вирішення. Ще я додаю до оцінює функції четвертий параметр, так званий «потенціал» — сумарну довжину префіксів ще не закінчених power-слів. Це дозволяє додатково збирати слова між ходами. В 22:30 ніби все готове. З хеш-таблицею тест 14 вважається хвилини за 3.

За цей час Максим написав «долбилку» сервера організаторів для визначення нових power-word'ів. Її принцип досить простий:
  • Запускаємо рішення зі списком слів, підозрюваних на властивість power.
  • Перевіряємо отриманий давар, що він дійсно містить всі підозрілі слова зі списку.
  • Помічаємо цей давар унікальним тегом і засилає на сервер організаторів.
  • Далі разів у хвилину автоматично перевіряємо таблицю результатів, поки там не з'явиться потрібний тег.
  • За підсумковим рахунком виноситься вердикт про «волшебности» використаних слів.


Дамір ж вивчав у візуалізатор отриманий раніше давар. Як виявилося, тести, у яких багато вільного місця для нас були хорошими — наша динаміка у всю використовувало його для набивання power-word'ів. Поганими ж виявилися тести, в яких місця було мало, фігурки були всяких складних форм, а загальна кількість фігурок, які треба було укласти, було великим. Наша тупа оцінювальна функція просто якось їх там укладала і поле досить швидко забивалося, тому на цих тестах ми отримували мало очок. Зокрема, такими тестами були тести з номерами 4, 9, 13 і 23. Ми вирішуємо для маленького поля прикрутити прорахунок на 2 ходи вперед.

В процесі засилання нового давара ми помічаємо дві команди в п'ятірці лідерів з назвами «Hack the pool» і «Hack the loop». І вирішуємо трохи побешкетувати… Переименовываемся в «Hack the poop». Ось він, апофеоз нашого хуліганства:



В офіційному irc-чаті один з адмінів обурюється «Ну що за неподобство?», але начебто не банить. Через пару годин перейменувалися назад у «WILD BASHKORT MAGES». Посміялися — і вистачить.

03:00. Я реалізував перебір на 2 ходи вперед. Насправді він був написаний набагато раніше, але там, як завжди, виникли баги. Найперший з них — ось ніби вже все має працювати, а не працює! Спочатку думали, що взагалі якась чортівня. Потім зрозуміли, що ми ідіоти — треба ж для другого ходу нову фігурку створювати вгорі поля. Коли цей баг був виправлений — зразок запрацювало.
Але працювало воно якось так:



Логіка програми приблизно наступна: «Якщо я поставлю одну фігурку ліворуч, а потім ще одну праворуч — я зберу стрічечки...». Тому програма ставить фігурку ліворуч. На наступний хід програма думає: «Якщо я поставлю одну фігурку куди попало, а потім поставлю наступну праворуч — я зберу стрічечки...». Ну і ставить першу фігурку куди попало. На наступних ходах відбувається те ж саме, програма як би говорить нам: «Так встигну я зібрати цю сходинку, чого прив'язалися!». Але така поведінка нам не треба, нам вигідно якомога швидше розчистити все поле щоб потім набивати power-word'и. Вирішили проблему за принципом «перше слово дорожче другого»: даємо першого ходу невеликий бонус, тому якщо до якогось стану гри можна прийти кількома способами, вибирається той, який приносить більше очок на першому ходу.
Нове рішення стало набагато краще справлятися з 4 тестом. Але, на жаль, все ще не ідеально. Дамір, перевіряючи в візуалізатор різні значення початкового random seed, говорить: «Ось, знову поле забилося». Я підтверджую: «Так, поле забилось у куток і боїться звідти вилазити». Вирішили, що треба все-таки перевіряти на 3 ходу вперед. На жаль, перебір на 2 ходи вперед вже дуже сильно загальмував наше рішення, тому його потрібно додатково прискорювати. Але у нас залишилася ще одна ідея в запасі: прискорення обчислення оціночної функції.

Поки я писав перебір на 2 ходи вперед, Дамір придумував евристики для того, щоб побороти тест 9. Суть цього тесту зводилася до того, щоб накидати на рівень більше палиць, при цьому стабільно збираючи рядка і, по можливості, не заваливаясь. Наше рішення працювало як-то так:



При цьому воно заваливалось на 35 ходу з 400 можливих. На жаль, нічого робітника в той пізній вечір Дамір не придумав.

Максим же все це час збирав підозрілі слова і тестував їх на те, що вони є power-word'ами. До 03:00 було знайдено чи 6, 8 таких слів (разом з тими 4, що ми знайшли раніше). Паралельно він запускав наше рішення зі все більшою кількістю знайдених «чарівних» слів і засилав отриманий давар на сервер. Таким чином, пройшли ще 3 апокаліпсису, тобто останній тег масового тестування був «apocalypse_4».

Після вечері в 3 години ночі (на цей раз були якісь заморожені овочі + гриби + покришені сосиски, розігріті всі разом на сковорідці) Дамір пішов спати (все-таки мало спав у попередню ніч), Максим продовжував довбати сервер організаторів підозрілими словами, а я сів прискорювати оцінну функцію.

Оціночна функція була переписана з O(розмір поля) на O(кількість елементів в фігурці) приблизно в 5:00. Поганяв — ніби стало швидше, значить, вже можна пробувати замахнутися на 3 ходу. Сьогодні замахивать вже немає сил, я лягаю спати на 3-4 години.

День 4. Фінальний ривок
Я прокидаюся десь в 9-10 ранку, Дамір трохи пізніше.

Максим вночі не спав (і не зібрався спати до самого закінчення контесту). За ніч він знайшов ще кілька «чарівних» слів, мало не распарсивая цілі статті з Вікіпедії, які так чи інакше пов'язані з Ктулху. Разом знайдених power-word'ів стало 10. Ось вони:
ei!
yuggoth
ia! ia!
r lyeh
necronomicon
planet 10
monkeyboy
john bigboote
in his house at r lyeh dead cthulhu waits dreaming.
yoyodyne
На жаль, як з'ясувалося після контесту, підхід для пошуку цих слів був ідеальний не до кінця. Наприклад, слово «Yog-Sothoth» було відкинуто, оскільки там містився дефіс. Виявилося, що «YogSothoth» (без дефіса!) виявилося power-word'ом! Загалом, не здогадався Максим просто викидати зайві дефіси. Ще момент: Максим перевіряв слово «laundry», проте силу мала рядок «the laundry». Також незрозумілість трапилася з «ph'nglui mglw'nafh cthulhu r lyeh wgah'nagl fhtagn.». Ця фраза була «чарівної», але наша процедура цього чомусь не підтвердила.

Ще Максим вночі провів п'ятий апокаліпсис з усіма 10 знайденими «чарівними» словами.

Вранці поки ми з Даміром прокидалися, Максим збігав в магазин за енергетиками (прогулявся на свіжому повітрі), щоб у нас вистачило сил для фінального ривка.

Робота пішла за трьома напрямками: я почав писати перебір на 3 ходу вперед, Дамір продовжив гратися з евристикою для 9 тіста (у нього з'явилися деякі нові ідеї), Максим почав писати скрипт, який парсити весь наш попередній давар, вибирає для кожного тесту/seed'а максимум і збирає це все воєдино.

Приблизно о 12:30 Дамір нарешті написав нормальну евристику для оціночної функції, яка набагато краще грає на тесті 9: затикається на 110 ході з 400, а не 35, як було раніше. Крім того, Дамір написав код, який запускає пошук рішення 2 рази: спочатку з новою оціночної функцією, потім зі старою. Для обох випадків вважає кількість очок і виводить у відповідь той варіант, де очок більше. Після цього Дамір з Максимом переключаються на компонування фінального тарбола і потихеньку пишуть README для журі.

Я дописую перебір на 3 ходу до 14:00. З ним довелося повозитися: додати ще декілька оптимізацій, щоб прискорити процес. Крім того, перебір третього ходу довелося трохи обрізати (бо інакше було зовсім тормознуто), а саме: перевіряти третій хід тільки у тих гілок, які самі перспективні. Тобто спочатку ми запускаємо перебір другого ходу «вхолосту», обчислюючи значення оціночних функцій без запуску третього ходу. Серед отриманих значень відсіваємо близько 10 максимальних і запускаємо перебір другого ходу вже «вбоевую»: при цьому пробуємо робити третій хід тільки з тих самих близько 10 оптимальних станів.

Те, що вийшло, вирішує 4 тест дуже і дуже круто. Майже по всім варіантам random seed знаходить вирішення в 200 ходів з 200. При цьому за отриманими даваром в візуалізатор було дуже цікаво спостерігати:



До 14:40 спільно з Даміром мержим дві наші модифікації. Начебто все проходить без особливих труднощів. Максим дописує скрипт для оптимального компонування давара. Збірний оптимальний давар йде під тегом «panopticum», засилає його на сервер.

Запускаємо останнє рішення за повному сеті. До дедлайну (17:00) залишається близько двох годин.

Тут у нас виникають деякі суперечки: а яке рішення, власне, запаковувати в тарбол? Те, що отримали зараз або те, яке у нас було вранці? Справа в тому, що нове рішення поки ще толком не протестовано, на відміну від ранкового + нове рішення стало помітно тормознутее ранкового. Тобто є ризик не встигнути його нормально протестувати і підсумку заслати лажу. А те, що у нас було вранці — типу вже перевірений стабільний реліз. Все-таки вирішуємо запакувати новий варіант.

Тим часом нове рішення тестується і, судячи з його продуктивності, стає ясно, що до дедлайну є шанс і не вкластися. У спішному порядку раскидываем розрахунок різних тестів на різні машини. У підсумку за півтори години до дедлайну порахували всі тести крім 4, 6 і 24. Справа в тому, що 4 та 6 тести мають маленький розмір поля, тому на них запускається перебір на 3 ходу вперед. Крім того, у кожному з них 50 подтестов (різні random seed) на 150 або 200 ходів. Наш перебір на 3 ходу вперед вимагає близько секунди на хід, тому стає ясно, що, скажімо, на весь 4й тест треба близько 3 годин часу. А у нас немає 3 годин часу! З 24 тестом ситуація трохи інша: хоча там лише 1 подтест, там дуже велике поле і 1620 ходів для обробки — на нього теж треба близько 3 годин.

У підсумку ми вирішуємо забити на 6 і 24 тести, а 4й тест розпаралелити на 5 підзадач (по 10 подтестов у кожній), порахувати на різних машинах, потім руками все склеїти. Сказано — зроблено. Вважаємо. Близько 16:00 (за годину до кінця) у Даміра від перегріву здихає ноут. Ну, не зовсім здихає, просто перезавантажується і тим самим 2 з 5 паралельних гілок губляться. Ну, робити нічого — Дамір починає рахувати свої гілки заново. Поки вони вважаються, Дамір ставить свій ноутбук на 2 склянки і потім створює навколо нього потоки повітря для кращого відведення тепла. До 16:20 у нас все дорахувалося, причому одночасно. Ну що поробиш, у нашому рішенні багато операцій з int64, у Даміра 64-бітний Лінукс, а у мене 32-бітна Вінда.

Відправляємо останній давар, дооформляємо тарбол, засилаємо. Через кілька хвилин Максим знаходить граматичну помилку у файлі README, править її, засилає виправлений тарбол за хвилину до кінця (все у нас якось в останній момент).

Епілог
Коли ми засилали останній давар — ми були на другій сходинці кваліфікаційної таблиці. Трохи згодом свій давар заслали Unagi і змістили нас на третю сходинку.

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

Наш репозиторій можна знайти на гітхабі (під час контесту він був в іншому приватному місці, на гитхаб перекинули тільки зараз). Можна поганяти/повивчати наші рішення/візуалізатор. У таблиці нижче можна бачити деякі наші рішення, запущені на всіх 18 power-word'ах, які стали відомі після закінчення контесту.



Спасибі всім, хто дочитав до кінця!

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.