Изначально это должен был быть отчёт победителя или хотя бы призёра соревнования. Участвовать в соревнованиях по программированию очень интересно и вдохновляюще, но победить никак не удавалось. Год назад я занял 14-е место, пол года назад удалось продвинуться до 6-го. Тематика и формат текущего кубка, казалось, позволят мне наконец одержать победу, но что‑то пошло не так.
Хоть я и пробрался в финал, но не смог попасть даже в двадцатку. Впрочем, товарищи убедили меня, что подобная статья всё равно может быть интересна многим ребятам, а может быть даже откроет для кого-то новый интересный аспект жизни айтишника. Итак, приступим.
Ещё пару лет назад при упоминании о соревновании по программированию я представлял себе решение алгоритмических задач на время. Собственно, такие соревнования и сейчас вполне распространены. Конечно, организаторы пытаются уже хотя бы формулировать задачи не очень оторвано от реальности, но это всё ещё «на входе X чисел от 0 до N, где 0 < X < 10000, а на выходе Y чисел от 1 до M ». Я не имею ничего против любителей математики и алгоритмов, но стоит признать, что сейчас большинство айтишников уже не гики с красными глазами, а обычные ребята, интересующиеся множеством разных тем и не желающие тратить время на такую банальщину.
Впрочем, есть примеры и других соревнований. Когда состязание происходит в игровой форме. Примером может служить Russion AI Cup, статья о котором уже была на Хабре. Примерно в такой же игровой форме проходило и данное состязание.
Как понятно из названия, игровым полем служило море размером 1000 на 1000, в случайных местах которого появлялись острова. Маяков на этих островах не было, но зато на них маячила прибыль. Не в виде кладов конечно, деньги можно было заработать, покупая на одном острове подешевле и продавая на другом подороже один из пяти видов товаров. Таким образом, передо мной предстала экономическая стратегия с довольно простыми правилами. Нужно было купить товар, загрузить на один из своих кораблей, перевезти на остров, где для него есть покупатель, затем продать его и разгрузить. В в каждом из матчей отборочного раунда участвовало 4 игрока, победа же доставалась тому, кто больше заработает.
Засучив рукава я принялся за кодинг уже на этапе бета-тестирования. Ведь каждому известно: «Кто рано встаёт, тому Посейдон благоволит». Описание правил игрового мира привело меня к естественной мысли - нужно решать задачу с помощью конечного автомата (State Machine). Я набросал список статусов и принялся за реализацию, ведь море волнуется без меня, и волнуется не зря - конкуренты уже пишут более крутые стратегии.
Пока вроде всё звучит неплохо, но самая большая засада была в том, что код писать нужно было на PL/pgSQL, с которым я был довольно слабо знаком. Да, базовые запросы SQL знает любой разработчик, но также каждый знает, что описывать бизнес-логику в базе данных - очень плохая практика. Собственно на большинстве своих проектов я по полной использовал Hibernate и уж конечно не использовал процедуры и функции. Я представлял, что примерно так же и у большинства других разработчиков, но просчитался. Соперники оказались с морскими звездами на погонах. Ребята в чате хвастали, как составляли запросы из нескольких сот строк и процедуры из нескольких тысяч запросов. Впору было впадать в уныние.
Впрочем, организаторы сразу предупредили, что моря в их задаче покоряются только смелым. Я взял себя в руки и принялся активно изучать незнакомую область. Ведь кроме спортивного интереса я имел и прагматичные цели, я поставил себе в качестве одной из задач на развитие углубленное изучение SQL. Весь день я обдумывал, как бы лучше реализовать конечный автомат в базе данных. Наконец, там где в море уже начала тонуть печаль, забрезжил компас земной в виде триггеров. Что в общем-то логично, какой же может быть конечный автомат без триггеров?
Изначальной идеей было просто по триггерам на события создавать все команды, но оказалось, что каждый игрок работает в своей копии базы, которая каждую команду think() синхронизируется с главной базой и какие-либо команды можно отдавать только во время действия этой процедуры. Так родилась дополнительная таблица вот такого вида:
CREATE SCHEMA IF NOT EXISTS custom;
CREATE TABLE IF NOT EXISTS custom.tasks
(
id integer,
status varchar,
ship integer,
start_island integer,
end_island integer,
item integer,
offer integer,
count_goods double precision
);
CREATE SEQUENCE tasks_id_seq START 1;По триггеру менялись статусы, а уже исходя из статуса каждому кораблю задавалась следующая команда. Отладив код на локальном эмуляторе, предоставленном разработчиками, я закинул решение на сайт и отметил готовым для битвы. И внезапно ушёл в минус. Мой корабль следовал модному течению, но оказалось, что оно поворачивало не туда, куда надо.
Приплыв на необитаемый остров, экипаж корабля сломал всю его концепцию. А необитаемый остров в свою очередь, сломал мою стратегию. Я совершенно не учёл, что на островах может не быть продавцов или подходящих покупателей какого-либо товара.
Время близилось к утру и волевым решением я повелел капитанам кораблей плыть на все четыре стороны, а если быть точнее, то начал отправлять их с пустого острова на любой другой случайный остров. С чистой совестью я лёг спать, ведь моё второе решение наконец-то начало приносить доход. Тем не менее впереди меня было уже больше 30 участников и уверенность начала меня покидать. Распив бутылочку рома, я решил остаться на дне турнирной таблицы и забросить этот конкурс.
Из ступора меня вывел внезапный баг-репорт от одного из участников. Оказывается, на некоторых островах были сразу и покупатели и продавцы для одного и того же товара. А ещё, можно было покупать отрицательное количество товара. Пока я учился плавать на кораблях, довольно большое количество участников нашли в реализации кротовью нору и спокойно таскали золото. Как только баг пофиксили, я просмотрел битвы игроков и убедился, что лишь около больше дюжины участников написали стратегию, не опирающуюся на этот баг.
Подробнее изучив правила, я понял, что покупка и продажа товара не требовали наличия корабля в порту, где находится контрагент и немного изменил последовательность смены состояний корабля. Теперь я покупал товар, затем продавал его, а затем уже загружался, плыл на остров назначения и разгружался там. Это позволило мне ещё чуток подняться по таблице, однако теперь я начал сталкиваться с вопиющим разгильдяйством моих капитанов. Внезапно оказалось, что они начали перехватывать контракты друг у друга. Что в общем-то было ожидаемо. Товаров всего 5, я всегда пытаюсь продать товар покупателю с самой большой ценой и если оба корабля закупили дерево, то они попытаются продать его одному и тому же человеку. Только вот внезапно оказалось, что заключать два договора на продажу с одним и тем же контрагентом нельзя.
Я пытался воззвать к совести организаторов, но всё было тщетно. Пришлось добавлять это ограничение в код. Тем временем прошла уже неделя. Бета-тест закончился и начался основной раунд. Неожиданно для меня, увеличилось количество кораблей, количество островов и контрагентов, но уменьшилось количество товара, доступного к покупке или продажи каждым из торговцев. Эти сухопутные крысы производили и потребляли слишком мало товара, моей торговой империи было просто негде развернуться в этом скромном мирке из пятидесяти островов.
В этом новом игровом мире, мои корабли постоянно заплывали на необитаемые острова и конкурировали между собой за ресурсы. И я решил полностью выбросить текущий код и переписать стратегию с нуля.
Я разделил на два процесса заключение сделки и доставку товара. Теперь у меня были две таблицы и много процедур, вызывающих друг друга.
CREATE TABLE IF NOT EXISTS custom.contracts
(
id integer,
status varchar,
start_island integer,
end_island integer,
item integer,
offer_buy integer,
buy_flag bool,
offer_sell integer,
sell_flag bool,
quantity double precision
);
CREATE TABLE IF NOT EXISTS custom.tasks
(
id integer,
status varchar,
ship integer,
contract_id integer
);
CREATE SEQUENCE contracts_id_seq START 1;
CREATE SEQUENCE tasks_id_seq START 1;Я подошёл к делу с умом и даже нарисовал примерную схему моей новой стратегии.
К сожалению, новая стратегия принесла с собой много новых багов. Некоторые из которых выявлялись лишь на определённой конфигурации мира, которая каждый раз была случайной. Простая казалось бы задача обросла кучей нюансов. Мне так и не удалось отловить все баги и заставить стратегию работать как надо. Некоторые моменты, сделанные в самом начале на скорую руку, с надеждой на дальнейшую доработку, так и остались недоделанными. Вот уж закончился отпуск, а каменный цветок всё никак не выходил из под моих клавиш. Я безусловно попал в финал, куда отбирались лучшие 50 игроков, но рассчитывать на высокое место не приходилось.
После завершения всех сражений, многие игроки стали делиться кодом и я внезапно понял, что секрет победы вовсе не в последовательности действий. Первые места заняли те, кто выполнял максимум возможных действий за одно выполнение процедуры think(). Некоторые из этих решений оказались компактней моего. Данное соревнование дало мне ценный опыт, который я никогда не получил бы, решая алгоритмы на время. Более того, это опыт универсальный, подходящий под многие жизненные ситуации.
Вот какие выводы я сделал.
Как бы ни была красива стратегия, строиться она должна не на основе предположений, а на основе конкретных данных. Необходимо уметь находить узкое место и оптимизировать свои действия именно там.
Никогда не стоит отчаиваться и падать духом, возможно совсем рядом находится грааль, который позволит вам одержать победу.
SQL очень неудобен для отладки и тестирования. Выводить бизнес-логику в базу данных - плохая идея. Людей, которым приходится писать хранимые процедуры по несколько тысяч строк мне искренне жаль.
Турниры по программированию в игровой форме гораздо интереснее любых других соревнований и следующий раз я снова буду участвовать. Возможно однажды мне удастся написать отчёт победителя.
P.S.: Выложил код некоторых этапов на Github
