ICFPC-2010 howto step-by-step by hack-the-loop team

Что за команда и какие результаты читаем тут: http://xoposhiy.livejournal.com/106201.html

Краткая постановка задачи.
Каждая команда может послать на сервер по 72 машинки. Машинки видны всем. Все могут пытаться делать топливо для чужих машинок. За каждое подошедшее топливо капают баллы.

Фишка в том, что про машинку известно только лишь то, что это структурка
List<Tuple<bool, List<int>, List<int>>> 
(с некоторыми дополнительными ограничениями), и что записывается она как-то в виде строки из 0, 1 и 2. Как именно  — не известно! :)
Ещё дан пример корректной машинки:

221022000022010112201010022001122011110220010

Можете попробовать минут 5 погадать, как из этого сделать List<Tuple<bool, List<int>, List<int>>> . У меня на это ушла вся ночь с субботы на воскресенье, плюс у меня была возможность тестировать свои версии машинок на сервере, плюс у меня была подсказка помощь зала. :-)

Топливо для машинки - это список матриц натуральных чисел. Он тоже как-то кодируется с помощью 0 1 2. Как - тоже не известно! И даже примера нет! :-о

Более того посылать на сервер нужно не топливо, а фабрику его производящую. Фабрика - это сеть с одним входом и одним выходом, состоящая из гейтов с двумя входами и двумя выходами. Гейты упорядочены. Дуги, соединяющие гейты от младшего к старшему передают сигнал мгновенно. Дуги в обратную сторону дают задержку в один такт. Фабрике на вход подается какая-то строка из 0 1 2, а на выходе должен быть секретный префикс, за которым следует описание топлива.

Так вот. Как кодировать фабрику, по какому принципу работают гейты, что подается на вход сети и какой секретный префикс — не известно! =:-O

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



Теперь к самому интересному. Что надо было делать, чтобы набрать много-много баллов?
По порядку:

1. Разобраться с кодированием фабрик. Это тривиально, но мы тупили около часа.

2. Как-то догадаться до принципа работы гейта. На это у нас ушло в общей сложности часов 7. За это время мы вручную построили 18 специальных фабрик, которые при запуске на сервере дали нам данные для двух заветных табличек. Это было тяжко, но мы справились. Некоторые команды как-то автоматизировали этот процесс брутфорсиком. Ну, молодцы. :)

3. Реализовать выполнятор фабрик. Когда известно, как работает гейт — дело техники.

4. Найти секретный ключевой префикс, с которого должно начинаться любое топливо.

5. Вычислить строку, которая подается сервером на вход фабрике. Я это делал брутфорсиком, а потом ещё одним перебором с участием сервера. Впрочем в зависимости от реализации п.5, этот пункт может быть лишним. :)

6. Придумать (2 часа), реализовать (ещё полтора часа) и отладить (ещё почти час) алгоритм построения фабрики для любого заданного бензина. Мы собирали фабрику из последовательных блоков. Один блок имеет один вход и один выход и обладает такими двумя свойствами: (1) на первом ходе выдает фиксированное заданное число, при условии, что на вход придет 0 (в входом будет обратная дуга, так что придет первым всегда 0); (2) выводом на (i+1)-ом ходе этого блока можно управлять подавая нужные сигналы на вход на i-ом шаге.

Всего таких блоков было три вида:

0L:
X0R0#X0R:
0L

1L:
0L1R0#0L1R,
X0R0#X0R:
1L

2L:
0L2R0#0L1R,
1R0R0#2R1L,
X1L0#X0R:
2L

Размер фабрики получался O(длина_топлива).
В целом все это базируется на динпрожике, который определяет, из каких блоков строить фабрику, и на хитром алгоритме стыковки входов и выходов этих блоков. Последний доставил нам особенно много радости при отладке.

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

7. Закоммитить, наконец, топливо для нулевой машинки! Мы это сделали лишь через 27 часов после начала контеста.

8. Разобраться в синтаксисе Ternary Streams. На это у нас ушло охрененно много времени и без подсказки (см выше) я, может быть и не справился бы. Короче, спасибо донору.

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

10. Начать отправлять для всех машинок разные простые виды топлива. Так решалось около трети всех машинок. После этого вы уже довольно круты.

11. Написать валидатор, который проверяет подходит ли топливо к машинке без сабмита топлива на сервер. Можно прикрутить его к п.10, чтобы откровенную лажу даже не пытаться отправлять. Осознать, что внутри валидатор будет оперировать большими числами и прикрутить длинную арифметику. Этого мы так и не сделали до конца контеста. В результате на выходе нашего валидатора на самом деле было три значения: "подходит", "не подходит" и "не знаю". :)

12. Придумать алгоритм подбора топлива к машинке и начать массово подбирать топлива к еще нерешенным машинкам. Мой тупой брутфорсик давал результаты не лучше, чем алгоритм из п.10. Придумывать и писать что-то умнее уже не было ни времени, ни силы духа.

13. Где-то параллельно с этим всем, придумать генератор хоть сколько нибудь нетривиальных машинок и засабмитить, наконец, свои 72 машинки. Мы это сделали лишь за 3 часа до конца. Да и то, наши машинки были довольно тривиальными. По хорошему надо было их сабмитить хотя бы за сутки до конца, но мы надеялись придумать нетривиальные схемы машинок.

14. Параллельно с этим можно было искать на code.google.com, github.org и в других подобных местах репозитории других команд и зырить! Назыренное методично отправлять на сервер в качестве решений. Можно даже часть этой работы автоматизировать. И даже не говорите мне, что я читер! :-D

Следуя (даже не очень строго) этому алгоритму можно было набрать более 1000 баллов. Проверено! :)