Dmitry Astapov (_adept_) wrote,
Dmitry Astapov
_adept_

Categories:

ICFPC-2016: день второй

(предыдущая часть, следующая часть)

Первый день у меня закончился тем, что я пробовал сделать модель "бумаги", которую можно будет "гнуть", и потом извлекать из нее результаты сгибания в виде, пригодном для отправки на сервер в качестве решения.

Так как решение состоит из точек (заданных координатами на начальном листике), полигонов (заданых порядковыми номерами точек) и финальной формы оригами (заданной конечными координатами точек), то я подумал, что моя модель бумаги будет состоять из:
  • текущего положения точек (список координат)
  • полигонов (заданых списками номеров точек)
  • какой-то истории сгибов

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

Наутро второго дня (в 10:00) я перечитал написаный код и понял, что дела не будет. Во-первых, полигоны в виде списка точек неудобны, так как постоянно нужна "предыдущая точка" или "следующая точка". То есть, удобнее будет задавать полигоны отрезками.

Во-вторых, интерфейс для сгибов, который требует задавать конечные координаты точки, тоже неудобный, так как зачастую эти координаты неизвестны и как их посчитать - неясно. Гораздно удобнее интерфейс "перегнуть через линию, заданную двумя точками"

В-третьих, моя реализация имела ошибку, и уверенно работала только в том случае, если в результате сгиба поворачивался только один "уголок" бумаги с одной вершиной.

В-четвертых, я так и не придумал, как хранить историю сгибов, и как "разгибать" бумагу назад, чтобы получить решение.

В-пятых, баг из пункта "в-третьих" был найден совершенно случайно и непреднамеренно, и я понял, что мне нужна какая-то визуализация процесса.

В общем и целом выходило так, что моя "бумага" ни на что не годилась.


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

К 12:00 я понял, что нужно расставить приоритеты. Я выкачал новую порцию задачек, сгенерировал для них картинки, сделал сводную статистику моих решений и их успешности и сел вместе с женой над ними медитировать. Выводов намечалось два: нужно делать свои задачи, они дают очки (и много). Но одними задачами выехать не получится - ты можешь размещать не более одной задачи в час, всего 46 штук. А твои конкуренты, которых 100-200 команд, могут за это время разместить до 8000 задач. То есть, все-таки нужен решатель. Более умный, чем "накрываем листиком, подворачиваем края".

Второй вывод заключался в том, что за ночь некоторые команды запостили уже по 8-9 задач. У некоторых это был просто квадрат (0,0),(0,1),(1,1),(1,0) (ура!). У некоторых это было что-то позаковыристее, но все время одно и то же. Прелесть в том, что сервер считал некий хэш от описания задачи, и повторяющиеся задачи можно было легко найти.

Первым делом жена сделала мне вручную описание задачки-"змеи". Вот она:


Я "запланировал" эту задачу на ближайшие 8 часов (можно было отсылать задачи заранее, указывая время их публикации), и стал думать, где бы взять еще задач, чтобы они были неодинаковые. Из разглядывания картинок было видно, что часть задач - это одно и то же оригами, повернутое под разными углами.

"Надо повернуть змею", - подумал я (т.к. идей для моей модели "бумаги" у меня по-прежнему не было). Матрица преобразования "поворот вокруг произвольной точки" в гомогенных координатах нашлась довольно быстро, но вот беда - там (кто бы мог подумать!) фигурировали синус и косинус угла поворота. А у нас-то все координаты - это дроби. А синусы и косинусы - они же вещественнозначные.

Тут на меня нашло какое-то затмение и я почему-то подумал, что надо найти реализацию синуса-косинуса через, например, continued fractions, и все замечательно получится. Такая библиотека была найдена, но (как можно было бы и догадаться) чуда не произошло. "Polygon #0 is not mapped congruently", все в сад, повторять школьную математику. Можно было бы взять значение синуса равным какому-то произвольному числу, и вычислить, какое при этом будет значение косинуса, но там же \sqrt{1-cos^2{\alpha}}, а корень квадратный у нас - что? Правильно, такая же фигня, как и с синусом и косинусом.

