У нас были: три демодулятора, пачка интерпретаторов, парсер битовых картинок и целый ворох различных функциональных комбинаторов. Не то, чтобы всё это было нужно для финального зачёта, но если уж собрался участвовать в ICFPC, нужно идти в этом деле до конца.

Антон Волохов

17-20 июля 2020 года прошёл очередной ICFPContest, в котором наша команда WinterMUTE снова приняла участие.

См. наши отчёты о предшествующих ICFPContest 2019 и ICFPContest 2018.

Задача

В этот раз легенда была чумовой: за пару недель до начала соревнований сотрудники Pegovka Observatory начали публиковать необычные сигналы, полученные из космоса, и призвали сообщество помочь их расшифровать. С помощью crowd-sourcing выяснилось, что нам прислали описание простого, но полноценного функционального языка. Наконец, было получено и опубликовано большое сообщение #42 под названием Galaxy.

Одной из первых задач для участников было написание интерпретатора языка для запуска Galaxy. Всё остальное дальше по порядку.

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

Команда

В этом году из-за злосчастного COVID-19 все взаимодействовали удалённо. Команда была распределённой, но в рамках всего нескольких часовых поясов.

Изначально планировалось участие 8 человек, но перед самым началом соревнований двое выбыли по личным обстоятельствам, один решил организовать свою команду на Python, а ещё один участник присоединился, впрочем, только на нулевой день. В итоге состав был следующим:

• Александр Савин (EPAM)
• Антон Волохов (Apple)
• Алексей Ростовский (JetBrains) -- нулевой и первый день
• Вадим Цесько (Одноклассники)
• Дмитрий Коренев -- нулевой день
• Олег Шпынов (JetBrains Research)

Впрочем, один из наших участников прошлых лет, возможно, оставил нам пасхалку в названии другой команды :)

Решение

Перед соревнованием мы устроили внутреннее голосование и в очередной раз выяснили, что наибольшим общим знаменателем для большинства участников остаётся Java, а на что-то более экзотическое типа Swift, Rust или даже Kotlin в этот раз мы не решились.

Day 0

Организаторы выложили ещё одну пачку полученных и пока не расшифрованных сообщений, составляющих спецификацию языка инопланетян, и предложили совместно разобраться с тем, что они значат, координируясь через общий чатик. Участники постепенно разбирались с новыми сообщениями и предлагали их описание в виде pull request. Как выяснилось, единственными операторами с побочными эффектами были рисование на canvas и взаимодействие со средой, включая отправку координат click.

Оказалось, что у Димы уже есть учебный интерпретатор похожего языка на Haskell и он решил адаптировать его для запуска интерпретации Galaxy. Вадим принимал теоретическое участие и раскуривал спеку. К сожалению, к вечеру Galaxy не заинтерпретировалась из-за недоприменённых функций, но с ходу баг найти не удалось.

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

К концу первого дня мы научились отправлять первоначальную последовательность от организаторов, но не раскололи, что она значит, и как интепретировать ответ от API.

Day 1

После неудачи с готовым интерпретатором на Haskell Вадим засел за реализацию интерпретатора на Java. Олег успешно распарсил все сырые сообщения, в т.ч. Galaxy, и самостоятельно занялся своим интерпретатором. Антон продолжал заниматься (де)модуляцией, а затем переключился на реализацию поддержки draw. Саша продолжил заниматься (де)модуляцией сложных структур и тестами для них, а затем подключился вместе с Антоном к реализации различных операторов нашего интерпретатора.

Day 2

Интерпретатор Олега успешно прожевал Galaxy. Вадим, Антон и Саша продолжали реализовывать, отлаживать и тестировать интерпретацию операторов языка, а также форсировали ленивость где только можно. Олег тем временем занялся визуализацией оператора draw.

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

Честно говоря, к этому моменту мы начали ощущать лёгкую депрессию, потому что совершенно не понимали, что от нас ожидается и как другие команды зарабатывают хоть какие-то очки. Из понятного была только спека и задачи по интерпретатору.

Олег ради эксперимента набросал "прокликивалку" по спирали и к концу дня мы увидели Galaxy!

Т.е. прокликивалка "нащупала" последовательность рабочих кликов в UI игры, на очередном цикле интерпретации Galaxy мы заметили, что всё стало "тормозить", а на выходе появились красочные картинки. Мы воодушевились и начали педалить с удвоенной силой.

Антон за половину грядущей ночи разобрался с API, наладил взаимодействие с ним и корректное подключение нашего решения к чемпионатам.

В этот момент стало понятно, что Galaxy сама по себе не нужна, и для участия в чемпионатах достаточно лишь уметь (де)кодировать представление мира и команд.

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

Day 3

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

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

Итоги

В этот раз по очкам мы были в хвосте, но главная цель получения фана всё-таки была достигнута. Лично я закрыл гештальт написания в сжатые сроки и отладки ленивого интерпретатора функционального языка, способного перемолоть нетривиальную программу Galaxy. А визуальная часть добавила хорошую порцию фана.

Выводы

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

К сожалению, задание предполагало довольно интенсивный темп до получения хоть какого-то фидбека. В пользу этого говорит хотя бы то, что всего 5 команд в lightning round (к концу первых суток) прошли tutorial #1 -- что это был за tutorial и как в нём поучаствовать, мы так и не поняли.

История с реализацией всех возможностей языка и интерпретацией Galaxy красива сама по себе, но не имела практической ценности для боёв во второй части контеста, на основе которых и строился leader board -- там достаточно было освоить небольшое подмножество языка, чтобы научиться взаимодействовать с игровым API. С другой стороны, Galaxy позволяла отреверсинжинирить всё раньше других команд и продвинуться дальше, что, впрочем, у нас не получилось.

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

Как обычно, у нас возникало дублирование функциональности, но тем не менее, все много взаимодействовали и неизбежный фан был получен :)

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

В целом, очень хорошо показал себя Google Meet -- мы сидели в нём non-stop все трое суток практически без единого разрыва. Да и сам онлайн формат получился гораздо лучше, чем я лично ожидал.

В текущем контесте возникло ясное осознание, что мы могли бы утилизировать существенно больше человеческих ресурсов (особенно в отдалённых часовых поясах), например, разделившись сразу на разбирательство с API параллельно с проработкой Galaxy.

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

Исходники нашего решения лежат здесь.

comments powered by Disqus