Забавно, что в этом мире всего лишь 1 измерение времени, но это не обязательно должно быть так. Легко представить себе миры с двумя или более измерениями времени, и в этих мирах вы можете создавать компьютеры и запускать на них программное обеспечение, как в этом.
Система
Вот система для запуска программ Brainf * ck в двух измерениях времени:
Два временных измерения - это х и у. Каждая программа Brainf * ck состоит из х полупрограммы и любой полупрограммы, например, программа может быть
x: +>+
y: [-]
Каждая из двух полупрограмм имеет свой собственный программный указатель, но у них один указатель на ленту (то есть они работают с одной и той же ячейкой ленты).
Время является двумерным, поэтому оно состоит из сетки моментов:
Двигаясь по измерению x, полупрограмма x выполняет один временной шаг. Двигаясь по измерению y, полупрограмма y выполняется за один раз.
Например, предположим, что лента начинается как [0] 0 0( []представляет указатель ленты), а программы x / y - +и ->-. Выполнение этой программы будет выглядеть так:
x y tape x-action y-action
0 0 [ 0] 0 0 + at 0 - at 0
1 0 [ 1] 0 0 (done) - at 0
0 1 [-1] 0 0 + at 0 move >
1 1 [ 0] 0 0 (done) move >
Обратите внимание, что, поскольку время движется в направлении y, полупрограмма x продолжает делать одно и то же снова и снова, потому что его время не прогрессирует.
Лента в каждый момент включает в себя совокупный эффект всех поступающих в нее действий (каждое действие считается один раз). Так, например, лента во время (2, 1) содержит совокупный эффект:
- X-действие от (0, 0)
- X-действие от (1, 0)
- X-действие от (0, 1)
- Х-действие из (1, 1)
- у-действие из (0, 0)
- у-действие из (1, 0)
- у-действие из (2, 0)
Накопительное означает:
- Все приращения и уменьшения к сумме ячеек вместе.
- Все движения влево (-1) и вправо (+1) к указателю ленты суммируются вместе.
Указатели инструкций не накапливаются. Каждая полупрограмма получает указатель инструкций от предыдущего момента в своем измерении. Таким образом, указатели программы x выполняются только в измерении x, а указатели программы y - только в измерении y. Так, например, в программе ( [], +), начиная с [0] 0 0, выполнение будет
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 0 0 0 + at 0 0 0
1 0 0 0 0 + at 0 2 (from jump) 0
0 1 1 0 0 0 1
1 1 2 0 0 1 (from NO jump) 1
Еще несколько моментов из вышеупомянутого ( +, ->-) моделирования:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
2 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 > 0 1
1 1 [ 0] 0 0 > 1 1
2 1 [-1] 0 0 > 1 1
0 2 -1 [ 0] 0 + at 1 - at 1 0 2
1 2 0 1 [ 0] - at 2 1 2
2 2 [-1] 1 0 - at 0 1 2
Допускаются следующие операторы Brainf * ck (они имеют стандартное значение):
+,-: приращение, уменьшение;[,]: цикл до нуля (обработка a[или]занимает один временной шаг, как в стандартном Brainf * ck);<,>: двигаться влево / вправо на ленте.
Сложный пример
Для программы ( >, +) начиная с [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > + at 0 0 0
1 0 0 [ 0] 0 + at 1 1 0
0 1 [ 1] 0 0 > 0 1
1 1 1 1 [ 0] 1 1
Для ( +, -) начиная с [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 0 1
1 1 [ 0] 0 0 1 1
Обратите внимание, что лента заканчивается как и [0] 0 0потому, что каждый +и -происходит дважды, суммируя до 0.
Для программы ( >+, [-]) начиная с [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > 0 0
1 0 0 [ 0] 0 + at 1 1 0
2 0 0 [ 1] 0 2 0
0 1 [ 0] 0 0 > 0 3
1 1 0 0 [ 0] + at 2 1 3
2 1 0 1 [ 1] - at 2 2 1
0 2 [ 0] 0 0 > 0 3
1 2 [ 0] 0 0 + at 0 1 3
2 2 [ 1] 1 0 2 2
Схема со стрелками
На диаграмме ниже показано, как рассчитать действия и ленту:
Головоломка
Напишите 2D-программу Brainf * ck (с полупрограммой x и y-полупрограммой) для запуска на 3-элементной ленте, которая удовлетворяет обоим следующим условиям:
- Если лента начинается как
[0] 0 0, во время (5, 5) она имеет0нулевую ячейку. - Если лента начинается как
[1] 0 0, во время (5, 5) она имеет0нулевую ячейку.
Победит самая короткая программа, отвечающая требованиям.
+и>? Если это1 1 [0](довольно сумасшедший, но это то, что спецификация, кажется, предлагает), Как комбинируются указатели инструкций? Если два потока+и[], то на1 2ленте данных будет[3], но является ли указатель второй инструкции внутри цикла ([]+путь) или снаружи ([+]путь) или даже недопустимым (+[])?+,>), чтобы увидеть, получу ли я тот же результат, что и вы.(1,1)через либо,(1,0)либо(0,1), но если одна программа начинается,>а другая начинается+, то, конечно, их относительный порядок имеет значение?Ответы:
Всего 4 байта: (
[-],>)Я написал брутфорсер, чтобы найти самую маленькую такую программу.
Вот схемы этой программы в действии. Эти сетки расположены аналогично сетке в спецификации, с (0,0) левым нижним углом, временем x по оси x и временем y по оси y. В верхнем правом углу содержится результат.
Во-первых, с лентой
0 0 0:Теперь с лентой
1 0 0:Было несколько вещей, которые не были четко объяснены в спецификации, например, тот факт, что 3-элементная лента наматывается вокруг.
В качестве бонуса, вот визуализация примера (
>+,[-]):И один из (
>+,+>) пример:Обратите внимание, что верхний правый угол отличается от того, что вы перечислили, я думаю, что это ошибка в вашем примере, потому что мой код соответствует любому другому примеру, который я пробовал.
источник