Задачи для ICFPC придумывают вроде бы люди из университетов, но при этом, похоже, эти люди имеют какой-то опыт промышленной разработки, так что процесс решения задач похож на "настоящее" программирование гораздо больше, чем, например, те же ACP ICPC. Начать с того, что сам процесс получения входных данных и формирования выходных каждый раз представляет собой целую небольшую задачу - то по REST надо разговаривать, то длинные рациональные числа парсить. В этот раз протокол был полностью бинарным: в командах координаты кодировались даже не байтами, а отдельными битами. Модели тоже были закодированы не совсем тривиально: по одному биту на воксель. Вероятно, как раз бинарный протокол стал причиной того, что в этот раз в контесте принимало участие гораздо меньше команд, чем в прошлые разы (всего 95 команд; в прошлом году, для сравнения, мы были 102-ми из 120).
Другой момент, делающий ICFPC похожим на "реальную жизнь" - не ограниченный размер команды. При ограниченном сроке (трое суток), очевидно, организовать эффективную работу большой команды над сложной задачей - целая большая управленческая проблема. Если у вас есть где-то чудо-ПМ, вы, теоретически, можете взять команду из 100 условных индусов и всех победить. Или вы можете взять двух-трёх хороших разработчиков без всякого ПМ-а и тоже всех победить. То есть, как и в реальных задачах, это соревнование не только по программированию, но и по управлению проектами.
И ещё один момент: условия задачи меняются и усложняются прямо во время разработки. Как знакомо. В этот раз, правда, усложнение было всего одно, зато какое... Так часто бывает на ICFPC: когда впервые читаешь задачу, появляется ощущение, что эту задачу решить нельзя никак, никакими силами и ни за какое время. Потом ты начинаешь что-то пилить, разбираться, у тебя начинает что-то получаться... А потом приходит усложнение задачи раз в пять.
Писали в этот раз опять на Haskell.
Пятница
Эту часть контеста Minoru охарактеризовал так:С прошлых лет у меня так и осталось ощущение, что очень важно побыстрее выдать хоть что-то. Не для того, чтобы набрать очки (правила подсчёта очков в ICFPC обычно такие, что одним только кодингом на скорость ничего не добьёшься). А для того, чтобы у команды появилось ощущение "ну, что-то вроде можем, может быть эту задачу даже можно решить". Пока такого ощущения не появится, все находятся в некоторой фрустрации: "руки опускаются". А это просто потеря времени.1. Никто ничо не понял, но Портнов уже пилит базовые типы и тулинг.
А для того, чтобы выдать хоть какой-то самый тривиальный алгоритм, надо написать некоторое количество обвязки: разбор файлов итд. Поэтому я нагуглил пакет bits и стал реализовывать кодирование команд ботам в заданный бинарный протокол. В чате в это время обсуждали общие подходы и усолвие задачи. А потом я пошёл спать.
Суббота
Краткое содержание от Minoru:На самом деле, я ещё продолжал пилить обвязку. Дело в том, что в данной задаче, когда ботов больше одного, команды для разных ботов должны идти вперемешку. Точнее, исполнитель на каждом шаге смотрит, сколько сейчас живых ботов, читает из программы N команд и раздаёт их ботам. С учётом того, что алгоритм должен выдавать команды ботам согласованно, целую небольшую задачку составляет формирование общей программы из программ для отдельных ботов, с учётом их переменного количества. А ещё я сделал чтение файлов моделей при помощи библиотеки bitwise.2. Появились какие-то базовые идеи, народ осваивает запиленный Портновым тулинг. 3. Идеи рождаются быстрее, чем пишется код, это всё выпрыскивается в чат (в этом году ещё и в трекер).
Потом я взялся писать "простой алгоритм", который включает антигравитацию и начинает печатать модель слой за слоем одним ботом. При этом мне приходилось по дороге допиливать обвязку.
Изначально у меня была мысль, что будет две отдельных сущности: Generator - набор API для формирования последовательности команд, и какой-нибудь Emulator - реализация описанной в спецификации модели, с подсчётом энергии, учётом закрашенных вокселей и т.д. И потом мы бы как-нибудь с использованием генератора создавали какие-нибудь программы, и сравнивали их при помощи эмулятора. Но потом постепенно как-то так получилось, что для написания хоть сколько-то полезных алгоритмов генератору на каждом шаге нужно (по крайней мере частично) знать состояние мира, в которое приводит сгенерированная последовательность команд. А эмулятор у нас так и не родился...
К вечеру самый простой алгоритм был готов, и мы даже надеялись что-то выдать в раммках lightning division, но не успели.
Потом я стал оптимизировать исходный тупой алгоритм. Идея была в том, чтобы выключать "антигравитацию", когда она не нужна. Только вот для этого в момент построения программы надо понимать, какие из закрашенных на данный момент вокселей "заземлены" (т.е. опираются на что-нибудь), а какие "висят в воздухе". Пришлось добавлять отслеживание этого в генератор, да и после мы с этой частью логики ещё долго возились.
Теперь:4. Выходит апдейт условий, все получают скачок адреналина, возможен регресс до второй фазы с целью перепилить тулинг. (Эта фаза может наступать несколько раз в зависимости от апдейта).
- можно не только превращать энергию в материю, но и наоборот
- несколько ботов могут взаимодействовать и закрашивать за один ход большие области: линию, прямоугольник или параллелипипед из вокселей.
- появились новые задачи, в которых надо не собрать модель, а разобрать
- появились ещё задачи, в которых надо разобрать одну модель и собрать другую.
Уже почти ночью мы всё-таки напоролись на "мифические" проблмы с производительностью из-за иммутабельности и ленивости (мифические, потому что по моему опыту на них наталкиваешься довольно редко). Решили кардинально, избавившись в этих местах и от ленивости, и от иммутабельности.
Ещё мы успели что-то залить, и оказались аж на 12м месте в лидерборде. Ну, просто потому, что только 15 команд к данному моменту успели хоть что-то выдать.
Воскресенье
Никакого особо умного алгоритма мы так и не придумали, поэтому продолжали оптимизировать тупой. В частности, я научился пользоваться двумя ботами и закрашивать весь слой серией команд "закрасить линию", в тех случаях, когда это достаточно просто, а именно - когда слой состоит из серии достаточно коротких линий. И ещё при закрашивании каждого следующего слоя научился менять направление, чтобы ботами туда-сюда меньше впустую ездить.Для возможности хоть как-то сравнивать разные решения задач я написал простой Evaluator, который оценивает количество энергии, потребляемое программой. При этом этот evaluator не отслеживает состояние модели, не отслеживает положение ботов, не выполняет никаких проверок...
Полноценного эмулятора у нас так и не было, поэтому оценить, насколько правильно решаются все задачи, мы не могли - только глазами проверить некоторые выборочно. Поэтому перед сном мы залили версию, которая на некоторых задачах нам дала существенный прирост, зато на всех остальных - нули, т.к. в программах были ошибки. Но узнали об этом мы только в понедельник, т.к. лидерборд обновлялся редко.
Понедельник
В понедельник остались только мы с Minoru. Товарищи Akon32 и ForNeVer оставили нам по длинному описанию начатых, но не законченных идей в трекере.С утра, увидев что мы сползли на 67е место из 78, я стал разбираться с ошибками, и к обеду залил исправленную версию.
Minoru начал писать скрипт, который бы с использованием evaluator выбрал лучший вариант решения для каждой задачи, из тех что мы отправляли за весь контест.
С какими-то ещё небольшими оптимизациями, мы поднялись на 48е место из 95. Не очень плохо, но бывало лучше...
А вскоре после обеда, лайвборд заморозили, и до вечера мы что-то ещё понемногу оптимизировали уже "вслепую": эмулятора-то не было, и мы до сих пор не знаем, чего в этих сабмишшенах было больше: оптимизаций или ошибок, и куда мы в итоге попадём. Примерно с равной вероятностью мы можем оказаться на 20м и на 80м месте.
5. В смысле конец контеста, у меня же ещё вот это, это и это не реализовано!
В общем
Некоторое количество замечаний в духе Капитана Очевидность:- Надо лучше организовывать общение в команде. В частности, лучше документировать код, наверное. А то я несколько раз объянял товарищам, как работает мой Generator. И пару раз выяснялось, что два человека параллельно делают одно и то же.
- Не надо экономить на инфраструктуре. Если понятно, что вот это можно вынести в утилитную функцию, вот здесь для ясности ввести type synonym, то это надо делать, хотя это занимает время. При работе в одиночку, или даже в команде в том случае, когда ты один пишешь большой кусок кода, иногда имеет смысл на первом этапе сэконоить: написать побыстрее некоторое количество тупого кода, с копипастой и прочим, убедиться в его работоспособности, а потом отрефакторить и убрать копипасту. В случае тесной командной работы так делать не надо: инфраструктурный код должен сразу иметь простое, "красивое" api.
- Если какая-нибудь часть инфраструктурного кода очевидно нужна (например, эмулятор, или pathfinding, или визуализатор), то её очевидно нужно писать, а не "да ладно, давайте как-нибудь так".
- Вся команда должна хорошо владеть используемым языком и его библиотеками. У нас же чрезвычайно разношёрстная команда: когда мы после контеста решили выяснить пересечение множеств умеемых каждым из нас языков, оказалось, что это пересечение пусто.