Как мы в ICFP Programming Contest 2021 участвовали

Небольшое intro

ICFP Programming Contest - это ежегодный контест, который проходит в предверии международной конференции по функциональному программированию. Контест проходит три дня, в течении которых предлагается решить задачу.

Задача

В этом году предлагалось решить следующую задачу: на вход приходят координаты вершин некой фигуры и список ребер в виде указания идентификаторов точек, которые ребро соединяет. Координаты точек всегда целочисленные. Также на вход передаются координаты дыры и ε, задающая на сколько можно сжимать или растягивать ребро. Требуется путём перемещения точек впихнуть фигуру в дырку, при этом расстояние от вершин дыры до вершин фигуры должно быть как можно меньше. Задача вдохновлена японскими шоу.

В этом году предлагалось решить следующую задачу: на вход приходят координаты вершин некой фигуры и список ребер в виде указания идентификаторов точек, которые ребро соединяет. Координаты точек всегда целочисленные. Также на вход передаются координаты дыры и ε, задающая на сколько можно сжимать или растягивать ребро. Требуется путём перемещения точек впихнуть фигуру в дырку, при этом расстояние от вершин дыры до вершин фигуры должно быть как можно меньше. Задача вдохновлена японскими шоу.

Как решали

Использовали язык C++ и для отображения gnuplot. Gravechapa занимался визуализацией, я солвером.

В качестве алгоритма был выбран алгоритм имитации отжига. Солвер пытался двигать вершины и минимизировать функцию оценки. Основная проблема, с которой столкнулись: перемещения одной вершины недостачно, фигуру нужно ещë складывать и вращать, что сделать уже не успели.

Как итог 133 место. Исходный код можно посмотреть тут: https://github.com/Gravechapa/icfp2021