Cykliczny układ znacznika jest bardzo małe, Turinga niepełny model obliczeniowy, składający się z dwóch alfabet symboli (będziemy używać {0,1}) skończoną, liście niepusty cyklicznego produkcji , które składają się z tych dwóch symboli, a także nieograniczona słowo który również składa się z te dwa symbole.

Na każdym kroku:

• pierwszy element słowa jest usuwany
• jeśli tak, 0obecna produkcja jest pomijana
• jeśli tak, to 1obecna produkcja jest dołączana na końcu słowa .
• następna produkcja staje się aktywna. Jeśli to była ostatnia produkcja, wróć do pierwszej.

System zatrzymuje się, gdy słowo staje się puste.

Przykład (z Wikipedii):

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

Twoim zadaniem, jeśli zdecydujesz się go zaakceptować, jest napisanie programu lub funkcji, która wymaga:

• lista produkcji,
• początkowe słowo oraz
• generacja,

i drukuje lub zwraca słowo tego pokolenia.

Na przykład,

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]

Szczegóły dotyczące wdrożenia:

• Alfabet nie ma znaczenia. Możesz używać 0i 1, Truei False, Ti NIL, Aa Bnawet 1a nawet 0cokolwiek innego możesz wymyślić, o ile jesteś konsekwentny. Wszystkie dane wejściowe i wyjściowe muszą używać tego samego alfabetu, a Ty musisz wskazać, do czego używasz 0i do czego 1.

• Długość słowa musi być teoretycznie nieograniczona. Oznacza to, że nie możesz zakodować na stałe maksymalnej długości słowa. Jeśli uruchomię twój program na idealnym komputerze z nieskończoną ilością pamięci, twój program musi teoretycznie być w stanie z niego skorzystać. (Możesz zignorować ograniczenia swojego tłumacza / kompilatora).

• Jeśli dany system zatrzyma się przed osiągnięciem danego pokolenia, musisz zwrócić lub wydrukować puste słowo.

• Pusta produkcja istnieje i musisz być w stanie sobie z nią poradzić. Jeśli napiszesz pełny program, twoje I / O również musi być w stanie go obsłużyć.

Edycja : Pierwotnie zamierzałem, aby generacja 0była samym słowem wejściowym, a generacja 1była wynikiem pierwszego kroku. To znaczy, chciałem, żebyś zwrócił kolumnę przed . Ponieważ jednak nie wyjaśniłem tego wystarczająco jasno, zaakceptuję obie opcje ; dla każdego pokolenia możesz zwrócić wartość w kolumnie przed lub po . Należy stwierdzić, że jesteś po po kolumnie, jeśli robisz tak. Musisz także zachować spójność w wybranej kolumnie.

Przyznam najmniejszy kod za tydzień od teraz (27.10.2014).

GolfScript (17–19 bajtów w zależności od formatu wejściowego i akceptowanego formatu wyjściowego)

18 bajtów:

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

Pobiera dane wejściowe w formularzu [1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 4i podaje dane wyjściowe w formularzu [1 0 1 0 0 0 0]. (Może być 17 bajtów bez ostatniego, `jeśli dane wyjściowe 1010000są dopuszczalne).

Demo online

19 bajtów:

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

Pobiera dane wejściowe w formularzu "11001" ["010" "000" "1111"] 4.

Demo online

Sekcja

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

Kredytowej Martin Büttner „s rozwiązania CJam dla idei generowania listy produkcjach przez powtarzanie i obcięcia.

Haskell, 55 53 51

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

używa to Truejako 1i Falsejako 0. przykładowy bieg:

*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 bajtów

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

Definiuje to blok (najbardziej zbliżony do funkcji), który oczekuje, że wejście znajdzie się na stosie w ten sposób

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

Będzie podobnie zostawić tablicę 0s oraz 1s na stosie.

Sprawdź to tutaj. Wklej wejście w pierwszym wierszu, kod w trzecim wierszu i dołącz a, ~aby faktycznie ocenić blok. Na przykład

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

Jeśli dane wyjściowe nie muszą mieć takiej samej postaci jak dane wejściowe

Wyjaśnienie:

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

Ostateczny stan słowa jest pozostawiony na stosie.

Dzięki Peter Taylor za ponowną wizytę.

Mathematica, 84 80 77 znaków

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

Przykład:

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

Wymaga wszystkich 3 argumentów jako osobnych danych wejściowych.

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

Przyjmuje argumenty takie jak:

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

Wyjaśnienie:

                        : 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

Ładna odpowiedź Joe Basic. Zakłada, że ​​pusta produkcja jest [[]].

Dzięki @xnor za zwrócenie uwagi, że gra w golfa o 2 nad ranem to kiepska decyzja.

Dodatkowe podziękowania dla @xnor, któremu zawdzięczam 50% mojego wyniku.

Próba:

>>> 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 bajtów

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

Wygląda niesamowicie podobnie do odpowiedzi Fry'ego, która właśnie pojawiła się w mojej przeglądarce. (Bez kopiowania, uroczyście przysięgam.)

Wygląda jednak na to, że poszedł trasą tablicową, a ja trasą ciąg / wyrażenie regularne.

Rozszerzony:

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

Przykładowe dane wyjściowe

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

Teraz obserwuj, jak nadchodzą języki golfa i masakra nas obu. :RE