Система циклических тегов - это крошечная, полная по Тьюрингу вычислительная модель, состоящая из двухсимвольного алфавита (я буду использовать {0,1}), конечного непустого циклического списка произведений , состоящих из этих двух символов, и неограниченного слова, которое также состоит из эти два символа.

На каждом этапе:

• первый элемент в слове удален
• если это было 0текущее производство пропускается
• если это было 1текущее производство , добавляется в конце слова .
• следующее производство становится активным. Если это было последнее производство, вернитесь к первому.

Система останавливается, когда слово становится пустым.

Пример (из Википедии):

Productions: (010, 000, 1111)
Initial word: 11001

Generation  Production   Word (before)            Word (after)
   0           010           11001             →     1001010       
   1           000            1001010          →      001010000
   2           1111            001010000       →       01010000
   3           010              01010000       →        1010000
   4           000               1010000       →         010000000
   5           1111               010000000    →          10000000
   6           010                 10000000    →           0000000010
   7           000                  0000000010 →            000000010
   8           1111                  000000010 →             00000010
   9           010                    00000010 →              0000010

Ваша задача, если вы решите принять ее, - написать программу или функцию, которая принимает:

• список производств,
• начальное слово и
• поколение,

и печатает или возвращает слово в этом поколении.

Например,

cyclic_tag(
      prod=[[0,1,0],[0,0,0],[1,1,1,1]], 
      word=[1,1,0,0,1], 
      gen=4) => [1,0,1,0,0,0,0]

Детали реализации:

• Алфавит не имеет значения. Вы можете использовать 0и 1, Trueи False, Tи NIL, Aи B, или, даже 1и 0, или что- либо еще , что вы можете придумать, если вы последовательны. Все входные и выходные данные должны использовать один и тот же алфавит, и вы должны указать, для чего вы используете и для 0чего 1.

• Длина слова должна быть теоретически неограниченной. То есть вы не можете жестко задавать максимальную длину слова. Если я запускаю вашу программу на идеальном компьютере с бесконечным объемом памяти, ваша программа должна теоретически использовать ее. (Вы можете игнорировать ограничения вашего интерпретатора / компилятора.)

• Если данная система останавливается до достижения данного поколения, вы должны вернуть или напечатать пустое слово.

• Пустое производство существует, и вы должны быть в состоянии справиться с этим. Если вы пишете полную программу, ваш ввод / вывод также должен уметь ее обрабатывать.

Редактировать : изначально я хотел, чтобы поколение 0было самим входным словом, а поколение 1- результатом первого шага. То есть я намеревался вернуть вам столбец перед . Тем не менее , поскольку я не достаточно ясно сформулировал это, я приму оба варианта ; для каждого поколения вы можете возвращать значение в столбце « до» или « после» . Вы должны указать, что следите за колонкой после , если вы это делаете. Вы также должны быть уверены, в какой колонке вы выбираете.

Я присуждаю самый маленький кодекс через неделю (27.10.2014).

GolfScript (от 17 до 19 байт в зависимости от формата ввода и принятого формата вывода)

18 байт:

~.@*<{\1,or(@*+}/`

Принимает вход в виде [1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 4 и выдает выходные данные в форме [1 0 1 0 0 0 0]. (Может быть 17 байтов без последнего, `если вывод как 1010000приемлемый).

Онлайн демо

19 байт:

