CodinGame: конкурс A*Craft завершился
Сегодня закончился конкурс A*Craft на CodinGame. В отличие от предыдущих, он длился всего два с половиной дня и был не на игры, а на оптимизацию: нужно было расставить стрелки на карте так, чтобы сделать суммарный путь роботов по ней максимальным. Я занял 150-ое место из 2456! (Правда, примерно последние 500 участников — те, кто зарегистрировался, но даже не попытался прислать хоть какой-то код, и поэтому получившие 0 очков.) Это гораздо лучший показатель, чем во всех предыдущих конкурсах. Если считать в относительных показателях, то до этого мне максимум удавалось подняться до 84%, а в этот раз — до 93%, что близко к моему верхнему порогу амбициозности!
И это несмотря на то, что толком на конкурс не настроился, и до воскресенья подходил к нему как-то лениво. Впрочем, задачи по оптимизации даются мне проще сами по себе. Кроме того, код был основан примерно на том же рекурсивном алгоритме, который я впервые пытался применить еще в Code of Ctulu. Написал я его достаточно быстро, но потом обнаружился какой-то совершенно непонятный баг, на борьбу с которым ушла половина воскресенья. А причина оказалась банальной: я дважды использовал одно и то же имя result в одной функции, но подразумевая при этом две совершенно разных переменных: одну для поиска максимума, вторую — для хранения значения, которое будет возвращено из функции. В результате вместо максимума возвращался последний результат.
Из-за этого я только вечером воскресенья обнаружил, что хотя алгоритм хорошо справляется с картами из узких длинных коридоров, но дает довольно посредственные результаты на картах с большими смежными областями. Для таких карт я задумал было еще один алгоритм с совершенно другим подходом, но так его и не реализовал. Во-первых, не хватало времени, чтобы тщательно его обдумать и вытащить из зоны неуверенности. Во-вторых, нашел один случай, когда первый алгоритм (который рекурсивный) давал неоптимальный результат. Сначала казалось, что ошибка простая и ее удастся устранить быстро. Но все оказалось не так: я провозился с ней до глубокой ночи. А потом выяснилось, что ошибка действительно примитивная: я забываю вызвать .copy() при рекурсивном вызове функции, в результате чего вместо копии карты для поиска на следующем шаге передается ее исходный вариант и результаты поиска пути в разных направлениях начинают влиять друг на друга. Странно, что на остальных картах это работало! Причем выяснилось, что если на каждом шаге создавать копию карты, это занимает много времени, и в итоге на многих тестах начинается вылет по таймауту. Пришлось применить «костыльное» решение: написать условие, по которому принимается решение, делать копию или нет.
Поэтому вместо второго алгоритма сделал простую проверку: если карта с большими смежными областями, и роботов много, то для последних строить путь только до ближайшей уже размещенной стрелки. И, как это ни странно, это дало определенный результат: вместо 5400 очков, которые я набирал изначально, стало получаться 5700! А вот исправление того бага с копией дало всего лишь жалких 17 очков (впрочем, их оказалось достаточно, чтобы подняться еще на несколько мест).
Но вообще, наверное, надо было писать не на Python, а на PHP. Там и код быстрее выполняется (если в PHP 7), и копии массивов создаются автоматически (так что я бы не возился полдня с первым багом и, может быть, успел бы и второй алгоритм реализовать), причем в режиме copy-on-write, что тоже дало бы неплохую оптимизацию. Но увы, нельзя применять в качестве ключей для хеша связки из нескольких значений (то, что в Python называется tuples). Впрочем, при желании это можно было бы легко обойти.
Но в любом случае, я доволен результатом!
И это несмотря на то, что толком на конкурс не настроился, и до воскресенья подходил к нему как-то лениво. Впрочем, задачи по оптимизации даются мне проще сами по себе. Кроме того, код был основан примерно на том же рекурсивном алгоритме, который я впервые пытался применить еще в Code of Ctulu. Написал я его достаточно быстро, но потом обнаружился какой-то совершенно непонятный баг, на борьбу с которым ушла половина воскресенья. А причина оказалась банальной: я дважды использовал одно и то же имя result в одной функции, но подразумевая при этом две совершенно разных переменных: одну для поиска максимума, вторую — для хранения значения, которое будет возвращено из функции. В результате вместо максимума возвращался последний результат.
Из-за этого я только вечером воскресенья обнаружил, что хотя алгоритм хорошо справляется с картами из узких длинных коридоров, но дает довольно посредственные результаты на картах с большими смежными областями. Для таких карт я задумал было еще один алгоритм с совершенно другим подходом, но так его и не реализовал. Во-первых, не хватало времени, чтобы тщательно его обдумать и вытащить из зоны неуверенности. Во-вторых, нашел один случай, когда первый алгоритм (который рекурсивный) давал неоптимальный результат. Сначала казалось, что ошибка простая и ее удастся устранить быстро. Но все оказалось не так: я провозился с ней до глубокой ночи. А потом выяснилось, что ошибка действительно примитивная: я забываю вызвать .copy() при рекурсивном вызове функции, в результате чего вместо копии карты для поиска на следующем шаге передается ее исходный вариант и результаты поиска пути в разных направлениях начинают влиять друг на друга. Странно, что на остальных картах это работало! Причем выяснилось, что если на каждом шаге создавать копию карты, это занимает много времени, и в итоге на многих тестах начинается вылет по таймауту. Пришлось применить «костыльное» решение: написать условие, по которому принимается решение, делать копию или нет.
Поэтому вместо второго алгоритма сделал простую проверку: если карта с большими смежными областями, и роботов много, то для последних строить путь только до ближайшей уже размещенной стрелки. И, как это ни странно, это дало определенный результат: вместо 5400 очков, которые я набирал изначально, стало получаться 5700! А вот исправление того бага с копией дало всего лишь жалких 17 очков (впрочем, их оказалось достаточно, чтобы подняться еще на несколько мест).
Но вообще, наверное, надо было писать не на Python, а на PHP. Там и код быстрее выполняется (если в PHP 7), и копии массивов создаются автоматически (так что я бы не возился полдня с первым багом и, может быть, успел бы и второй алгоритм реализовать), причем в режиме copy-on-write, что тоже дало бы неплохую оптимизацию. Но увы, нельзя применять в качестве ключей для хеша связки из нескольких значений (то, что в Python называется tuples). Впрочем, при желании это можно было бы легко обойти.
Но в любом случае, я доволен результатом!
