Un sistema de etiquetas cíclicas es un pequeño modelo computacional completo de Turing que consta de un alfabeto de dos símbolos (lo usaré {0,1}), una lista cíclica finita, no vacía de producciones que consisten en esos dos símbolos, y una palabra sin límites que también consiste en Esos dos símbolos.

En cada paso:

• se elimina el primer elemento de la palabra
• si fuera 0la producción actual se omite
• si era 1la producción actual se agrega al final de la palabra .
• La próxima producción se activa. Si esta fue la última producción, regrese a la primera.

El sistema se detiene cuando la palabra se vacía.

Un ejemplo (de 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

Su tarea, si elige aceptarla, es escribir un programa o función que tome:

• una lista de producciones,
• la palabra inicial, y
• Una generación,

e imprime o devuelve la palabra en esa generación.

Por ejemplo,

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]

Detalles de implementacion:

• El alfabeto no importa. Puede usar 0y 1, Truey False, Ty NIL, Ay B, o incluso 1y 0, o cualquier otra cosa que se le ocurra, siempre que sea coherente. Todas las entradas y salidas deben usar el mismo alfabeto, y usted debe indicar para qué está usando 0y para qué 1.

• La longitud de la palabra debe ser teóricamente ilimitada. Es decir, no puede codificar una longitud máxima de palabra. Si ejecuto su programa en una computadora ideal con una cantidad infinita de memoria, su programa teóricamente debe poder usarlo. (Puede ignorar los límites de su intérprete / compilador).

• Si el sistema dado se detiene antes de que se alcance la generación dada, debe devolver o imprimir la palabra vacía.

• La producción vacía existe y debes poder manejarla. Si escribe un programa completo, su E / S también debe poder manejarlo.

Editar : originalmente tenía la intención de que la generación 0fuera la palabra de entrada en sí, y que la generación 1fuera el resultado del primer paso. Es decir, tenía la intención de que devolvieras la columna anterior . Sin embargo , como no he sido lo suficientemente claro al afirmar esto, aceptaré ambas opciones ; para cada generación, puede devolver el valor en la columna anterior o posterior . Debe indicar que está siguiendo la columna posterior , si lo está haciendo. También debe ser coherente en la columna que elija.

Otorgaré el código más pequeño dentro de una semana (27/10/2014).

GolfScript (17 a 19 bytes dependiendo del formato de entrada y el formato de salida aceptado)

18 bytes:

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

Toma entrada en el formulario [1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 4y da salida en el formulario [1 0 1 0 0 0 0]. (Podría tener 17 bytes sin el último `si la salida 1010000es aceptable).

Demostración en línea

19 bytes:

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

Toma entrada en el formulario "11001" ["010" "000" "1111"] 4.

Demostración en línea

Disección

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

El crédito a Martin Büttner 's solución Cjam de la idea de generar la lista de producciones de repetición y truncamiento.

Haskell, 55 53 51

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

esto usa Trueas 1y Falseas 0. ejemplo ejecutado:

*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?(@*+}/}

Esto define un bloque (lo más parecido a una función), que espera que la entrada resida en la pila de esta manera

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

Del mismo modo que dejará una gran variedad de 0s y 1s en la pila.

Pruébalo aquí. Pegue la entrada en la primera línea, el código en la tercera línea, y agregue una ~para evaluar realmente el bloque. P.ej

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

Si la salida no tiene que tener la misma forma que la entrada

Explicación:

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

El estado final de la palabra se deja en la pila.

Gracias a Peter Taylor por hacerme volver a visitar esto.

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]

Ejemplo:

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

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

Pyth 22

Requiere los 3 argumentos como entradas separadas.

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

Toma argumentos como:

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

Explicación:

                        : 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

Pretty Joe-Basic respuesta. Asume que la producción vacía es [[]].

Gracias a @xnor, por señalar que jugar golf a las 2 am es una mala decisión.

Un agradecimiento adicional a @xnor, a quien parece que le debo el 50% de mi puntaje.

Muestra:

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

Se ve extrañamente similar a la respuesta de Fry que acaba de aparecer en mi navegador. (Sin copiar, lo juro solemnemente).

Sin embargo, parece que él siguió la ruta de la matriz mientras yo fui por la ruta de cadena / expresión regular.

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

Salida de muestra

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

Ahora mire cómo llegan los idiomas del golf y masacre a los dos. :RE