После ICFPC
(После ICFPC. Флорис ван Дейк. Холст, масло.)
Для тех, кто ещё не знает, ICFPC - это турнир по программированию, проводимый до конференции ICFP, пожалуй, самой главной конференцией по функциональному программированию. Участвовать в турнире могут команды из произвольного количества людей, нужно решить заданную организаторами задачу за 72 часа. Определяется лучшее решение, созданное в первые сутки (lightning-зачёт), и тройка лучших решений, подготовленных за все трое суток (общий зачёт). Язык програмимирования, используемый лучшим решением, на конференции ICFP объявляют "лучшим языком программирования для выдающихся хакеров", второго решения - "хорошим средством программирования для многих приложений". Язык победителя lightning-зачёта объявляют "весьма подходящим для быстрого прототипирования".
Поскольку я люблю и практикую функциональное программирование, я участвую в ICFPC с 2008 года (с 2011 - без пропусков). В этом году я подготовился к турниру: отправил жену на дачу день рождения nadiyshenka (с прошедшим днём рождения!), накупил лимонада и приготовил бутербродов. В этом году получилось так, что смогли участвовать только трое из нашей команды, поэтому пришлось писать много.
Задача заключалась в следующем.
Есть сеть рек между точками, по которой двигаются лодочники и перевозят лямбды. Лямбды добывают в выделенных точках - шахтах. Лодочники поочередно делают ходы: либо пропускают ход, либо захватывают какую-либо реку (и тогда по ней больше никто не может проехать). Через определённое количество ходов игра заканчивается. Лодочник получает количество очков, равное сумме по всем шахтам сумм по всем достижимым точкам квадратов минимального расстояния (по любым рекам) от шахты до достижимой (по рекам, захваченным лодочников) точки. Нужно написать программу для лодочника.
Через некоторое время в lightning-зачёте добавили фьючерсы - в начале игры можно выставить ставки, что лодочник захватит путь от указанной шахты до указанной точки. Если он захватывает путь, он выигрывает куб минимального расстояния между этими шахтой и точкой; если нет - проигрывает столько же.
В основное время добавили ещё splurges (пускание пыли в глаза?) - возможность захватить одним ходом несколько рек, если до этого лодочник пропускал ходы и опционы - возможность захватить реку *двум* лодочникам.
Мы решали её так (как оказалось, ничего принципиально нового мы не придумали до конца турнира). Сеть рек - это граф с вершинами в точках и ребрами-реками. На каждом ходу удаляем все рёбра, захваченные до этого другими лодочниками. Ищем кратчайшие пути от всех шахт до всех точек. Берём самый длинный из них и захватываем первое ребро в этом пути (и устанавливаем его длину в нуль). В итоговом решении мы пытались строить деревья Вороного, минимальные остовные деревья, оценивать каждый путь, но суть оставалась той же.
Сейчас организаторы оценивают решения: заставляют играть вместе различные решения, и суммируют очки (за победу - 3, за второе место - 2 и т.д.). После этого выбывает нижняя половина участников и процесс повторяется на бóльших картах. После первого раунда выбывания мы (NCPLUG) на 9-11 месте в lightning-зачёте (это лучший наш результат в любом зачёте за всё время участия в ICFPC). А здесь можно посмотреть ход каждой игры. К сожалению, на больших картах наше решение тормозит, и мы, скорее всего, дальше вылетим. А в общем зачёте нас, скорее всего, обгонят команды, которые успели придумать более умные решения. Такие дела.
Мысли по итогам:
- строгая типизация и АТД рулят! по крайней мере, для протокола общения с сервером
- полезно писать вспомогательные программы, например, визуализатор помог нам в отладке
- имеет смысл готовить разные решения для разных видов входных данных
- библиотека fgl вполне рабочая
- нужно больше^Wменьше колы эффективнее писать код
А как вы проводите лето?
Backup of this entry can be found here: http://gltronred.dreamwidth.org/5666.html.