?

Log in

No account? Create an account
dump -0f - /dev/mind
Я знаю Haskell, OCaml, GSM, эндофункторы и много других страшных слов
ICFPC-2016: день второй 
9th-Aug-2016 10:16 pm
(предыдущая часть, следующая часть)

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

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

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

Наутро второго дня (в 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):


(предыдущая часть, следующая часть)
Comments 
10th-Aug-2016 10:18 am (UTC)
> А все новые точки в оригами получаются только при сгибании, когда отрезки между существующими точками делятся на две части.

О, б-блин...
10th-Aug-2016 02:49 pm (UTC)
Вот да, у меня чтение чужих отчетов тоже было полно чудных открытий :)
This page was loaded Aug 21st 2017, 9:37 pm GMT.