Um sistema cíclico de tags é um minúsculo modelo computacional completo de Turing que consiste em um alfabeto de dois símbolos (eu usarei {0,1}), uma lista cíclica finita e não vazia de produções que consistem nesses dois símbolos e uma palavra ilimitada que também consiste em esses dois símbolos.

Em cada etapa:

• o primeiro elemento da palavra é removido
• se fosse 0a produção atual é ignorada
• se foi, 1a produção atual é anexada ao final da palavra .
• a próxima produção se torna ativa. Se essa foi a última produção, volte para a primeira.

O sistema pára quando a palavra fica vazia.

Um exemplo (da Wikipedia):

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

Sua tarefa, se você optar por aceitá-la, é escrever um programa ou função que utilize:

• uma lista de produções,
• a palavra inicial e
• uma geração,

e imprime ou retorna a palavra nessa geração.

Por exemplo,

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]

Detalhes da implementação:

• O alfabeto não importa. Você pode usar 0e 1, Truee False, Te NIL, Ae B, ou mesmo 1e 0, ou qualquer outra coisa que possa inventar, desde que seja consistente. Todas as entradas e saídas devem usar o mesmo alfabeto e você deve indicar para o que está usando 0e para que 1.

• O comprimento da palavra deve ser teoricamente ilimitado. Ou seja, você não pode codificar um tamanho máximo de palavra. Se eu executar o seu programa em um computador ideal com uma quantidade infinita de memória, seu programa deve teoricamente ser capaz de fazer uso dele. (Você pode ignorar os limites do seu intérprete / compilador.)

• Se o sistema especificado parar antes que a geração seja atingida, você deverá retornar ou imprimir a palavra vazia.

• A produção vazia existe e você deve poder lidar com isso. Se você escrever um programa completo, sua E / S também deve poder lidar com isso.

Edit : Eu pretendia originalmente que geração 0fosse a própria palavra de entrada e geração 1fosse o resultado do primeiro passo. Ou seja, eu pretendia que você retornasse a coluna anterior . No entanto , como não fui suficientemente claro ao afirmar isso, aceitarei as duas opções ; para cada geração, você pode retornar o valor na coluna antes ou depois . Você deve declarar que está seguindo a coluna depois , se estiver fazendo isso. Você também deve ser consistente em qual coluna você escolher.

Atribuirei o menor código daqui a uma semana (27/10/2014).

GolfScript (17 a 19 bytes, dependendo do formato de entrada e do formato de saída aceito)

18 bytes:

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

Recebe entrada no formulário [1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 4e fornece saída no formulário [1 0 1 0 0 0 0]. (Pode ter 17 bytes sem o último `se a saída 1010000for aceitável).

Demonstração online

19 bytes:

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

Recebe entrada no formulário "11001" ["010" "000" "1111"] 4.

Demonstração online

Dissecação

~        # 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

Crédito para Martin Büttner 's solução CJam para a idéia de gerar a lista de produções por repetição e truncagem.

Haskell, 55 53 51

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

isso usa Truecomo 1e Falsecomo 0. exemplo execute:

*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 bytes

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

Isso define um bloco (a coisa mais próxima de uma função), que espera que a entrada resida na pilha como esta

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

Ele também irá deixar um conjunto de 0s e 1s na pilha.

Teste aqui. Cole a entrada na primeira linha, o código na terceira linha e acrescente a ~para realmente avaliar o bloco. Por exemplo

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

Se a saída não precisar ter o mesmo formato da entrada

Explicação:

_@*<{\_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.";

O estado final da palavra é deixado na pilha.

Agradeço a Peter Taylor por me fazer revisitar isso.

Mathematica, 84 80 77 caracteres

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

Exemplo:

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

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

Pitão 22

Requer todos os 3 argumentos como entradas separadas.

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

Toma argumentos como:

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

Explicação:

                        : 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

Resposta bastante Joe-Basic. Assume que a produção está vazia [[]].

Graças a @xnor, por apontar que jogar golfe às 2 da manhã é uma péssima decisão.

Agradecimentos adicionais a @xnor, a quem pareço dever 50% da minha pontuação.

Amostra:

>>> 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 bytes

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

Parece estranhamente semelhante à resposta de Fry, que apareceu no meu navegador. (Sem cópia, juro solenemente.)

Parece que ele seguiu a rota do array enquanto eu segui a rota string / regex.

Expandido:

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

Saída de amostra

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

Agora observe as línguas do golfe entrarem e massacrarem nós dois. : D