В этом году мы вернулись к схеме, которую попробовали два года назад: в течение дня участники пишут и отлаживают SQL-запрос, делающий ходы в какой-то игре; ночью проводится турнир между итоговыми запросами претендентов и по сумме набранных очков определяется победитель. В отличие от традиционного набора задач с «правильными решениями», в таком формате участники не могут упереться в потолок набранных баллов, а напряжение держится до последнего.
В позапрошлом году мы развлекались крестиками-ноликами, а сейчас выбрали гонки, в них, кстати, тоже можно играть в тетрадке в клетку.
Вот правила, которые мы раздали участникам.
Правила игры
На финальном этапе вам предстоит написать SQL-запрос, управляющий гоночным болидом.
Организаторы предоставляют веб-приложение, в котором необходимо регистрировать свои запросы. Приложение также может упростить отладку, позволяя пробовать и визуализировать произвольное количество вариантов. Один из вариантов, отмеченный вами как итоговый, будет участвовать в определении победителей: после окончания финала между итоговыми запросами всех участников будет проведено несколько турнирных заездов.
Краткое описание игры
Гонка проводится по трассе (возможно, с развилками), нарисованной на листке в клетку. Точки-машины начинают со стартовых позиций; побеждает тот, кто первым пересечёт финишную черту. Ходят по очереди: гонщик мысленно продолжает вектор предыдущего хода и выбирает любую из соседних точек. При этом траектория не должна пересекать границу трассы или касаться её.
Правила игры
Таблицы
Трасса представляет собой многоугольник, заданный набором границ (колец), которые образованы последовательностью точек. У многоугольника всегда есть внешняя граница и может быть несколько внутренних, «вырезающих» в них дырки.
CREATE TABLE racetrack( ring_id integer NOT NULL, -- номер границы, начиная с единицы point_id integer NOT NULL, -- номер точки границы, начиная с единицы x integer NOT NULL CHECK (x BETWEEN 0 AND 99), y integer NOT NULL CHECK (y BETWEEN 0 AND 99) );
Точки пронумерованы начиная с произвольного места границы, в порядке её обхода по часовой стрелке или против неё. Линия границы не имеет самопересечений; все точки границы различны. Границы не пересекаются и не касаются друг друга. Внутренние границы лежат строго внутри внешней.
Например, трасса, показанная на первой странице, может быть задана следующим образом:
INSERT INTO racetrack(ring_id, point_id, x, y) VALUES (1, 1, 2, 0), (1, 2, 2, 2), (1, 3, 1, 6), (1, 4, 1, 8), (1, 5, 2, 9), (1, 6, 4, 10), (1, 7, 8, 10), (1, 8, 11, 8), (1, 9, 11, 5), (1, 10, 9, 2), (1, 11, 9, 0), (1, 12, 6, 0), (1, 13, 6, 2), (1, 14, 7, 4), (1, 15, 4, 5), (1, 16, 5, 3), (1, 17, 5, 0); INSERT INTO racetrack(ring_id, point_id, x, y) VALUES (2, 1, 7, 8), (2, 2, 8, 7), (2, 3, 8, 6), (2, 4, 4, 7), (2, 5, 5, 8);
Финишные позиции расположены по вертикальной или горизонтальной линии на внешней границе многоугольника и заданы крайними точками отрезка:
CREATE TABLE finish( x1 integer NOT NULL CHECK (x1 BETWEEN 0 AND 99), y1 integer NOT NULL CHECK (y1 BETWEEN 0 AND 99), x2 integer NOT NULL CHECK (x2 BETWEEN 0 AND 99), y2 integer NOT NULL CHECK (y2 BETWEEN 0 AND 99), CHECK ( (x1 = x2 AND x1 IN (0, 99)) OR (y1 = y2 AND y1 IN (0, 99)) ) );
Доступны текущая и предыдущая позиции всех автомобилей, участвующих в гонке:
CREATE TABLE cars( num integer PRIMARY KEY, my boolean NOT NULL, x integer NOT NULL, y integer NOT NULL, x_prev integer NOT NULL, y_prev integer NOT NULL );
Ваш автомобиль отмечен флагом my. На старте текущая и предыдущая позиции автомобиля совпадают и находятся внутри трассы.
Перед каждым ходом таблица cars перезаписывается актуальной информацией; таблицы racetrack и finish остаются в том состоянии, в котором они были после вашего предыдущего хода.
Правила хода
Ходят по очереди. Ход состоит в перемещении машины из текущей позиции в следующую по прямой линии.
Чтобы определить позиции, на которые автомобиль может переместиться, надо от текущей позиции отложить вектор перемещения прошлого хода и выбрать любую из допустимых соседних точек (по горизонтали, вертикали или диагонали):
нельзя пересекать границу многоугольника трассы или касаться её (финишный отрезок исключается из проверки);
нельзя занимать место, где стоит другой автомобиль.
Автомобиль финиширует, если перемещается на одну из позиций финишного отрезка или пересекает финишный отрезок.
Требования к решению
Решение должно состоять из одного SQL-запроса, который возвращает две целочисленные координаты x и y позиции, на которую надо переместить автомобиль на следующем ходу. Названия столбцов игнорируются.
Суммарное время работы всех вызовов запроса ограничено 60 секундами. Отдельный вызов запроса не имеет дополнительных ограничений по времени.
Участнику заезда засчитывается технический проигрыш, если:
запрос вернул некорректные данные (должна быть ровно одна строка с двумя целыми числами);
автомобиль был перемещён в недопустимую позицию;
автомобиль не финишировал за отведённое время.
Настройки сервера
Проверка решений происходит на сервере с установленным PostgreSQL 18. Все настройки имеют значения по умолчанию, кроме параметра jit, который выключен.
Учитывайте, что время работы запроса не постоянно и зависит от многих факторов, а ваш ноутбук может отличаться от сервера по производительности как в одну, так и в другую сторону.
Правила проведения турнира
После завершения финального дня между запросами, отмеченными участниками как итоговые, будут проведены турнирные заезды.
За технический проигрыш участник получает ноль очков. Финишировавшие участники распределяются по местам: чем меньше ходов потребовалось совершить, тем выше место (участники с одинаковым количеством ходов разделяют одно место). Занявшие последнее место получают одно очко, предпоследнее — два очка и так далее.
Была ещё небольшая часть про веб-приложение; её я опущу, но суть в том, что участники отлаживали запросы на своих ноутбуках, а потом загружали их в приложение и в нём могли соревноваться с нашим «Шумахером» или со случайным запросом анонимного соперника, а затем пошагово анализировать результаты заезда. Как обычно, за веб-приложение и игровой движок большое спасибо Илье Баштанову.
Финал проводился в Санкт-Петербурге, в офисе нашей компании. На задачу отводилось восемь часов (включая обеденный перерыв на пироги). Традиционно мы разрешали пользоваться всеми благами интернета, кроме общения с другими людьми.
Трасса генерировалась случайно для каждого заезда. Вот реальный пример с отмеченными стартом и финишем:
Обычная ширина трека — четыре позиции, но присутствуют и сужения, особенно на поворотах. Трасса на рисунке имеет две развилки. Это максимум; как правило, развилка была одна, а некоторые трассы генерировались и вовсе без ответвлений.
Кстати, формирование трассы — сама по себе интересная задача. Каюсь, поленился: генератор написан на PL/pgSQL в процедурном стиле, а не одним запросом.
Одна из сложностей была связана с получением правдоподобной трассы для локального тестирования запросов. Лишь немногие догадались, что раз приложение рисует картинку, то оно, скорее всего, получает от сервера координаты, и их можно подсмотреть в браузере. А уж преобразовать JSON в INSERT‑ы — дело одной минуты. Программисту на SQL тоже не мешает быть немного хакером!
Для тех, кто захочет попробовать, вот релевантный фрагмент JSON, который можно было раздобыть:
Скрытый текст
{"track":[{"ring":1,"points":[{"x":44,"y":61},{"x":44,"y":66},{"x":44,"y":69},{"x":42,"y":71},{"x":48,"y":77},{"x":50,"y":77},{"x":53,"y":75},{"x":59,"y":71},{"x":59,"y":69},{"x":58,"y":67},{"x":60,"y":66},{"x":62,"y":66},{"x":67,"y":66},{"x":70,"y":66},{"x":72,"y":66},{"x":77,"y":66},{"x":80,"y":66},{"x":82,"y":66},{"x":83,"y":69},{"x":83,"y":70},{"x":80,"y":71},{"x":78,"y":71},{"x":73,"y":71},{"x":70,"y":71},{"x":69,"y":70},{"x":64,"y":75},{"x":64,"y":79},{"x":64,"y":81},{"x":60,"y":80},{"x":57,"y":82},{"x":52,"y":87},{"x":52,"y":89},{"x":52,"y":90},{"x":59,"y":97},{"x":60,"y":97},{"x":62,"y":95},{"x":67,"y":95},{"x":70,"y":95},{"x":74,"y":96},{"x":78,"y":90},{"x":78,"y":89},{"x":77,"y":87},{"x":80,"y":87},{"x":82,"y":87},{"x":82,"y":89},{"x":83,"y":92},{"x":87,"y":96},{"x":90,"y":96},{"x":94,"y":97},{"x":97,"y":90},{"x":97,"y":89},{"x":97,"y":87},{"x":97,"y":82},{"x":97,"y":79},{"x":98,"y":76},{"x":98,"y":71},{"x":98,"y":69},{"x":98,"y":65},{"x":98,"y":60},{"x":98,"y":59},{"x":99,"y":57},{"x":92,"y":50},{"x":90,"y":50},{"x":89,"y":51},{"x":88,"y":46},{"x":90,"y":46},{"x":94,"y":46},{"x":98,"y":40},{"x":98,"y":39},{"x":97,"y":36},{"x":97,"y":31},{"x":97,"y":29},{"x":98,"y":25},{"x":98,"y":20},{"x":98,"y":19},{"x":98,"y":16},{"x":98,"y":11},{"x":98,"y":9},{"x":97,"y":6},{"x":93,"y":2},{"x":90,"y":2},{"x":87,"y":1},{"x":82,"y":1},{"x":80,"y":1},{"x":77,"y":2},{"x":72,"y":2},{"x":70,"y":2},{"x":68,"y":0},{"x":63,"y":0},{"x":60,"y":0},{"x":59,"y":0},{"x":54,"y":5},{"x":54,"y":9},{"x":52,"y":10},{"x":59,"y":17},{"x":60,"y":17},{"x":64,"y":17},{"x":69,"y":17},{"x":70,"y":17},{"x":72,"y":17},{"x":77,"y":17},{"x":80,"y":17},{"x":82,"y":16},{"x":83,"y":19},{"x":82,"y":22},{"x":82,"y":27},{"x":82,"y":29},{"x":82,"y":31},{"x":80,"y":32},{"x":79,"y":30},{"x":79,"y":29},{"x":77,"y":25},{"x":74,"y":22},{"x":70,"y":22},{"x":69,"y":21},{"x":64,"y":21},{"x":60,"y":21},{"x":58,"y":21},{"x":53,"y":21},{"x":50,"y":21},{"x":47,"y":21},{"x":42,"y":21},{"x":40,"y":21},{"x":37,"y":21},{"x":33,"y":27},{"x":33,"y":29},{"x":34,"y":32},{"x":37,"y":35},{"x":40,"y":35},{"x":43,"y":35},{"x":44,"y":39},{"x":42,"y":42},{"x":40,"y":42},{"x":38,"y":40},{"x":33,"y":40},{"x":30,"y":40},{"x":28,"y":42},{"x":27,"y":39},{"x":28,"y":35},{"x":28,"y":30},{"x":28,"y":29},{"x":29,"y":27},{"x":22,"y":20},{"x":20,"y":20},{"x":17,"y":21},{"x":13,"y":27},{"x":13,"y":29},{"x":14,"y":30},{"x":14,"y":35},{"x":14,"y":39},{"x":14,"y":41},{"x":10,"y":40},{"x":7,"y":42},{"x":7,"y":39},{"x":8,"y":36},{"x":8,"y":31},{"x":8,"y":29},{"x":7,"y":25},{"x":7,"y":20},{"x":7,"y":19},{"x":7,"y":15},{"x":10,"y":17},{"x":12,"y":15},{"x":17,"y":15},{"x":20,"y":15},{"x":23,"y":15},{"x":28,"y":15},{"x":30,"y":15},{"x":33,"y":16},{"x":38,"y":16},{"x":40,"y":16},{"x":43,"y":15},{"x":49,"y":11},{"x":49,"y":9},{"x":48,"y":5},{"x":44,"y":1},{"x":40,"y":1},{"x":38,"y":1},{"x":33,"y":1},{"x":30,"y":1},{"x":28,"y":0},{"x":23,"y":0},{"x":20,"y":0},{"x":19,"y":0},{"x":14,"y":0},{"x":10,"y":0},{"x":8,"y":1},{"x":3,"y":1},{"x":0,"y":1},{"x":0,"y":6},{"x":3,"y":6},{"x":8,"y":6},{"x":10,"y":6},{"x":14,"y":5},{"x":19,"y":5},{"x":20,"y":5},{"x":23,"y":5},{"x":28,"y":5},{"x":30,"y":5},{"x":33,"y":6},{"x":38,"y":6},{"x":40,"y":6},{"x":44,"y":6},{"x":43,"y":9},{"x":44,"y":11},{"x":40,"y":10},{"x":38,"y":11},{"x":33,"y":11},{"x":30,"y":11},{"x":28,"y":10},{"x":23,"y":10},{"x":20,"y":10},{"x":17,"y":10},{"x":12,"y":10},{"x":10,"y":10},{"x":9,"y":12},{"x":2,"y":15},{"x":2,"y":19},{"x":2,"y":20},{"x":2,"y":25},{"x":2,"y":29},{"x":3,"y":31},{"x":3,"y":36},{"x":3,"y":39},{"x":2,"y":42},{"x":7,"y":47},{"x":10,"y":47},{"x":13,"y":45},{"x":19,"y":41},{"x":19,"y":39},{"x":19,"y":35},{"x":19,"y":30},{"x":19,"y":29},{"x":18,"y":27},{"x":20,"y":26},{"x":22,"y":25},{"x":24,"y":29},{"x":23,"y":30},{"x":23,"y":35},{"x":23,"y":39},{"x":22,"y":41},{"x":28,"y":47},{"x":30,"y":47},{"x":33,"y":45},{"x":38,"y":45},{"x":40,"y":45},{"x":42,"y":47},{"x":47,"y":42},{"x":47,"y":39},{"x":49,"y":36},{"x":43,"y":30},{"x":40,"y":30},{"x":37,"y":30},{"x":39,"y":29},{"x":38,"y":27},{"x":40,"y":26},{"x":42,"y":26},{"x":47,"y":26},{"x":50,"y":26},{"x":53,"y":26},{"x":58,"y":26},{"x":60,"y":26},{"x":64,"y":26},{"x":69,"y":26},{"x":70,"y":26},{"x":74,"y":27},{"x":72,"y":29},{"x":74,"y":30},{"x":79,"y":35},{"x":80,"y":35},{"x":83,"y":37},{"x":87,"y":31},{"x":87,"y":29},{"x":87,"y":27},{"x":87,"y":22},{"x":87,"y":19},{"x":88,"y":17},{"x":82,"y":11},{"x":80,"y":11},{"x":77,"y":12},{"x":72,"y":12},{"x":70,"y":12},{"x":69,"y":12},{"x":64,"y":12},{"x":60,"y":12},{"x":59,"y":12},{"x":57,"y":9},{"x":59,"y":5},{"x":60,"y":5},{"x":63,"y":5},{"x":68,"y":5},{"x":70,"y":5},{"x":72,"y":7},{"x":77,"y":7},{"x":80,"y":7},{"x":82,"y":6},{"x":87,"y":6},{"x":90,"y":6},{"x":93,"y":7},{"x":92,"y":9},{"x":93,"y":11},{"x":93,"y":16},{"x":93,"y":19},{"x":93,"y":20},{"x":93,"y":25},{"x":93,"y":29},{"x":92,"y":31},{"x":92,"y":36},{"x":92,"y":39},{"x":93,"y":40},{"x":90,"y":41},{"x":88,"y":41},{"x":83,"y":41},{"x":80,"y":41},{"x":77,"y":41},{"x":72,"y":41},{"x":70,"y":41},{"x":67,"y":40},{"x":69,"y":39},{"x":69,"y":36},{"x":63,"y":30},{"x":60,"y":30},{"x":57,"y":30},{"x":54,"y":37},{"x":54,"y":39},{"x":54,"y":40},{"x":54,"y":45},{"x":54,"y":49},{"x":52,"y":50},{"x":59,"y":57},{"x":60,"y":57},{"x":62,"y":57},{"x":62,"y":61},{"x":60,"y":61},{"x":57,"y":61},{"x":53,"y":67},{"x":53,"y":69},{"x":54,"y":71},{"x":50,"y":70},{"x":48,"y":72},{"x":47,"y":69},{"x":49,"y":66},{"x":49,"y":61},{"x":49,"y":59},{"x":49,"y":57},{"x":42,"y":50},{"x":40,"y":50},{"x":38,"y":51},{"x":33,"y":51},{"x":30,"y":51},{"x":29,"y":52},{"x":22,"y":55},{"x":22,"y":59},{"x":22,"y":62},{"x":27,"y":67},{"x":30,"y":67},{"x":34,"y":67},{"x":32,"y":69},{"x":33,"y":71},{"x":30,"y":71},{"x":29,"y":71},{"x":23,"y":75},{"x":23,"y":79},{"x":22,"y":80},{"x":29,"y":87},{"x":30,"y":87},{"x":34,"y":86},{"x":39,"y":86},{"x":40,"y":86},{"x":44,"y":87},{"x":42,"y":89},{"x":43,"y":90},{"x":40,"y":91},{"x":37,"y":91},{"x":32,"y":91},{"x":30,"y":91},{"x":27,"y":91},{"x":22,"y":91},{"x":20,"y":91},{"x":17,"y":92},{"x":12,"y":92},{"x":10,"y":92},{"x":8,"y":92},{"x":7,"y":89},{"x":9,"y":86},{"x":10,"y":85},{"x":12,"y":86},{"x":18,"y":82},{"x":18,"y":79},{"x":18,"y":77},{"x":18,"y":72},{"x":18,"y":69},{"x":18,"y":67},{"x":18,"y":62},{"x":18,"y":59},{"x":18,"y":55},{"x":14,"y":51},{"x":10,"y":51},{"x":7,"y":50},{"x":4,"y":57},{"x":4,"y":59},{"x":3,"y":62},{"x":3,"y":67},{"x":3,"y":69},{"x":3,"y":71},{"x":0,"y":71},{"x":0,"y":76},{"x":3,"y":76},{"x":8,"y":71},{"x":8,"y":69},{"x":8,"y":67},{"x":8,"y":62},{"x":8,"y":59},{"x":9,"y":57},{"x":10,"y":55},{"x":14,"y":56},{"x":13,"y":59},{"x":13,"y":62},{"x":13,"y":67},{"x":13,"y":69},{"x":13,"y":72},{"x":13,"y":77},{"x":13,"y":79},{"x":13,"y":82},{"x":10,"y":81},{"x":8,"y":80},{"x":4,"y":86},{"x":4,"y":89},{"x":2,"y":91},{"x":8,"y":97},{"x":10,"y":97},{"x":12,"y":97},{"x":17,"y":97},{"x":20,"y":97},{"x":22,"y":96},{"x":27,"y":96},{"x":30,"y":96},{"x":32,"y":96},{"x":37,"y":96},{"x":40,"y":96},{"x":44,"y":96},{"x":48,"y":90},{"x":48,"y":89},{"x":47,"y":85},{"x":44,"y":82},{"x":40,"y":82},{"x":39,"y":81},{"x":34,"y":81},{"x":30,"y":81},{"x":29,"y":82},{"x":27,"y":79},{"x":28,"y":75},{"x":30,"y":76},{"x":33,"y":76},{"x":38,"y":71},{"x":38,"y":69},{"x":37,"y":65},{"x":34,"y":62},{"x":30,"y":62},{"x":27,"y":62},{"x":27,"y":59},{"x":27,"y":55},{"x":30,"y":57},{"x":33,"y":56},{"x":38,"y":56},{"x":40,"y":56},{"x":42,"y":55},{"x":44,"y":59}]},{"ring":2,"points":[{"x":64,"y":42},{"x":67,"y":45},{"x":70,"y":45},{"x":72,"y":46},{"x":77,"y":46},{"x":80,"y":46},{"x":83,"y":46},{"x":84,"y":51},{"x":80,"y":51},{"x":79,"y":52},{"x":74,"y":52},{"x":70,"y":52},{"x":67,"y":52},{"x":62,"y":52},{"x":60,"y":52},{"x":59,"y":52},{"x":57,"y":49},{"x":59,"y":45},{"x":59,"y":40},{"x":59,"y":39},{"x":59,"y":37},{"x":60,"y":35},{"x":63,"y":35},{"x":64,"y":39}]},{"ring":3,"points":[{"x":63,"y":85},{"x":69,"y":81},{"x":69,"y":79},{"x":69,"y":75},{"x":70,"y":75},{"x":73,"y":76},{"x":78,"y":76},{"x":80,"y":76},{"x":84,"y":76},{"x":88,"y":70},{"x":88,"y":69},{"x":88,"y":67},{"x":82,"y":61},{"x":80,"y":61},{"x":77,"y":61},{"x":72,"y":61},{"x":70,"y":61},{"x":67,"y":61},{"x":67,"y":57},{"x":70,"y":57},{"x":74,"y":57},{"x":79,"y":57},{"x":80,"y":57},{"x":84,"y":56},{"x":89,"y":56},{"x":90,"y":56},{"x":92,"y":55},{"x":94,"y":59},{"x":93,"y":60},{"x":93,"y":65},{"x":93,"y":69},{"x":93,"y":71},{"x":93,"y":76},{"x":93,"y":79},{"x":92,"y":82},{"x":92,"y":87},{"x":92,"y":89},{"x":92,"y":90},{"x":90,"y":92},{"x":87,"y":91},{"x":88,"y":89},{"x":87,"y":87},{"x":82,"y":82},{"x":80,"y":82},{"x":77,"y":82},{"x":72,"y":87},{"x":72,"y":89},{"x":73,"y":90},{"x":70,"y":91},{"x":67,"y":90},{"x":62,"y":90},{"x":60,"y":90},{"x":59,"y":92},{"x":57,"y":89},{"x":57,"y":87},{"x":60,"y":87}]}]}
Итак, как подступиться к задаче? Сначала расскажу про наш «Шумахер», а потом посетую немного о достигнутых результатах.
Шумахер
Наверное, первое, что приходит в голову, — это свести задачу к обычному поиску кратчайшего пути в графе. Вот только очень уж развесистым получается этот граф: допустимых ходов слишком много, причём зависят они и от местоположения, и от вектора скорости.
А ведь поиск пути придется выполнять на каждом ходу. Как прикинуть временнóй бюджет? Например, можно написать однострочный запрос-камикадзе, делающий некорректный ход, и отправить его играть с «Шумахером». Просмотр нескольких партий покажет, что добраться до финиша обычно получается ходов за 280, возьмём 300 для ровного счёта. При отведённой на заезд минуте на один ход приходится 200 мс, а лучше бы справляться быстрее, чтобы не поймать тайм-аут при нагруженном сервере. Не сказать, что очень много.
Тогда приходит следующая, более плодотворная идея: заменить глобальную оптимизацию локальной, то есть вместо поиска цепочки перемещений, ведущей к победе, пытаться за несколько ходов максимально приблизиться к финишу. И тут есть два варианта.
Большинство участников выбрали строго локальную оптимизацию, применяя для оценки перемещения те или иные эвристики (например, можно пытаться отъехать как можно дальше от текущей позиции). К минусам такого решения мы ещё вернёмся.
«Шумахер» действует иначе. Для оценки продвижения к финишу он строит градиент: чем дальше позиция от старта и чем она ближе к финишу, тем больший вес она получает. Чем же это отличается от обычного перебора всех вариантов? Как минимум, не надо учитывать вектор скорости, и можно уповать на эффективность волнового алгоритма.
Но давайте по порядку. Нам интересны только позиции внутри многоугольника, вот этим в первую очередь и займёмся.
Принадлежность точки многоугольнику
Как определить, принадлежит ли точка многоугольнику? Стандартный алгоритм состоит в том, чтобы выпустить из точки луч (в любую сторону, но для определённости пусть идёт влево) и посчитать, сколько отрезков многоугольника он пересечёт. Если число пересечений нечётное, точка находится внутри. Дьявол, как обычно, в частных случаях. Я решительно избавился от них, сразу выкинув точки, лежащие на границах многоугольника, а луч выпускал из точки, чуть-чуть сдвинутой вниз, чтобы не думать про горизонтальные отрезки. Поскольку у нас целочисленные координаты и не очень большое поле, такая вольность вполне сходит с рук.
Формулу пересечения отрезков несложно написать самому, но в Постгресе есть геометрические типы lseg и point, для которых все базовые операции уже реализованы эффективно и правильно. Грех этим не воспользоваться.
Многие участники почему-то не воспользовались и реализовали «самодельную геометрию на векторных произведениях», как это прекрасно охарактеризовал DeepSeek.
Зато пара человек вспомнили, что в Постгресе есть тип и для многоугольников (
polygon), а к нему — готовая функция проверки принадлежности точки. Правда, поддерживаются только многоугольники без дырок (это вам не PostGIS), так что полости приходится учитывать отдельно. Ну и формировать полигон из точек тоже не очень удобно.
Для начала разобьём многоугольник на отдельные отрезки (приходится принимать меры, чтобы не потерять отрезок, соединяющий первую и последнюю точки):
WITH RECURSIVE segments(x1,y1,x2,y2) AS ( SELECT x1, y1, coalesce(x2,x3), coalesce(y2,y3) FROM ( SELECT x x1, y y1, lead(x) OVER (PARTITION BY ring_id ORDER BY point_id) x2, lead(y) OVER (PARTITION BY ring_id ORDER BY point_id) y2, first_value(x) OVER (PARTITION BY ring_id ORDER BY point_id) x3, first_value(y) OVER (PARTITION BY ring_id ORDER BY point_id) y3 FROM racetrack ) ) SELECT count(*) FROM segments;
Затем найдём внутренние позиции:
... all_points(x,y) AS ( SELECT x, y FROM generate_series(0,99) x, generate_series(0,99) y ), interior(x,y) AS ( WITH points(x,y) AS ( SELECT x, y FROM all_points EXCEPT -- не на контуре полигона SELECT x,y FROM all_points JOIN segments ON point(x,y) <@ lseg(point(x1,y1),point(x2,y2)) ), intersections(x,y,n) AS ( SELECT x, y, count(*) FROM points JOIN segments ON lseg(point(0,y-0.001),point(x,y-0.001)) ?# lseg(point(x1,y1),point(x2,y2)) GROUP BY x, y ) SELECT * FROM intersections WHERE n % 2 = 1 ) SELECT count(*) FROM interior;
Посмотрим, что у нас получилось:
К слову, визуализация очень помогает отладке. А в наше время для этого даже не надо прилагать усилий: любая ИИшечка сходу предложит скрипт на Питоне, рисующий такую картинку по данным, представленным в любом формате.
Волновой алгоритм
Теперь займёмся градиентом, или же картой расстояний. Для этого придуман волновой алгоритм, вариацию которого мы сейчас и реализуем.
Первый этап алгоритма — распространение волны. Где у нас старт, мы знаем по таблице cars (по крайней мере на первом ходу; что там будет дальше, пока и думать не хочется), так что сразу присвоим стартовым позициям номер 1. Затем присвоим следующий номер точкам, соседним с единицами, и так далее. Когда дойдём до конца, все точки будут занумерованы, причём чем дальше к финишу, тем больше будет число.
Чуть повозившись, можно прийти к чему-то подобному:
... dir4(dx,dy) AS ( VALUES (0,1), (1,0), (0,-1), (-1,0) ), gradient_forward(x,y,dist) AS ( WITH RECURSIVE -- нумеруем точки от старта к финишу num_forward(x,y,dist) AS ( -- старт формально не знаем, но там сейчас стоят машины SELECT x, y, 1 FROM cars UNION ALL -- добавляем соседей и оставляем уже пройденный путь ( WITH prev AS ( SELECT * FROM num_forward ), new AS ( SELECT s.x, s.y, prev.dist + 1 FROM prev CROSS JOIN dir4 d JOIN ( SELECT x, y FROM interior UNION ALL SELECT x, y FROM all_points p, finish WHERE x BETWEEN least(x1,x2) AND greatest(x1,x2) AND y BETWEEN least(y1,y2) AND greatest(y1,y2) ) s ON s.x = prev.x + dx AND s.y = prev.y + dy WHERE prev.dist = (SELECT max(dist) FROM prev) AND NOT EXISTS ( SELECT NULL FROM prev WHERE prev.x = s.x AND prev.y = s.y ) ) SELECT * FROM new UNION SELECT * FROM prev WHERE (SELECT count(*) FROM new) > 0 ) ) -- схлопнем SELECT x, y, any_value(dist) FROM num_forward GROUP BY x, y ) SELECT count(*) FROM gradient_forward;
Тут стоит заметить, что перемещение между двумя соседними внутренними позициями не всегда будет корректным. Именно поэтому я использую 4-связность: ход по диагонали может «пройти сквозь стену», подпортив градиент. (Ход по вертикали или горизонтали тоже может оказаться некорректным, но для наших трасс эта нехорошая возможность не реализуется.) Совсем правильно было бы проверять перемещение на пересечение границ, но сейчас наша задача — построить градиент относительно быстро, поэтому не отвлекаемся.
На картинке:
Что делать с развилками? По градиенту мы не сможем понять, в какую сторону сворачивать, если только не заглядывать достаточно далеко (а на это нет времени). Для этого и нужен второй этап алгоритма — восстановление пути. Мы можем убрать лишние (то есть более длинные) дорожки, повторив процедуру задом наперёд: пойдём теперь от финиша к старту, двигаясь к точкам с тем же или меньшим номером.
... dir8(dx,dy) AS ( VALUES (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1) ), gradient(x,y,dist) AS ( WITH RECURSIVE -- теперь надо пройтись от финиша к старту, чтобы отбросить длинные пути num_backward(x,y,dist) AS ( -- финиш там, где максимальный номер SELECT x, y, dist FROM gradient_forward CROSS JOIN finish WHERE x BETWEEN least(x1,x2) AND greatest(x1,x2) AND y BETWEEN least(y1,y2) AND greatest(y1,y2) UNION ALL -- добавляем соседей с номером, меньшим на один, и оставляем уже пройденный путь ( WITH prev AS ( SELECT * FROM num_backward ), new AS ( SELECT s.* FROM prev CROSS JOIN dir8 d JOIN gradient_forward s ON s.x = prev.x + dx AND s.y = prev.y + dy AND (s.dist = prev.dist - 1 OR s.dist = prev.dist) WHERE prev.dist = (SELECT min(dist) FROM prev) AND NOT EXISTS ( SELECT NULL FROM prev WHERE prev.x = s.x AND prev.y = s.y ) ) SELECT * FROM new UNION SELECT * FROM prev WHERE (SELECT count(*) FROM new) > 0 ) ) -- схлопнем SELECT x, y, any_value(dist) FROM num_backward GROUP BY x, y ) SELECT count(*) FROM gradient;
На обратном ходу я использовал 8-связность, но, как видите, часть ходов всё равно пропала:
Вообще-то это баг, и визуализация моментально выводит его на чистую воду. Но в итоге баг оказался фичей. Дело в том, что оставшаяся (раскрашенная на картинке) область определяет множество допустимых позиций, поскольку только про них мы знаем расстояние до финиша. Другие позиции запрос рассматривать не будет, несмотря на то что они могут быть разрешены правилами. Чем меньше позиций, тем вроде бы хуже, поскольку уменьшается маневренность. Но есть и плюсы. Во-первых, чем меньше вариантов, тем быстрее их перебирать. А во-вторых, на тестовых заездах мне показалось, что машина меньше рыскает и мечется между соседними позициями с одинаковым весом. В итоге я сознательно оставил запрос в таком виде, хотя поправить его совсем не сложно.
Что же показывает секундомер? Пять с половиной секунд у меня на ноутбуке. Да-а, с бюджетом никак не бьётся, а возможностей ускорить процесс на порядки не очень-то видно.
Кеширование спешит на помощь
Но сдаваться рано. Если перечитать задание, в нём можно найти тонкий намёк:
Перед каждым ходом таблица
carsперезаписывается актуальной информацией; таблицыracetrackиfinishостаются в том состоянии, в котором они были после выполнения предыдущего хода.
Более толстый намёк состоял в том, что на сервере «Шумахер» тратил около 10 секунд на первый ход, зато потом ехал очень быстро.
Да-да, это кеш. Если мы сохраним добытую информацию в racetrack (ну или в finish), то сможем воспользоваться ею на следующем ходу. Чтобы отделить свои данные от исходных, можно, например, взять нулевой или отрицательный ring_id. Отсутствие серьёзных ограничений целостности на таблице — ещё одна лёгкая подсказка; обычно я проставляю все ограничения, какие только можно.
Минимальный фрагмент, кеширующий результат выполнения запроса, выглядит так:
\timing on WITH slow(x,y) AS ( -- медленный запрос на 10 секунд SELECT g, g FROM (SELECT pg_sleep(1), generate_series(1,10) g) WHERE NOT EXISTS (SELECT NULL FROM racetrack WHERE ring_id = 0) ), cache_miss(x,y) AS ( -- вставляем результат запроса в кеш и возвращаем его... INSERT INTO racetrack(ring_id,point_id,x,y) SELECT 0, 0, x, y FROM slow WHERE -- ...но только если кеш ещё пуст NOT EXISTS (SELECT NULL FROM racetrack WHERE ring_id = 0) RETURNING x, y ) -- возвращаем результат из кеша... SELECT x, y FROM racetrack WHERE ring_id = 0 UNION ALL -- ...и из процедуры начального заполнения SELECT x, y FROM cache_miss;
Первый раз:
Time: 11018.172 ms (00:11.018)
Второй и дальше:
Time: 1.078 ms
Мы, очевидно, должны сохранить два набора данных: градиент (чтобы определять направление движения) и отрезки (чтобы проверять корректность ходов). Отрезки я сохраняю в столбцы ring_id, point_id, x и y (у первых двух координат меняю знак), а градиент сохраняю с ring_id = -100. Разумеется, можно выбрать и другую схему, это ни на что не влияет. Главное, самому не запутаться.
... segments_cache_miss(x1,y1,x2,y2) AS ( INSERT INTO racetrack(ring_id,point_id,x,y) SELECT -s.x1, -s.y1, s.x2, s.y2 FROM segments s CROSS JOIN cars c CROSS JOIN finish f WHERE c.my -- не кешируем финишный сегмент, иначе не сможем финишировать AND NOT point( (f.x1+f.x2)/2, (f.y1+f.y2)/2 ) <@ lseg(point(s.x1,s.y1),point(s.x2,s.y2)) AND NOT EXISTS (SELECT NULL FROM racetrack WHERE ring_id BETWEEN -99 AND 0) RETURNING ring_id, point_id, x, y ), segments_cached(x1,y1,x2,y2) AS ( SELECT -ring_id, -point_id, x, y FROM racetrack WHERE ring_id BETWEEN -99 AND 0 UNION ALL SELECT -x1, -y1, x2, y2 FROM segments_cache_miss ), gradient_cache_miss(x,y,dist) AS ( INSERT INTO racetrack(ring_id,point_id,x,y) SELECT -100, dist, x, y FROM gradient WHERE NOT EXISTS (SELECT NULL FROM racetrack WHERE ring_id = -100) RETURNING x, y, point_id ), gradient_cached(x,y,dist) AS ( SELECT x, y, point_id FROM racetrack WHERE ring_id = -100 UNION ALL SELECT x, y, dist FROM gradient_cache_miss ) ...
Жизнь налаживается.
Выбираем лучший ход
Теперь у нас есть всё, чтобы вычислить сам ход. Для этого будем просчитывать ситуацию на несколько шагов вперёд. Сильно далеко заглядывать нельзя из-за риска тайм-аута, но всё же надо отдалиться достаточно, чтобы уверенно определить направление к финишу, не обращая внимание на шум градиента.
Методом проб и ошибок я выбрал такой подход: первые три шага никак не ограничиваются, а затем запрос начинает тормозить «в пол». Если сумел остановиться, не врезавшись, ход как минимум безопасен, с трассы не вылетим.
Я пробовал ещё вариант, который просматривал ситуацию на несколько шагов, не тормозя. Но стабильно держаться в рамках трека удавалось только при ограничении скорости до четырёх. Ездил такой запрос, кстати, очень неплохо, но на длинных прямых участках — слишком осторожно, так что назвать его Шумахером не повернулся язык.
Остаётся взять найденные безопасные цепочки ходов, выбрать из них ту, что продвинулась как можно дальше в сторону финиша, и взять из неё самый первый ход.
Учитываем, конечно, что не каждое перемещение между допустимыми позициями будет допустимо: есть риск с размаху проскочить через пару стен. Поэтому дополнительно проверяем, чтобы ход не пересекал ни одного отрезка.
... pos(x0,y0,x,y) AS ( SELECT x_prev, y_prev, x, y FROM cars WHERE my ), schumacher( x0, y0, -- предыдущая позиция x, y, -- текущая позиция dist, -- текущая дальность x1 ,y1, -- самый первый ход (не меняется) v, -- скорость первого хода (не меняется) safe, -- успели ли затормозить k -- порядковый номер хода ) AS ( -- Первые три хода любые, а дальше тормозим. Если оттормозились и не врезались - можно брать. SELECT r.x, r.y, p.x, p.y, p.dist, p.x, p.y, greatest( abs(p.x-r.x), abs(p.y-r.y) ), -- скорость как метрика Чебышёва greatest( abs(p.x-r.x), abs(p.y-r.y) ) <= 1, 1 FROM pos r JOIN gradient_cached p ON abs(p.x-r.x - (r.x-r.x0)) <= 1 AND abs(p.y-r.y - (r.y-r.y0)) <= 1 WHERE NOT EXISTS ( -- ни на кого не наезжаем SELECT NULL FROM cars c WHERE NOT my AND p.x = c.x AND p.y = c.y ) AND NOT EXISTS ( -- пересечения с сегментами (включая касания) SELECT NULL FROM segments_cached s WHERE least(s.x1,s.x2) <= greatest(r.x,p.x) AND greatest(s.x1,s.x2) >= least(r.x,p.x) AND least(s.y1,s.y2) <= greatest(r.y,p.y) AND greatest(s.y1,s.y2) >= least(r.y,p.y) AND lseg(point(r.x,r.y),point(p.x,p.y)) ?# lseg(point(s.x1,s.y1),point(s.x2,s.y2)) ) UNION ALL SELECT r.x, r.y, p.x, p.y, p.dist, r.x1, r.y1, r.v, greatest( abs(p.x-r.x), abs(p.y-r.y) ) <= 1, r.k + 1 FROM schumacher r JOIN gradient_cached p ON abs(p.x-r.x - (r.x-r.x0)) <= 1 AND abs(p.y-r.y - (r.y-r.y0)) <= 1 AND (r.k + 1 < 4 OR -- начиная с третьего хода - тормозим ( greatest( abs(p.x-r.x), abs(p.y-r.y) ) -- текущая скорость < greatest( abs(r.x-r.x0), abs(r.y-r.y0) ) -- предыдущая скорость ) ) WHERE NOT r.safe -- пока не остановились -- для ходов после первого наезд на другие машины не проверяем AND NOT EXISTS ( -- пересечения с сегментами (включая касания) SELECT NULL FROM segments_cached s WHERE least(s.x1,s.x2) <= greatest(r.x,p.x) AND greatest(s.x1,s.x2) >= least(r.x,p.x) AND least(s.y1,s.y2) <= greatest(r.y,p.y) AND greatest(s.y1,s.y2) >= least(r.y,p.y) AND lseg(point(r.x,r.y),point(p.x,p.y)) ?# lseg(point(s.x1,s.y1),point(s.x2,s.y2)) ) ) SELECT x1, y1 -- выбираем безопасный ход, который обещает лучший результат FROM schumacher WHERE safe ORDER by dist DESC, v DESC, random() LIMIT 1;
В таком виде запрос уже работает, но на финишной прямой будет не разгоняться, а тормозить, чтобы завершить ход ровно у черты. Это некрасиво и может стоить победы. Простое решение — продлить область градиента за финиш. Это несложно сделать, поскольку из ограничения целостности на finish мы знаем, что финишный отрезок лежит на одном из краёв квадрата 100×100.
... overrun(n,x,y) AS ( SELECT 1000+d, CASE WHEN x1 = 0 THEN -d ELSE 99 + d END, y FROM finish, generate_series(1,15) d, generate_series(least(y1,y2)+1, greatest(y1,y2)-1) y WHERE x1 = x2 UNION ALL SELECT 1000+d, x, CASE WHEN y1 = 0 THEN -d ELSE 99 + d END FROM finish, generate_series(1,15) d, generate_series(least(x1,x2)+1, greatest(x1,x2)-1) x WHERE y1 = y2 ), ...
Остаётся просто добавить эту площадку с помощью UNION ALL к gradient_cached в запросе schumacher.
Её можно было бы сохранить вместе с остальным градиентом в racetrack, но мешают ограничения целостности на x и y. Нет проблем придумать другое кодирование, но прямоугольник вычисляется достаточно быстро, чтобы не беспокоиться о кешировании.
На всё про всё — 241 строчка. Вот запрос целиком для удобства:
Скрытый текст
WITH RECURSIVE -- все точки в границах ограничений all_points(x,y) AS ( SELECT x, y FROM generate_series(0,99) x, generate_series(0,99) y ), -- площадка за финишной чертой overrun(n,x,y) AS ( SELECT 1000+d, CASE WHEN x1 = 0 THEN -d ELSE 99 + d END, y FROM finish, generate_series(1,15) d, generate_series(least(y1,y2)+1, greatest(y1,y2)-1) y WHERE x1 = x2 UNION ALL SELECT 1000+d, x, CASE WHEN y1 = 0 THEN -d ELSE 99 + d END FROM finish, generate_series(1,15) d, generate_series(least(x1,x2)+1, greatest(x1,x2)-1) x WHERE y1 = y2 ), -- отрезки многоугольника segments(x1,y1,x2,y2) AS ( SELECT x1, y1, coalesce(x2,x3), coalesce(y2,y3) FROM ( SELECT x x1, y y1, lead(x) OVER (PARTITION BY ring_id ORDER BY point_id) x2, lead(y) OVER (PARTITION BY ring_id ORDER BY point_id) y2, first_value(x) OVER (PARTITION BY ring_id ORDER BY point_id) x3, first_value(y) OVER (PARTITION BY ring_id ORDER BY point_id) y3 FROM racetrack WHERE ring_id > 0 -- не нужно, но удобно для отладки ) ), segments_cache_miss(x1,y1,x2,y2) AS ( INSERT INTO racetrack(ring_id,point_id,x,y) SELECT -s.x1, -s.y1, s.x2, s.y2 FROM segments s CROSS JOIN cars c CROSS JOIN finish f WHERE c.my -- не кешируем финишный сегмент, иначе не финишируем AND NOT point( (f.x1+f.x2)/2, (f.y1+f.y2)/2 ) <@ lseg(point(s.x1,s.y1),point(s.x2,s.y2)) AND NOT EXISTS (SELECT NULL FROM racetrack WHERE ring_id BETWEEN -99 AND 0) RETURNING ring_id, point_id, x, y ), segments_cached(x1,y1,x2,y2) AS ( SELECT -ring_id, -point_id, x, y FROM racetrack WHERE ring_id BETWEEN -99 AND 0 UNION ALL SELECT -x1, -y1, x2, y2 FROM segments_cache_miss ), -- внутренние точки многоугольника interior(x,y,n) AS ( -- здесь используем segments, а не cached_segments: должны быть все сегменты, а мы не кешируем финиш WITH points(x,y) AS ( SELECT x, y FROM all_points EXCEPT -- не на контуре полигона SELECT x,y FROM all_points JOIN segments ON point(x,y) <@ lseg(point(x1,y1),point(x2,y2)) ), intersections(x,y,n) AS ( SELECT x, y, count(*) FROM points JOIN segments ON lseg(point(0,y-0.001),point(x,y-0.001)) ?# lseg(point(x1,y1),point(x2,y2)) GROUP BY x, y ) SELECT * FROM intersections WHERE n % 2 = 1 ), dir4(dx,dy) AS ( VALUES (0,1), (1,0), (0,-1), (-1,0) ), -- градиент от старта до финиша gradient_forward(x,y,dist) AS ( WITH RECURSIVE -- нумеруем точки от старта к финишу num_forward(x,y,dist) AS ( -- старт формально не знаем, но там сейчас стоят машины SELECT x, y, 1 FROM cars UNION ALL -- добавляем соседей и оставляем уже пройденный путь ( WITH prev AS ( SELECT * FROM num_forward ), new AS ( SELECT s.x, s.y, prev.dist + 1 FROM prev CROSS JOIN dir4 d -- dir8 может сделать некорректный ход (острый угол) JOIN ( SELECT x, y FROM interior UNION ALL SELECT x, y FROM all_points p, finish WHERE x BETWEEN least(x1,x2) AND greatest(x1,x2) AND y BETWEEN least(y1,y2) AND greatest(y1,y2) ) s ON s.x = prev.x + dx AND s.y = prev.y + dy WHERE prev.dist = (SELECT max(dist) FROM prev) AND NOT EXISTS ( SELECT NULL FROM prev WHERE prev.x = s.x AND prev.y = s.y ) ) SELECT * FROM new UNION SELECT * FROM prev WHERE (SELECT count(*) FROM new) > 0 ) ) -- схлопнем SELECT x, y, any_value(dist) FROM num_forward GROUP BY x, y ), dir8(dx,dy) AS ( VALUES (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1) ), -- градиент без лишних ветвей gradient(x,y,dist) AS ( WITH RECURSIVE -- теперь надо пройтись от финиша к старту, чтобы отбросить длинные пути num_backward(x,y,dist) AS ( -- финиш там, где максимальный номер SELECT x, y, dist FROM gradient_forward CROSS JOIN finish WHERE x BETWEEN least(x1,x2) AND greatest(x1,x2) AND y BETWEEN least(y1,y2) AND greatest(y1,y2) UNION ALL -- добавляем соседей с номером, меньшим на один, и оставляем уже пройденный путь ( WITH prev AS ( SELECT * FROM num_backward ), new AS ( SELECT s.* FROM prev CROSS JOIN dir8 d -- а обратно - dir8, чтобы захватить побольше точек вокруг JOIN gradient_forward s ON s.x = prev.x + dx AND s.y = prev.y + dy AND (s.dist = prev.dist - 1 OR s.dist = prev.dist) WHERE prev.dist = (SELECT min(dist) FROM prev) AND NOT EXISTS ( SELECT NULL FROM prev WHERE prev.x = s.x AND prev.y = s.y ) ) SELECT * FROM new UNION SELECT * FROM prev WHERE (SELECT count(*) FROM new) > 0 ) ) -- схлопнем SELECT x, y, any_value(dist) FROM num_backward GROUP BY x, y ), gradient_cache_miss(x,y,dist) AS ( INSERT INTO racetrack(ring_id,point_id,x,y) SELECT -100, dist, x, y FROM gradient WHERE NOT EXISTS (SELECT NULL FROM racetrack WHERE ring_id = -100) RETURNING x, y, point_id ), gradient_cached(x,y,dist) AS ( SELECT x, y, point_id FROM racetrack WHERE ring_id = -100 UNION ALL SELECT x, y, dist FROM gradient_cache_miss ), -- предыдущая и текущая позиции pos(x0,y0,x,y) AS ( SELECT x_prev, y_prev, x, y FROM cars WHERE my ), -- основной запрос schumacher( x0, y0, -- предыдущая позиция x, y, -- текущая позиция dist, -- текущая дальность x1 ,y1, -- самый первый ход (не меняется) v, -- скорость первого хода (не меняется) safe, -- успели ли затормозить k -- порядковый номер хода ) AS ( -- Первые три хода любые, а дальше тормозим. Если оттормозились и не врезались - можно брать. SELECT r.x, r.y, p.x, p.y, p.dist, p.x, p.y, greatest( abs(p.x-r.x), abs(p.y-r.y) ), -- скорость как метрика Чебышёва greatest( abs(p.x-r.x), abs(p.y-r.y) ) <= 1, 1 FROM pos r JOIN (SELECT * FROM gradient_cached UNION ALL SELECT * FROM overrun) p ON abs(p.x-r.x - (r.x-r.x0)) <= 1 AND abs(p.y-r.y - (r.y-r.y0)) <= 1 WHERE NOT EXISTS ( -- ни на кого не наезжаем SELECT NULL FROM cars c WHERE NOT my AND p.x = c.x AND p.y = c.y ) AND NOT EXISTS ( -- пересечения с сегментами (включая касания) SELECT NULL FROM segments_cached s WHERE least(s.x1,s.x2) <= greatest(r.x,p.x) AND greatest(s.x1,s.x2) >= least(r.x,p.x) AND least(s.y1,s.y2) <= greatest(r.y,p.y) AND greatest(s.y1,s.y2) >= least(r.y,p.y) AND lseg(point(r.x,r.y),point(p.x,p.y)) ?# lseg(point(s.x1,s.y1),point(s.x2,s.y2)) ) UNION ALL SELECT r.x, r.y, p.x, p.y, p.dist, r.x1, r.y1, r.v, greatest( abs(p.x-r.x), abs(p.y-r.y) ) <= 1, r.k + 1 FROM schumacher r JOIN (SELECT * FROM gradient_cached UNION ALL SELECT * FROM overrun) p ON abs(p.x-r.x - (r.x-r.x0)) <= 1 AND abs(p.y-r.y - (r.y-r.y0)) <= 1 AND (r.k + 1 < 4 OR -- начиная с третьего хода - тормозим ( greatest( abs(p.x-r.x), abs(p.y-r.y) ) -- текущая скорость < greatest( abs(r.x-r.x0), abs(r.y-r.y0) ) -- предыдущая скорость ) ) WHERE NOT r.safe -- пока не остановились -- для ходов после первого наезда на другие машины не проверяем AND NOT EXISTS ( -- пересечения с сегментами (включая касания) SELECT NULL FROM segments_cached s WHERE least(s.x1,s.x2) <= greatest(r.x,p.x) AND greatest(s.x1,s.x2) >= least(r.x,p.x) AND least(s.y1,s.y2) <= greatest(r.y,p.y) AND greatest(s.y1,s.y2) >= least(r.y,p.y) AND lseg(point(r.x,r.y),point(p.x,p.y)) ?# lseg(point(s.x1,s.y1),point(s.x2,s.y2)) ) ) SELECT x1, y1 -- выбираем безопасный ход, который обещает лучший результат FROM schumacher WHERE safe ORDER by dist DESC, v DESC, random() LIMIT 1;
На сервере «Шумахер» обычно укладывался в полминуты. Оставшееся машинное время можно было бы применить с пользой: увеличить глубину поиска, не давать себя подрезать (не выбирать ходы с единственным продолжением) и, наоборот, стараться подрезать оппонентов и так далее.
Я специально прекратил заниматься запросом, как только он стал показывать более или менее приличные результаты, надеясь порадоваться за того, кто его обгонит. Увы, «Шумахер» занял бы верхнюю ступеньку пьедестала, если бы не выступал вне зачёта. Жаль, но у меня, конечно, было куда больше времени, чем у участников, чтобы спокойно подумать и попробовать разные варианты. Например, я начал с того, что построил осевую линию операцией эрозии, чтобы упростить поиск пути до финиша, хотя в итоге оказалось, что с задачей за разумное время справляется и обычный волновой алгоритм.
Кстати, если захотите попробовать силы, присылайте свой запрос, приоткроем доступ к приложению.
Пара слов о запросах участников
Большинство участников решили ограничиться локальной оптимизацией на основе эвристик. Среди таких решений были неплохие (Иван Максимов занял второе место, а Нам Хоай Ву — третье), но по баллам они проиграли лидеру в два раза. В чём причина? В развилках, конечно.
Вот пример показательного и довольно драматичного турнирного заезда. На четверти пути красная машина вылетает с трассы. Жёлтый болид мчится быстрее всех, к середине гонки становится понятно, что его уже не догнать… но эвристика заставляет гонщика ехать прямо — на штрафной круг. У синего гонщика другая эвристика, он сворачивает налево — и тоже уходит на штрафной круг, только в другую сторону. А вот гонщик на зелёном болиде (запрос Кристины Марченко, занявшей первое место) использует волновой алгоритм и чётко понимает, в какой стороне финиш.
Какие использовались эвристики? О, тут участники дали волю фантазии. Вот что я насчитал (по смыслу понятно, какие показатели надо максимизировать, а какие — минимизировать):
расстояние до финиша по прямой линии или по внешней границе полигона (очевидно, что свернуть «не туда» при этом очень легко);
расстояние, на которое удалось отъехать от своего начального положения;
на каком ходу получается финишировать, если получается;
расстояние от стен;
отклонение от текущего вектора скорости;
топтание на месте и повторение собственных ходов;
скорость (как правило, вводилось ограничение, чтобы не разгоняться слишком уж сильно);
на сколько ходов удалось проехать, не врезавшись;
количество уникальных состояний (то есть пространство для маневра).
Какие-то эвристики логичны (но, как мы видели, всё равно неэффективны), какие-то загадочны. Волновой алгоритм я обнаружил только у троих участников, при этом с кешированием — у двоих. Но лишь Кристина довела решение до рабочего состояния.
Но как же так — волновой алгоритм есть, кеширование есть, а не работает? А вот так. Больше нельзя взглянуть на код и сразу сообразить, стóящий запрос перед тобой или нет. Все неработающие запросы, ни разу не доехавшие до финиша, как один были «похожи на правду». Понятно, что все мы так или иначе используем ИИ, но увы, многие участники положились на него целиком и полностью.
Встретилось довольно много неэффективных фрагментов. Про «самодельную геометрию на векторных произведениях» я уже говорил (проще было взять штатные типы данных и функции). Кто-то обрабатывал кольца полигона по одному (достаточно было свалить все отрезки в одну кучу). Кто-то искал внешнее кольцо по максимальной площади (хотя по условию оно имеет первый номер). Раньше лень победила бы, заставила немного пораскинуть мозгами, чтобы не жать лишний раз на кнопки. А сейчас ИИ без проблем генерирует сотню строк туда, сотню строк сюда… Рекорд был — 1159 строк! Не надо так. Оставляйте голову включённой, это полезно.
Ещё удивило частое совмещение в одном запросе нескольких идей: и просмотр вперёд на несколько шагов, и отдельная проверка неповторения предыдущей позиции, и всякие дополнительные эвристики, и ещё fallback-стратегия — попытка двинуться хоть куда-нибудь, если не удалось найти нормальный ход. Едва ли не у половины участников был такой набор, а в одном запросе я встретил резервную fallback-стратегию на случай, если основная на сработает! Но зачем? Просто чтобы красиво вылететь с трассы? «Шумахер» в таких случаях говорит «штош» и ничего не возвращает.
Из ИИ-маркеров отметил для себя тотальное приведение типов, вроде такого:
AND ((r.x - r.x0)::bigint * (w.y1 - r.y0)::bigint - (r.y - r.y0)::bigint * (w.x1 - r.x0)::bigint) * ((r.x - r.x0)::bigint * (w.y2 - r.y0)::bigint - (r.y - r.y0)::bigint * (w.x2 - r.x0)::bigint) <= 0
Интересно, зачем?
Любопытная находка: в одном решении встретилось кеширование, но не с помощью записи в таблицу, а путём сохранения данных в конфигурационный параметр. Неожиданно, но да, оказывается так тоже можно было.
А приз судейских симпатий достаётся Егору Зуйкову, который запилил гонку с преследованием: его машина пристраивалась в хвост сопернику и пыталась повторять за ним все маневры. К сожалению, запрос слишком часто врезался в машины противников и не показал хороших результатов. Первое место так, конечно, не займёшь, но до приличных результатов можно было бы докрутить. В любом случае это оригинально, весело и написано собственной головой.
На этом прощаюсь. Получайте от SQL удовольствие!
