top of page
Level 4
Загадочная
машина
Лампочки на терминале приняли необходимое положение и панель центрального сервера открылась.
Однако, вместо ожидаемых электронных плат и проводов, наши друзья увидели внутри машину, весьма странного вида. Весь большой компьютер был просто бутафорией, скрывавшей эту машину!
Машина состоит из длиннющей бумажной ленты, поделённой на клетки, над которой туда-сюда ездит механическая рука с карандашом и стёркой.
Параллельно первой ленте есть и вторая, тоже поделённая на клетки - однако над ней, вместе "руки" двигается считывающая головка. Эта вторая лента заполнена странного вида значками, вроде таких:
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
Рядом находится принтер, больше напоминающий старинную печатную машинку.
Обычного человека такой поворот дел наверняка бы смутил, но наши хакеры не лыком шиты!
Они тут же распознали в загадочных надписях "ВыносМозга" - эзотерический компьютерный язык, известный невозможностью читать программы на нём написанные.
Что же это за язык ? Как прочитать загадочные надписи ?
Давайте с ним познакомимся.
В конкретной, немного упрощённой реализации Wintermute, cистема ВыносМозга состоит из ленты, поделённой на ячейки, в каждой из которых могут быть записаны числа от 0 до 255 (то есть, один байт информации). Назовём её "лентой данных". На ленту данных указывает считывающе-записывающая головка (назовём её "указатель данных"), в каждый момент времени находящаяся строго над какой-то одной клеткой. Эта головка может передвигаться по ленте в соответствии с программой, записанной на второй ленте, которую мы назовём "лентой программы". По ленте программы передвигается считывающее устройство, тоже находящее строго над одной ячейкой в каждый момент времени. Это устройство мы назовём "указателем программы". У машины также есть и печатающее устройство (которое печатает на простой бумаге, не имеющей отношения к двум первым лентам).
Вот диаграмма машины ВыносМозга:
Теперь нам нужно познакомиться с самим языком.
Он крайне прост и в нашем диалекте состоит из семи команд:
> - продвинуть указатель данных на одну ячейку вправо на ленте данных.
< - продвинуть указатель данных на одну ячейку влево на ленте данных.
+ - увеличить текущее число под указателем данных на ленте данных на единицу.
- - уменьшить текущее число под указателем данных на ленте данных на единицу.
. - распечатать текущее число под указателем данных на ленте данных на печатающем устройстве.
[ - если текущее число на ленте данных ноль, то найти на ленте программы соответствующую скобку ] (двигаться вправо) и установить указатель программы на ячейку, следующую за ]
]- если текущее число на ленте данных больше нуля, то найти на ленте программы соответствующую скобку [(двигаться влево) установить указатель программы на ячейку, следующую за [
ВАЖНО:
Указатель программы вначале устанавливается на самую левую ячейку и сдвигается на одну ячейку вправо после выполнения каждой команды на ленте программы, кроме тех случаев, когда команды [ и ] заставляют его прыгать по ленте программы.
Перед запуском программы все ячейки ленты данных содержат нули.
Этот язык интересен тем, что он - Turing-Complete ("Тьюринг-полон" по-русски). Это означает то, что любая задача, которая может быть решена на самом быстром современном суперкомьютере, может быть решена и на системе "ВыносМозга". А также, любая программа, которая может быть написана на любом, самом мощном языке программирования (например, С++), может быть написана на языке "ВыносМозга".
Конечно, работать она будет в миллион раз медленней, и программу эту прочитать будет совершенно невозможно, но тем не менее с задачей она справится успешно.
Как решить задачу ?
Для решения этой задачи вам нужно будет написать интерпретатор языка "ВыносМозга".
Интерпретатор - это программа, которая переводит некий язык программирования в команды, понятные компьютеру (в данном случае - в команды, понятные машине, описанной выше).
(Кстати, сам Пайтон - это тоже интерпретатор, который переводит написанную вами программу в некие промежуточные команды (называемые "байткодом"), которые в свою очередь переводятся в машинные команды).
Для этого вам нужно будет представить на Пайтоне ленту данных, ленту программы, указатель данных и указатель программы.
Печатным устройством будет служить распечатывающая функция Пайтона (см. ниже).
Обратите внимание на команды [ и ]. Каждая из них говорит о передвижении к соответствующей скобке. Это означает следующее:
Однако, такое определение значительно усложняет вашу задачу.
Для наших целей вам будет достаточно просто найти первую попавшуюся на ленте скобку:
для [ найти первую встретившуюся справа ],
для ] найти первую встретившуюся слева [.
Тем не менее, если вы хотите решить задачу целиком, ищите именно соответствующие скобки.
Что вам может понадобиться для решения ?
Здесь вам может пригодиться понятие класса (class), хотя это совершенно не обязательно. Тем не менее, в классе удобно хранить все относящиеся к делу переменные, например:
class Interpreter:
def __init__(self, program):
self.data_tape = # some representation
self.data_pointer = 0
self.program = program
self.program_pointer = 0
Числа на ленте данных можно представлять простыми integers. Важно: следите, чтобы при отнимании единицы, число 0 превращалось в 255, а не в -1, а при прибавлении единицы, число 255 превращалось в 0, а не в 256 !!!
Для того, чтобы распечатывать числа на "печатающем устройстве", используйте следующую конструкцию:
sys.stdout.write(chr(data_tape[data_pointer]))
где data_tape - лента данных, а data_pointer - указатель данных. (Не забудьте также импортировать модуль sys).
Такой вызов будет распечатывать символы ASCII, соответствующие кодам на ленте данных, и без перевода строки. Это означает только то, что вы сможете свободно читать надпись на ленте данных, как будто бы она была написана английскими буквами, а не числами.
Для того, чтобы проверять работу программы (debugging), удобно создать функцию print_data_tape(), которая будет распечатывать текущее состояние ленты данных и указатель ленты данных после каждой команды программы.
Как раскрыть пароль ?
Каждый хакер в своём почтовом ящике получит сообщение, которое будет представлять собой программу на языке "ВыносМозга". Запустив это программу на созданном интерпретаторе, вы узнаете свою часть пароля.
Пароль будет состоять из частей, раскрытых каждым из хакеров в следующем порядке:
Линус + Сатоши Накамото + Тринити + J.F.Sebastian + Дораемон
до конца уровня
Теперь, когда вы знаете пароль, можете переходить на
bottom of page