?

Log in

 
 
26 July 2010 @ 07:22 pm
ICFPC 2010 - кулаками после боя  

Прошло больше месяца после очередного ICFPC. Страсти улеглись, мозги отдохнули, разбор полетов проведен. (отчет от Sanny находится здесь). На этот раз мы - тридцатые, что по-своему неплохо.
Задание этого года оказалось сложным и весьма многоплановым. Пришлось возиться и с нелинейными системами неравенств, и с синтезом сложных систем (фабрик) из простых компонентов, и с разгадыванием целого ряда хакерских квестов (недокументированные кодировки чисел, машин и топлива). Охватить все за 72 часа не было никакой возможности, поэтому я решил вернуться к некоторым интересным проблемам, и чисто для себя расставить все точки над ё.
По мере возможности буду складывать здесь результаты своих изысканий.

Входная последовательность от сервера

Знание входной последовательности нам совершенно не пригодилось во время контеста, поскольку мы нашли способ строить фабрики, выход которых не зависит от входа. Однако некоторые команды (например, hack-the-loop) напрямую использовали входную последовательность, поэтому им пришлось ее вычислить. Я опишу способ, как можно найти входную последовательность произвольной длины.

Во всех наших мытарствах мы будем использовать в качестве информации скудные по содержанию ответы сервера на наши тестовые фабрики. Выберем машину 2416 и будем с ней работать, пытаясь подбирать к ней топливо.

Знаменитая "пустая" фабрика X::X дает нам первые 17 тритов последовательности (так как вход накоротко соединен с выходом):
 

circuit output starts with
01202101210201202
this is an illegal prefix.

 

Чтобы идти далее, введем 3 вида макроблоков:
 

                         x +--+   in(0) = 0; y(0) = 0;
                         | |y0|   out(i) = in(i) - y0(i);
0L:                     +---+ |   y0(i+1) = in(i) * y0(i) - 1;
X0R0#X0R:         h0    | 0 | |
0L                      +---+ |
                         | |  |
                         x +--+


                      +--+ +--+   x0(0) = 0; y0(0) = 0;
                      |x0| |y0|   x0(i+1) = x0(i) - y0(i);
                      | +---+ |   in(0) = 0;
                      | | 0 | |   out(i) = in(i) - x0(i) * y0(i) + 1;
                      | +---+ |   y0(i+1) = in(i) * x0(i) * y0(i) - in(i) - 1;
1L:                   |  | |  |
0L1R0#0L1R,           +--+ |  |
X0R0#X0R:         h1       |  |
1L                       x |  |
                         | |  |
                        +---+ |
                        | 1 | |
                        +---+ |
                         | |  |
                         x +--+


                     +--+ +----+   x0(0) = 0; y0(0) = 0;                       
                     |x0| |y0  |   x0(i+1) = x0(i) - y0(i);                    
                     | +---+   |   in(0) = 0;
                     | | 0 |   |   out(i) = x0(i) * y0(i) - 1 - in(i);
                     | +---+   |   y0(i+1) = (x0(i) * y0(i) - 1) * in(i) - 1;
1R:                  |  | |    |
0L1R0#0L1L,          +--+ | x  |
0RX0#X0R:       h2        | |  |
1L                       +---+ |
                         | 1 | |
                         +---+ |
                          | |  |
                          x +--+

Это те самые 3 вида блоков, из которых мы строили свои фабрики во время контеста (не зависящие от входа), но они же пригодятся и для решения нашей задачи.

Итак, блок h[i] выдаст на выходе трит i в начальный момент времени, при условии, что на вход будет подан 0. Это условие легко удовлетворяется путем соединения блоков в цепочку "обратными" проводами. Обратным мы называем провод, соединяющий выход гейта с большим номером со входом гейта с меньшим номером. Такой провод в начальный момент времени подает на вход 0, а затем уже то, что было на другом конце провода (т.е. осуществляет задержку сигнала на 1 такт со вставкой нуля в начале).

