icfp programming contest 2010

[jsn]

Сыграли с brohm-ом в ICFP Programming Contest, как обычно. Команда наша называлась nbu. brohm первые сутки участвовал не в полную силу, так как был занят другими делами; начиная со вторых пилили уже полноценно вдвоём. Ни с кем не советовались, на irc отсутствовали, etc. Описание задачи здесь, традиционное описание и отчёт от _adept_ здесь, их команда называлась Futamura Rejection.

день 1

2 часа : ТЗ прочитано, написана первая пустая фабрика
4 часа : сгенерены все фабрики размера 1 и 2, получен их выход
6 часов: солвер для функций гейтов, и, как результат, таблицы функций
8 часов: парсер фабрик
10 часов: интерпретатор фабрик
11 часов: реальный input sequence
22 часа : сгенерён ключ, первый score
24 часа : сгенерено первое горючее, score пошёл в рост

день 2

6 часов: webcrawler для вытаскивания чужих машин
14 часов: формат тернарных чисел, частично остальные тернарные форматы

день 3

1 час : горючее для 2 .. 6-баковых машин, score снова пошёл расти
7 часов: полный парсер для тернарного формата машин
10 часов: полный парсер для тернарного формата горючего
11 часов: быстрый интерпретатор фабрик на C
14 часов: быстрый брут-форсер для фабрик
16 часов: сериалайзер машин и топлив в тернарный формат
18 часов: нагенерённые топлива поставлены в очередь автосабмиттера
21 час : генератор пар машина-топливо, первые десятки машин ушли на сервер

результаты: 40-е место

score:	506.417
others' cars solved:	954
cars submitted:	72

Languages: Ruby, Perl, C; VCS: git.

Comments

[cherry-merry.livejournal.com]

ничего не поняла. :-)
Ты результатом доволен? (судя по описанию процесс был захватывающим)
А сколько всего мест?

[jsn.livejournal.com]

Скорее доволен, чем нет. Процесс тоже был неплох, да. Ну всего команд зарегистрировано там было больше 800.

[bish0nen.livejournal.com]

Совершенно предсказуемая реакция, прошу заметить! Вот если б писали на Хаскелле...

[b-a-t.livejournal.com]

Ты мой герой!

[jsn.livejournal.com]

:)

[brohm.livejournal.com]

А я?!

[b-a-t.livejournal.com]

И ты тоже, конечно!

[tarseny.livejournal.com]

И какие результаты по брутфорсу фабрик? Сколько разрядов можно приписать к префиксу, насколько долго работает?

[jsn.livejournal.com]

То, что использовалось в последний день, ничего особенного из себя не представляло -- форсило 100-символьные горючие за минуту на C, кажется. У нас не было реальной проблемы с длиной к этому моменту, так что мы не морочились.

Разумеется, на следующий день после окончания я от нечего делать написал на ruby билдер фабрик, который легко генерит фабрики для килобайтных горючих за несколько минут, на C это будут единицы секунд (после драки-то святое дело кулаками помахать).

[tarseny.livejournal.com]

Мы до сих пор кулаками помахиваем. А какой принцип перебора? Мы шестигейтную схему для префикса подобрали, а семигейтные наш брутфорс уже не брал категорически.

[jsn.livejournal.com]

Последний вариант не брутфорсит, строго говоря -- там довольно детерминистичный процесс. Элементарные фабрики: http://pastie.org/1037128. Легко видеть, что фабрики 0-any, 1-any и 2-any на выходе на первом шаге дают 0, 1 или 2 соответственно, а на каждом следующем их выход однозначно определяется входом. Из этих фабрик легко строить цепочки.

Соответственно, чтобы построить фабрику, генерирующую произвольный выход длиной N, достаточно 1) взять фабрику из этих трёх, генерирующую на первом шаге первый символ из N, 2) найти вход длиной N-1 для этой фабрики, такой, что на выходе будут правильные N-1 следующих символов, и 3) повторить шаги 1-3 для этой новой последовательности длиной N-1.

[tarseny.livejournal.com]

Про построение такое цепочки уже читал в отчётах. Спасибо за ответ! ;)