В этот раз мы писали программы для какого-то фантастического
3D-принтера, в котором печать производят летающие наноботы. Боты имеют
какую-то систему команд, могут перемещаться по полю и превращать материю
в энергию и обратно. Кроме того, присутствует некое
"подпространственное поле", за счёт которого напечатанные куски модели
могут висеть в воздухе, пока поле включено. Боты могут размножаться
делением и потом опять соединяться. Каждая команда ботам стоит
сколько-то энергии, и включение "антигравитации" тоже сколько-то стоит.
Дан набор моделей, которые надо напечатать, надо написать
соответствующие программы для ботов, тратящие как можно меньше энергии.
Задачи для ICFPC придумывают вроде бы люди из университетов, но при этом, похоже, эти люди имеют какой-то опыт промышленной разработки, так что процесс решения задач похож на "настоящее" программирование гораздо больше, чем, например, те же ACP ICPC. Начать с того, что сам процесс получения входных данных и формирования выходных каждый раз представляет собой целую небольшую задачу - то по REST надо разговаривать, то длинные рациональные числа парсить. В этот раз протокол был полностью бинарным: в командах координаты кодировались даже не байтами, а отдельными битами. Модели тоже были закодированы не совсем тривиально: по одному биту на воксель. Вероятно, как раз бинарный протокол стал причиной того, что в этот раз в контесте принимало участие гораздо меньше команд, чем в прошлые разы (всего 95 команд; в прошлом году, для сравнения, мы были 102-ми из 120).
Другой момент, делающий ICFPC похожим на "реальную жизнь" - не ограниченный размер команды. При ограниченном сроке (трое суток), очевидно, организовать эффективную работу большой команды над сложной задачей - целая большая управленческая проблема. Если у вас есть где-то чудо-ПМ, вы, теоретически, можете взять команду из 100 условных индусов и всех победить. Или вы можете взять двух-трёх хороших разработчиков без всякого ПМ-а и тоже всех победить. То есть, как и в реальных задачах, это соревнование не только по программированию, но и по управлению проектами.
И ещё один момент: условия задачи меняются и усложняются прямо во время разработки. Как знакомо. В этот раз, правда, усложнение было всего одно, зато какое... Так часто бывает на ICFPC: когда впервые читаешь задачу, появляется ощущение, что эту задачу решить нельзя никак, никакими силами и ни за какое время. Потом ты начинаешь что-то пилить, разбираться, у тебя начинает что-то получаться... А потом приходит усложнение задачи раз в пять.
Писали в этот раз опять на Haskell.
А для того, чтобы выдать хоть какой-то самый тривиальный алгоритм, надо написать некоторое количество обвязки: разбор файлов итд. Поэтому я нагуглил пакет bits и стал реализовывать кодирование команд ботам в заданный бинарный протокол. В чате в это время обсуждали общие подходы и усолвие задачи. А потом я пошёл спать.
Потом я взялся писать "простой алгоритм", который включает антигравитацию и начинает печатать модель слой за слоем одним ботом. При этом мне приходилось по дороге допиливать обвязку.
Изначально у меня была мысль, что будет две отдельных сущности: Generator - набор API для формирования последовательности команд, и какой-нибудь Emulator - реализация описанной в спецификации модели, с подсчётом энергии, учётом закрашенных вокселей и т.д. И потом мы бы как-нибудь с использованием генератора создавали какие-нибудь программы, и сравнивали их при помощи эмулятора. Но потом постепенно как-то так получилось, что для написания хоть сколько-то полезных алгоритмов генератору на каждом шаге нужно (по крайней мере частично) знать состояние мира, в которое приводит сгенерированная последовательность команд. А эмулятор у нас так и не родился...
К вечеру самый простой алгоритм был готов, и мы даже надеялись что-то выдать в раммках lightning division, но не успели.
Потом я стал оптимизировать исходный тупой алгоритм. Идея была в том, чтобы выключать "антигравитацию", когда она не нужна. Только вот для этого в момент построения программы надо понимать, какие из закрашенных на данный момент вокселей "заземлены" (т.е. опираются на что-нибудь), а какие "висят в воздухе". Пришлось добавлять отслеживание этого в генератор, да и после мы с этой частью логики ещё долго возились.
Уже почти ночью мы всё-таки напоролись на "мифические" проблмы с производительностью из-за иммутабельности и ленивости (мифические, потому что по моему опыту на них наталкиваешься довольно редко). Решили кардинально, избавившись в этих местах и от ленивости, и от иммутабельности.
Ещё мы успели что-то залить, и оказались аж на 12м месте в лидерборде. Ну, просто потому, что только 15 команд к данному моменту успели хоть что-то выдать.
Для возможности хоть как-то сравнивать разные решения задач я написал простой Evaluator, который оценивает количество энергии, потребляемое программой. При этом этот evaluator не отслеживает состояние модели, не отслеживает положение ботов, не выполняет никаких проверок...
Полноценного эмулятора у нас так и не было, поэтому оценить, насколько правильно решаются все задачи, мы не могли - только глазами проверить некоторые выборочно. Поэтому перед сном мы залили версию, которая на некоторых задачах нам дала существенный прирост, зато на всех остальных - нули, т.к. в программах были ошибки. Но узнали об этом мы только в понедельник, т.к. лидерборд обновлялся редко.
С утра, увидев что мы сползли на 67е место из 78, я стал разбираться с ошибками, и к обеду залил исправленную версию.
Minoru начал писать скрипт, который бы с использованием evaluator выбрал лучший вариант решения для каждой задачи, из тех что мы отправляли за весь контест.
С какими-то ещё небольшими оптимизациями, мы поднялись на 48е место из 95. Не очень плохо, но бывало лучше...
А вскоре после обеда, лайвборд заморозили, и до вечера мы что-то ещё понемногу оптимизировали уже "вслепую": эмулятора-то не было, и мы до сих пор не знаем, чего в этих сабмишшенах было больше: оптимизаций или ошибок, и куда мы в итоге попадём. Примерно с равной вероятностью мы можем оказаться на 20м и на 80м месте.
Задачи для 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, или визуализатор), то её очевидно нужно писать, а не "да ладно, давайте как-нибудь так".
- Вся команда должна хорошо владеть используемым языком и его библиотеками. У нас же чрезвычайно разношёрстная команда: когда мы после контеста решили выяснить пересечение множеств умеемых каждым из нас языков, оказалось, что это пересечение пусто.