Введем обозначение :> для описания соединения двух макроблоков с такой задержкой. Тогда, к примеру, запись h0:>h0:>h1 означает следующее:

  +--+ +--+
  |  | |  |
  | +---+ |
  | | 0 | |
  | +---+ |
  |  | |  |
  +--+ |  |
       |  | h1
  +--+ |  |
  |  | |  |
  | +---+ |
  | | 1 | |
  | +---+ |
  |  | |  |
  |  x +--+
  |          +-------------+
  |          | +--+        |
  |          | |  |        |
  |         +---+ |        |
  |         | 2 | | h0     |
  |         +---+ |        |
  |          | |  |        |
  +----------+ +--+        |
                           |
                    x +--+ |
                    | |  | |
                   +---+ | |
                   | 3 | | | h0
                   +---+ | |
                    | |  | |
                    | +--+ |
                    +------+

Теперь построим следующую схему:
     +--+ +-------------------------------------------------------------------+     
     |  | |                                                                   |     
     | +---+                                                                  |     
     | | S |                                                                  |     
     | +---+                                                                  |     
     |  | |p   15  14  13  12  11  10  09  08  07  06  05  04  03  02  01  00 |     
     x  x +--:>h2:>h2:>h2:>h0:>h2:>h1:>h0:>h1:>h0:>h2:>h2:>h0:>h0:>h2:>h2:>h2-+     
                :   :   :   :   :   :   :   :   :   :   :   :   :   :   :   :
0    0  1  2\_  `2  `2  `2  `0  `2  `1  `0  `1  `0  `2  `2  `0  `0  `2  `2  `2
1    1  1  2/    0   0   0   0   2   0   2   1   2   2   0   0   1   2   0   0
2    2  0  0     ?0  2   2   0   1   0   2   1   0   2   0   0   1   0   0   2
3    0  2  2         ?1  2   0   0   2   1   1   1   1   0   1   1   1   2   1
4    2  1  1             ?0  2   2   0   0   1   2   0   1   1   2   0   0   1
5    1  2  1                 ?1  2   0   0   1   0   0   0   2   0   0   2   2
6    0  1  2                     ?0  0   1   2   1   2   2   2   2   2   0   2
7    1  0  0                         ?1  1   1   0   2   2   0   0   2   0   1
8    2  1  1                             ?2  2   1   2   2   2   0   1   0   1
9    1  1  2                                 ?2  0   0   1   0   0   1   1   0
10   0  2  2                                     ?2  2   2   1   0   0   2   1
11   2  1  1                                         ?1  2   0   2   2   2   1
12   0  0  2                                             ?0  2   2   2   2   0
13   1  1  2                                                 ?1  0   2   2   0
14   2  2  2                                                     ?1  0   1   0
15   0  2  2                                                         ?1  2   1
16   2  1  1                                                             ?0  1
17   ?1 ?2                                                                   ?2
     In Ou In*(In-Ou)-1                                                    In-Ou

По вертикали расположена шкала времени (левый столбец).

Известные данные: 17 входных тритов In (0, 1, 2, 0, ...), 17 выходных тритов aka префиксная последовательность Ou (1, 1, 0, 2, ...). Буквой S обозначен последний гейт, вычитающий из входной последовательности то, что получилось на выходе цепочки. То есть, последний столбец легко находится вычитанием In-Ou по модулю 3: (2, 0, 2, 1, 1, ...). Эта последовательность начинается с двойки, следовательно последним макроблоком должен быть h2. Обращением функции h2 (программа на C прилагается) находим последовательность на выходе предыдущего макроблока. Она начинается с двойки, поэтому нужен снова h2.

Повторяем указанный процесс до тех пор, пока очередной столбец не совпадет полностью с выходом p (который представляет собой In*(In-Ou)-1). В худшем случае понадобилась бы цепочка из 17 макроблоков, но нам повезло - выход p начинается как раз с одной двойки, что совпадает со столбцом длиной 1, состоящим из одной двойки, полученным обращением последовательности (2, 0) левым элементом h2. То есть эту двойку генерить не надо и мы экономим один блок.

Итак, мы собрали схему из 16 макроблоков и вычитателя S, генерящую префиксную последовательность. Скормим полученную фабрику серверу:


27L:
0L1R0#0L1L,
0R3L0#27R0R,
2L3R0#2L3L,
2R5L0#1R2R,
4L5R0#4L5L,
4R6L0#3R4R,
7L6R0#5R6R,
9L7R0#6L7R,
8L9R0#8L9L,
8R11L0#7L8R,
10L11R0#10L11L,
10R12L0#9R10R,
14L12R0#11R12R,
13L14R0#13L14R,
15L13R0#12L13R,
17L15R0#14L15R,
16L17R0#16L17R,
19L16R0#15L16R,
18L19R0#18L19L,
18R20L0#17L18R,
22L20R0#19R20R,
21L22R0#21L22L,
21R24L0#20L21R,
23L24R0#23L24L,
23R26L0#22R23R,
25L26R0#25L26L,
25R27R0#24R25R,
X1L0#X26R:
27L

circuit output starts with
11021210112101221
this is a legal prefix
parse error in fuel description
"input" (line 1, column 2):
unexpected token
expecting: '2'

Здесь мы столкнулись с особенностью кодировки чисел, а именно с тем фактом, что количество ведущих двоек в числе должно быть четным. Итак, судя по ответу сервера, в первой позиции после префикса у нас на выходе двойка, а следующая цифра - не двойка. Посмотрим, как можно применить новую найденную цифру выхода в наших целях. Запишем двойку в столбце Ou (строка 17, рядом с вопросительным знаком). Но что дальше? Известных данных в этой строке больше нет? Самое время вспомнить о том, что мы до сих пор использовали всего одну цифру с выхода p, хотя нам известны целых 17. Возьмем первые две (2, 2) и пропустим их через всю цепочку макроблоков. На каждом шаге будем получать одну новую цифру; дойдя до конца, будем иметь то, чего недоставало - двойку в строке 17 столбца In-Ou. Следовательно, у нас есть очередная цифра входной последовательности.

Теперь наша задача - получать последовательно подобные сообщения сервера, только "column 4, column 6, column 8... Для этого предусмотрим 2 режима брутфорса: в первом режиме мы добиваемся исчезновения сообщения "(line 1, column 2): unexpected token expecting: '2'" подбором последней цифры, удовлетворяя тем самым потребность сервера в недостающей двойке. На это требуется максимум 2 итерации. Во втором режиме мы перебираем сразу два следующих трита, чтобы вызвать сообщение "(line 1, column 4): unexpected token expecting: '2'". Здесь понадобится до 8 итераций. Итак, менее, чем за 10 итераций находятся 2 трита входной последовательности.

К сожалению, а может быть, и к счастью, указанный процесс нельзя продолжать бесконечно - на тысячной двойке сервер перестанет реагировать на процесс перебора - это ограничение длинной арифметики на стороне сервера. Однако, нас это ни в коем случае не остановит - самое время применить МОЗГ.

Выпишем полученную нами цепочку тритов:

012021012102012021020121012021012102012101202102012021012102012021020121012021020120210121...
Поглядим на нее внимательно. И еще раз. И еще. Никакого периода не наблюдается. Перепишем ее группами по 4 трита:
0120
2101
2102
0120
2102
0121
0120
2101
2102
0121
0120
2102
....

Теперь видно, что во второй колонке всегда единицы, а в первой и третьей - двойки и "инверсные" им нули. В четвертой же колонке записана вся входная последовательность. Итак, достаточно найти первую колонку тритов, а остальные колонки легко вычислить. Выпишем:
022020022002...
Снова сгруппировав по 4 цифры, и оставив только левую колонку, мы обнаружим, что... НИЧЕГО НЕ ИЗМЕНИЛОСЬ! Входная последовательность сервера является фрактальной!

Теперь легко можно сэмулировать вход сервера ЛЮБОЙ длины. Определим оператор Expand следующим образом. Он переводит цифру 0 в четверку цифр 0220, а цифру 2 - соответственно в четверку цифр 2002. Запишем первый трит 0, и применим к нему Expand. И повторим этот процесс теперь с каждым тритом полученной четверки. И еще раз, с каждым тритом из полученных 16-ти. "И еще много-много раз, да еще раз..." (С)

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