~.@*<{\0`or(1&@*+}/

Принимает участие в форме "11001" ["010" "000" "1111"] 4.

Онлайн демо

рассечение

~        # Evaluate input: stack: word productions gen
.@*<     # Produce a list of the right number of productions with suitable repetition
{        # For each of those productions:
  \      #   Bring the word to the top
  0`or   #   Ensure that we don't get an error if the word is empty
  (1&    #   Pop the first char from the word and evaluate it
  @*     #   Repeat the production that many times
  +      #   Concatenate 0 or 1 copies of the production to the rest of the word
}/       # Endforeach

Кредит Martin Büttner «s решение CJam для идеи создания списка постановок повторения и усечения.

Хаскелл, 55 53 51

(t:w)%p|t=w++p|0<1=w
x%_=x
e w=(!!).scanl(%)w.cycle

это использует Trueкак 1и Falseкак 0. пример выполнения:

*Main> let t=True ; f=False
*Main> e [t,f,t] [[f,f,f],[t,t,t]] 4
[False,False,False,False,False]

CJam, 31 30 28 27 24 18 байт

{_@*<{\_0a?(@*+}/}

Это определяет блок (самый близкий к функции), который ожидает, что вход будет находиться в стеке, как это

[1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 9

Он также оставит массив 0s и 1s в стеке.

Проверьте это здесь. Вставьте ввод в первую строку, код в третью строку и добавьте a, ~чтобы фактически оценить блок. Например

[1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 9
{_@*<{\_0a?(@*+}/}~

Если вывод не должен иметь ту же форму, что и ввод

Объяснение:

_@*<{\_0a?(@*+}/
_@               "Duplicate the generation and pull the productions to the top.";
  *<             "Repeat the productions N times and take the first N elements.";
    {         }/ "For each element in that list, run this block.";
     \           "Swap production and current word W.";
      _0a?       "W = (W != []) ? W : [0]. This is to ensure we can unshift an element.";
          (      "Unshift the first 0 or 1 from the word.";
           @     "Rotate the stack, pulling the production to the top.";
            *    "Repeat it 0 or 1 times.";
             +   "Append to the word.";

Конечное состояние слова остается в стеке.

Спасибо Питеру Тейлору за то, что он заставил меня вернуться к этому.

Mathematica, 84 80 77 символов

f[_,w_,_]=w;f[p_,{x_,y___},n_/;n>0]:=f[RotateLeft@p,Flatten@{y,p~Take~x},n-1]

Пример:

f[{{0, 1, 0}, {0, 0, 0}, {1, 1, 1, 1}}, {1, 1, 0, 0, 1}, 4]

{1, 0, 1, 0, 0, 0, 0}

Пиф 22

Требуются все 3 аргумента в качестве отдельных входных данных.

#Vvw=z+tz*@Q%NlQshz)zq

Принимает аргументы, такие как:

11001
["010","000","1111"]
4

Объяснение:

                        : Implicit: z = input(); Q=eval(input())
#                       : Loop until an exception is thrown
 Vvw               )    : for N in range(eval(input()))
    =z                  : assign to z
      +tz               : the sum of the tail of z and
         *@Q%NlQ        : Q[N%len(Q)] times
                shz     : the numeric value of the first character in z
                    zq  : print z then throw exception

Python 2 - 61 67 91 105 124

c=lambda p,w,g:g*w and c(p[1:]+p[:1],w[1:]+w[0]*p[0],g-1)or w

Симпатичный Джо-Базовый ответ. Предполагается, что пустое производство[[]] .

Спасибо @xnor за то, что указал на то, что игра в гольф в 2 часа ночи - плохое решение.

Дополнительная благодарность @xnor, которому я, похоже, должен 50% моего балла.

Образец:

>>> c([[0,1,0],[0,0,0],[1,1,1,1]],[1,1,0,0,1],4)
[1, 0, 1, 0, 0, 0, 0]

Javascript ES6 - 88 байт

f=(p,w,g,n)=>g?w.replace(/(.)(.*)/,(_,a,b)=>f(p,a*1?b+p[(n=n||0)%p.length]:b,g-1,n+1)):w

Выглядит жутко похоже на ответ Фрая, который только что появился в моем браузере. (Нет копирования, я торжественно клянусь.)

Казалось бы, он пошел по маршруту массива, а я по маршруту string / regex.

Expanded:

f = (p,w,g,n) =>
    g ?
        w.replace( /(.)(.*)/, (_,a,b) =>
            f( p, a*1 ? b + p[(n=n||0)%p.length] : b, g-1, n+1 )
        )
    :
        w

Пример вывода

f(['010','000','1111'],'11001',4)
"1010000"

Теперь смотрите, как появляются языки гольфа и расправляетесь с нами обоими. : D