Идея перебрать натуральные дроби из какого-то диапазона, удовлетворяющие a^2+b^2=c^2, и положить синус равным a/c, а косинус - b/c мне тогда в голову не пришла. В результате змея так и осталась неповернутой.

На неравный бой с тригонометрией у меня ушел битый час. Потом я еще какое-то время почитал всякие статьи, некоторые из них были довольно любопытными. В частности, из "Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami" я узнал, что можно сложить оригами в виде любого плоского многогранника - хоть и невыпуклого, хоть бы и с дырками. Доказательство было конструктивным, но вот беда - подразумевало неограниченное количество бумаги. Кому лень читать статью - идея была в том, чтобы сложить узкую полоску, а потом "змейкой" замостить полигон, и напоследок завернуть под него выступающие части "змейки". Даже если бы я и умудрился сложить из квадрата очень узкую и очень длинную полоску, у меня было всего 5000 байт на решение, а такое количество точек и ребер туда бы не влезло.

В процессе всего этого я периодически вяло выкачивал новые задания и решал их, постепенно сползая к 30-му месту.

Тут жена сказала, что я всегда говорил о том, что во время ICFPC полезно гулять. С собой не поспоришь :) И мы пошли гулять. В процессе гуляния я плакался на тяжелую жизнь и отсутствие модели "бумаги" и тут я понял, что, во-первых, надо представлять полигоны отрезками, а не точками. А во-вторых, вовсе необязательно запоминать, как именно я согнул бумагу и потом "разгибать" ее обратно.

Достаточно для каждой точки хранить и ее координаты на оригинальном листе, и координаты ее положения в текущем состоянии оригами. Тогда при любом складывании или перемещении будут изменяться только ее текущие координаты. А все новые точки в оригами получаются только при сгибании, когда отрезки между существующими точками делятся на две части. При этом все отрезки перемещаются и поворачиваются, но не растягиваются и не сжимаются.

А это значит, что, например, если мы делим некий отрезок AB новой точкой C пополам, то текущие координаты C можно просто посчитать, а координаты C на оригинальном листе можно узнать, разделив пополам отрезок между оригинальными точками AB. Аналогичным образом все работает для деления отрезков в любой другой пропорции.

С этой новой идеей я за время где-то с 17:00 до 22:00 написал новую модель бумаги и процедуру ее сгибания вдоль произвольной линии, заданной двумя точками A и B. При этом линия считалась идущей из A в B, и все, что лежало справа от нее, перегибалось налево. Кроме того я реализовал "отладочный вывод", заключавшийся в том, что после каждого сгибания модель бумаги сохраняла на диск .png с изображением "разогнутого" и текущего состояний. Мой ocaml был собран без graphics, интерфейс cairo2 был большим и мне незнакомым, поэтому я нашел векторыне библиотеки Vg и Gg и использовал их (потеряв, наверное, на этом сколько-то времени). Зато -- и это оказался большой плюс -- Vg/Gg позволяли рисовать в произвольных координатах и сами транслировали нарисованное в рамки картинки.

Естественно, ничего не заработало с первого раза. Линии, пересекающие полигоны точно в вершине, или сопадающие с одной из сторон, или параллельные осям координат все потребовали каких-то тестов и фиксов.

Только к часу ночи я написал программу, которая читала из файла список отрезков, последовательно сгибала бумагу по каждому из них, и записывала получившееся решение в файл. В четыре руки с женой мы сделали несколько задач "посложнее" (как мне тогда казалось) и отправились спать.

Хронология второго дня выглядит так (время в часах от начала ICFPC):


(предыдущая часть, следующая часть)
Tags: icfpc
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments