ICFP Contest 2010: день первый
Как широко известно в узких кругах в эти выходные прошел очередной ICFP Contest. Учитывая массу полученного фана и неплохие результаты нашей команды в 2008 году, турнира этого года ждал с нетерпением. К сожалению, коллега с которым мы гоняли марсоход в 2008-м, в последний момент сказал, что участвовать не сможет... Я понял, что придется рубиться в одиночку. Это, конечно, сильно повлияло на результат, т.к. задачка в этом году очень хорошо параллелилась на 3-4 человек. В итоге оказался на 45-месте.
Ну теперь о том как это было.
16:00 по местному времени, очередное нажатие F5 в браузере и вот оно задание!
Перечитывал несколько раз, ибо задание сходу показалось больно навороченным. Организаторы предложили нам поучаствовать в рынке производства автомобилей и топлива к ним. Прилагалось описание автомобиля, вернее его "двигателя" (engine), топлива (fuel) и описание, как определить подходит топливо к конкретному автомобилю или нет. Очки давались за создание топлива к как можно большему числу автомобилей, при этом чем раньше создашь топливо, тем больше успеешь заработать денег/очков. Это меня подрасстроило, т.к. команды с бОльшим количеством народа скорее всего начнут выдавать результаты раньше. Ну да ладно.
Кроме топлива можно было генерить и сабмитить машины. Непосредственно за них очков не давали, зато если придумать машину, к которой только ты сможешь создать топливо, то получишь много очков за такое топливо.
Как сказали организаторы, это не был бы ICFP contest, если бы всё было так просто.
Способ кодирования машин задан не был. Позже обещали выложить несколько тестовых машин. А с топливом вообще была засада. Напрямую сабмитить его было нельзя, а надо было создать фабрику, которая его производит. Ни описания формата топлива, ни формата фабрики конечно же не давали. Сказали лишь, что фабрика состоит из гейтов, у каждого два входа и два выхода, соединение только один к одному, у всей схемы один вход и один выход -- внешние, на них поступают и снимаются данные, и также дали пример некой тестовой фабрики и ее вход. Выглядела она вот так:
19L:
12R13R0#1R12R,
14R0L0#4R9L,
9R10R0#3L8L,
2L17R0#5L9R,
15R1L0#10R13R,
3L18R0#6L15L,
5L11R0#13L12L,
19R16R0#11R8R,
2R7R0#11L10L,
1R3R0#18L2L,
8R4L0#16L2R,
8L7L0#15R6R,
6R0R0#14L0L,
6L4R0#14R0R,
12L13L0#17L1L,
5R11L0#16R4L,
10L15L0#17R7R,
14L16L0#18R3R,
9L17L0#19R5R,
X18L0#X7L:
19L
вход: [0,2,2,2,2,2,2,0,2,1,0,1,1,0,0,1,1]
Да, топливо и машины кодируются последовательностями цифр троичной системы (тритов).
Ну осознав наконец задание, приступил к делу. Решил начать с фабрик, т.к. без них нету топлива, а без топлива не создать машину. Очевидно, что каждая строчка фабрики - это описание гейта. До символа # входы, после выходы. Дальше надо было построить функцию одного гейта. Я очень надеялся, что гейт не имеет памяти, и действовал исходя из этого предположения. Поэкспериментировал с простыми схемами из одного гейта (всего 4 варианта соединения) и получил 4 выхода (что поступает на вход было неизвестно). Теперь у меня были известные последовательности, которые можно было послать на вход другому гейту и попытаться построить табличную функцию гейта. Составляя разные схемки достаточно быстро за часик получил заветную функцию:
0 0 -> 0 2
0 1 -> 2 2
0 2 -> 1 2
1 0 -> 1 2
1 1 -> 0 0
1 2 -> 2 1
2 0 -> 2 2
2 1 -> 1 1
2 2 -> 0 0
Дальше достаточно просто немного побектрейсов можно было выяснить, что же подавалось на вход. Оказалось, что это последовательность 01202101210201202. Последние пять тритов давали надежду на то, что она циклическая. Кстати пока пробовал разные схемки обратил внимание, что вроде бы две одинаковые схемы из двух гейтов, но с разной нумерацией гейтов, дают отличие в первом трите. Что это? Бага? Неее. Отложил в подсознание, что вероятно порядок указания гейтов в схеме важен. Пошел писать читалку и эмулятор фабрики. На удивление быстро написал рекурсивный проход по гейтам и даже без багов. Простые схемки работали на ура, но вот тестовая 19-гейтовая выдавала результат отличный от серверного. Тут я достал из подсознания мысль о том, что порядок гейтов важен, и попробовал те две схемки, которые должны давать разные результаты. У меня они, естественно, давали результат одинаковый. Не совпадала та, у которой гейты шли в обратном порядке, т.е. вход шел на 1-й гейт, а выход снимался с нулевого. Стало очевидно, что обратные дуги -- это те, которые идут к гейтам с меньшим номером (ну или к самим себе конечно). Быстро переделал рекурсию на обычный проход с 0-го до пследнего гейта и... О чудо! выход большой фабрики совпал с сервером!
Едем дальше.
Для сабмита топлива на сервер было необходимо добавить к нему 17-тритовый префикс, который был не известен, но предполагалось, что фабрика из задания будучи накормленой тестовым входом из задания выдаст искомый префикс. Быстро прогнав их через симулятор получил: 11021210112101221
Правильный ли это префикс было не понятно. Нужно было научиться его генерить, чтобы убедиться, что сервер его принимает.
Взял много бумаги и карандаш и стал медитировать над таблицей, гейтами, и тестовой схемой, пытаясь понять, как она работает.
Достаточно очевидно, что табличная функция - это:
L(l,r) = l-r
R(l,r) = l*r-1
Пытался составлять и упрощать формулы для простейших комбинаций блоков, но как-то ничего интересного не выходило.
Глядя на тестовую схему из задания обратил внимание, что внешний вход поступает на левый вход блока, с которого же слева и снимается выход. Т.к. левый вход (Li) и левый выход (Lo) имеют обратимое пребразование, зная вход и выход системы, можно было однозначно установить каким должен быть правый вход и каким будет правый выход. Это хорошо, но этот факт мне никак не помогал, ибо задача сводилась к такой же. Т.е. надо было опять получить некий выход, имея некий вход. Хотя учитывая, что можно одну из этих дуг сделать обратной, возможно, можно было двигать задачу в сторону упрощения. Но было уже как-то совсем поздно и голова отказывалась варить. Понимал, что сижу туплю и решил пойти спать...
Продолжение
Ну теперь о том как это было.
16:00 по местному времени, очередное нажатие F5 в браузере и вот оно задание!
Перечитывал несколько раз, ибо задание сходу показалось больно навороченным. Организаторы предложили нам поучаствовать в рынке производства автомобилей и топлива к ним. Прилагалось описание автомобиля, вернее его "двигателя" (engine), топлива (fuel) и описание, как определить подходит топливо к конкретному автомобилю или нет. Очки давались за создание топлива к как можно большему числу автомобилей, при этом чем раньше создашь топливо, тем больше успеешь заработать денег/очков. Это меня подрасстроило, т.к. команды с бОльшим количеством народа скорее всего начнут выдавать результаты раньше. Ну да ладно.
Кроме топлива можно было генерить и сабмитить машины. Непосредственно за них очков не давали, зато если придумать машину, к которой только ты сможешь создать топливо, то получишь много очков за такое топливо.
Как сказали организаторы, это не был бы ICFP contest, если бы всё было так просто.
Способ кодирования машин задан не был. Позже обещали выложить несколько тестовых машин. А с топливом вообще была засада. Напрямую сабмитить его было нельзя, а надо было создать фабрику, которая его производит. Ни описания формата топлива, ни формата фабрики конечно же не давали. Сказали лишь, что фабрика состоит из гейтов, у каждого два входа и два выхода, соединение только один к одному, у всей схемы один вход и один выход -- внешние, на них поступают и снимаются данные, и также дали пример некой тестовой фабрики и ее вход. Выглядела она вот так:
19L:
12R13R0#1R12R,
14R0L0#4R9L,
9R10R0#3L8L,
2L17R0#5L9R,
15R1L0#10R13R,
3L18R0#6L15L,
5L11R0#13L12L,
19R16R0#11R8R,
2R7R0#11L10L,
1R3R0#18L2L,
8R4L0#16L2R,
8L7L0#15R6R,
6R0R0#14L0L,
6L4R0#14R0R,
12L13L0#17L1L,
5R11L0#16R4L,
10L15L0#17R7R,
14L16L0#18R3R,
9L17L0#19R5R,
X18L0#X7L:
19L
вход: [0,2,2,2,2,2,2,0,2,1,0,1,1,0,0,1,1]
Да, топливо и машины кодируются последовательностями цифр троичной системы (тритов).
Ну осознав наконец задание, приступил к делу. Решил начать с фабрик, т.к. без них нету топлива, а без топлива не создать машину. Очевидно, что каждая строчка фабрики - это описание гейта. До символа # входы, после выходы. Дальше надо было построить функцию одного гейта. Я очень надеялся, что гейт не имеет памяти, и действовал исходя из этого предположения. Поэкспериментировал с простыми схемами из одного гейта (всего 4 варианта соединения) и получил 4 выхода (что поступает на вход было неизвестно). Теперь у меня были известные последовательности, которые можно было послать на вход другому гейту и попытаться построить табличную функцию гейта. Составляя разные схемки достаточно быстро за часик получил заветную функцию:
0 0 -> 0 2
0 1 -> 2 2
0 2 -> 1 2
1 0 -> 1 2
1 1 -> 0 0
1 2 -> 2 1
2 0 -> 2 2
2 1 -> 1 1
2 2 -> 0 0
Дальше достаточно просто немного побектрейсов можно было выяснить, что же подавалось на вход. Оказалось, что это последовательность 01202101210201202. Последние пять тритов давали надежду на то, что она циклическая. Кстати пока пробовал разные схемки обратил внимание, что вроде бы две одинаковые схемы из двух гейтов, но с разной нумерацией гейтов, дают отличие в первом трите. Что это? Бага? Неее. Отложил в подсознание, что вероятно порядок указания гейтов в схеме важен. Пошел писать читалку и эмулятор фабрики. На удивление быстро написал рекурсивный проход по гейтам и даже без багов. Простые схемки работали на ура, но вот тестовая 19-гейтовая выдавала результат отличный от серверного. Тут я достал из подсознания мысль о том, что порядок гейтов важен, и попробовал те две схемки, которые должны давать разные результаты. У меня они, естественно, давали результат одинаковый. Не совпадала та, у которой гейты шли в обратном порядке, т.е. вход шел на 1-й гейт, а выход снимался с нулевого. Стало очевидно, что обратные дуги -- это те, которые идут к гейтам с меньшим номером (ну или к самим себе конечно). Быстро переделал рекурсию на обычный проход с 0-го до пследнего гейта и... О чудо! выход большой фабрики совпал с сервером!
Едем дальше.
Для сабмита топлива на сервер было необходимо добавить к нему 17-тритовый префикс, который был не известен, но предполагалось, что фабрика из задания будучи накормленой тестовым входом из задания выдаст искомый префикс. Быстро прогнав их через симулятор получил: 11021210112101221
Правильный ли это префикс было не понятно. Нужно было научиться его генерить, чтобы убедиться, что сервер его принимает.
Взял много бумаги и карандаш и стал медитировать над таблицей, гейтами, и тестовой схемой, пытаясь понять, как она работает.
Достаточно очевидно, что табличная функция - это:
L(l,r) = l-r
R(l,r) = l*r-1
Пытался составлять и упрощать формулы для простейших комбинаций блоков, но как-то ничего интересного не выходило.
Глядя на тестовую схему из задания обратил внимание, что внешний вход поступает на левый вход блока, с которого же слева и снимается выход. Т.к. левый вход (Li) и левый выход (Lo) имеют обратимое пребразование, зная вход и выход системы, можно было однозначно установить каким должен быть правый вход и каким будет правый выход. Это хорошо, но этот факт мне никак не помогал, ибо задача сводилась к такой же. Т.е. надо было опять получить некий выход, имея некий вход. Хотя учитывая, что можно одну из этих дуг сделать обратной, возможно, можно было двигать задачу в сторону упрощения. Но было уже как-то совсем поздно и голова отказывалась варить. Понимал, что сижу туплю и решил пойти спать...
Продолжение