dastapov: (new)
[personal profile] dastapov
Предыдущие части : день первый, день второй.

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

На третий день количество написанного кода превысило критический порог и наконец-то ПОПЁРЛО.

К 12:00 я сделал вычисление выпуклой оболочки (convex hull) и стал писать солвер, который заворачивает любое оригами как подарок -- кладет сверху лист бумаги и подгибает все края по граням выпуклой оболочки, пока бумага не перестанет торчать за пределы нужного контура.

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

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

Где-то в 13:00 я начал первые пробные запуски нового солвера, и на удивление он почти сразу же заработал. Единственной найденной проблемой было то, что я сдвигал оригами к (0,0), потом оборачивал вокруг него бумагу, а потом двигал результат обратно в то место, где он должен быть по условию задачи. И вот это последнее движение могло превратить все мои координаты в ужасные громадные дроби, что приводило к превышению лимита в 5000 байт.

К 14:00 я закончил допиливать скрипты для проверки решений, и поставил решение задач и их отправку на поток, а сам принялся разглядывать неидеально решенные задачи.

С ключом -debug солвер мог сохранять на диск картинки до и после каждого сгибания. Вот как это выглядит (линии тонкие, рекомендую фуллскрин):


Очень быстро я понял, что в отдельные моменты хочется сказать "да где ты загибаешь! Ты не вот там загибай, ты вот тут загибай!". К этому моменту (15:30) жена прошерстила статистику по имеющимся задачам и моим решениям, и сказала мне, что есть довольно много задач, которые по сути являются выпуклой оболочкой, которую потом перегнули еще раз или два. И если бы мой солвер мог сделать еще и это ...

Как именно вычислить такие задачи и сделать дополнительный шаг или два я в тот момент сообразить не мог. Зато я вспомнил ICFPC 2007, на котором jabber.ru решил все задачи вручную (написав для этого подходящие инструменты).

К 16:00 я залили все решения, которые только мог произвести и скакнул с 52 места на 20-е. Дальше имеющийся солвер меня поднять не мог.

И я стал писать интерактивный солвер на базе имеющегося у меня кода. Тут я впервые пожалел о том, что выбранный мной подход к визуализации позволяет мне только сохранять .png. Поколебавшись между "переписать все с нуля" и "оставить как есть и что-то придумать" я решил оставить все, как есть.
В результате интерактивная решалка после каждого шага сохраняла /tmp/interactive.png, а я запускал программу для просмотра картинок, которая раз в пол-секунды ее перерисовывала.

На картинке я рисовал исходный лист бумаги и точки "скелета" на нем, а рядом - текущий вид оригами и, опять-таки, точки скелета. Управлялся процесс интерактивной сборки через простой командный интерфейс. Программа имела/умела:
  • ввод через readline с историей и поиском
  • неограниченное undo (undo)
  • сгибание через произвольные координаты (fc x,y x2,y2)
  • сгибание через линию, проходящую через а произвольные точки (fp точка1 точка2)
  • смещение бумаги на произвольный вектор (mv dx,dy)
  • совмещение точек на оригами и скелете (mp paper_point skeleton_point)
  • показать координаты точек скелета (skeleton)
  • показать размер решения (size)
  • и самая киллер-фича: многократно сгибать бумагу по двум указанным линиям, пока есть, что сгибать. В результате она свернется в полоску, края которой совпадают с этими линиями (strip line1_point1 line1_point2 line2_point1 line2_point2)

Последняя команда была добавлена из-за того, что было очень много задач вида "полоска, согнутая 1-3 раза".

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

Вот как это выглядит:


С 19:00 до 21:00 я допиливал фичи в интерактивный решатель, делал новые задачи и вручную решал имеющиеся. Жена постоянно подбрасывала мне информацию о том, какие задачки выглядят решаемыми (глядя в статистику и картинки). Первым делом я старался решать задачи, которые присутствовали в N копиях, чтобы получить побольше очков.

Очень скоро стали понятны ограничения моего кода. Самым серьезным оказалось то, что сгиб по линии сгибал всё оригами целиком, тогда как для некоторых задач надо было согнуть только его часть. Кроме того, я не мог сделать нетривиальные сгибы с вытаскиванием или засовыванием углов (тот самый inside reverse fold, который я разглядывал в первый день).

Но даже и без этого я быстро поднялся с 20-го на 19-е место, преодолев довольно существенный (в несколько тысяч очков) разрыв. Дальше таблицу чемпионов заморозили (за 5 часов до окончания), и я не в курсе, насколько далеко нам удалось продвинуться дальше.

Жена решила мне вручную какое-то невообразимое количество задач (что-то около 30), которые были моему коду не по зубам.

Где-то к 22:00 я написал код, который вытягивал из snapshot-а информацию о задачах, которые идеально решило меньше трех человек. Я просматривал их картинки и пытался решить их вручную, и решил что-то около десятка.

Две задачи требовали ручного сдвига бумаги "на чуть-чуть", я пытался высчитать правильное значение, но не смог, и в результате решил их с resemblance=0.99999999999. Обидно :)

Остаток времени ушел на то, чтобы еще раз прогнать солвер по всем задачам, убедиться, что все решения отправлены, еще раз посчитать статистику и решить максимальное количество задач вручную. Последнюю задачу я решил за 15 секунд до конца и отправить уже не успел :)

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


Исходники (там вместе с задачками, картинками и всеми снепшотами, около 100М):
https://bitbucket.org/dastapov/icfpc2016/

Статистика:
  • Идеально решенных задач: 1120
  • С подобием от 0.5 до 1.0: 2125
  • С подобием меньше 0.5: 236

По своим задачам точную статистику я не вел, но помню, что были какие-то, решенные всего 2-3 участниками.

Надеюсь, что с 19-го я поднимусь хотя быть на 18-е место :)

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

Выводы:
  • Жена, увлекавшаяся оригами - страшная сила
  • Без команды вполне себе ничего
  • Гулять - хорошо :)
  • Если что-то приуныл - пиши скрипты, разглядывай картинки, что-то делай. Мысль придет
  • После ежедневного ocaml на работе я даже и не думал писать на haskell -- уже не ориентируюсь в современных библиотеках, а тратить время на разбирательство неохота.
  • Это, конечно, не 2006 год, но тоже неплохо.


EOF

(первая часть, вторая часть)
From:
Anonymous
OpenID
Identity URL: 
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

dastapov: (Default)
Dmitry Astapov

July 2017

M T W T F S S
     12
3456789
1011 1213141516
17181920212223
24252627282930
31      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags