Simulate a Cyclic Tag System

Question

A cyclic tag system is a tiny, Turing-complete computational model consisting of a two-symbol alphabet (I'll use {0,1}), a finite, nonempty cyclic list of productions that consist of those two symbols, and an unbounded word which also consists of those two symbols.

At each step:

• the first element in the word is removed
• if it was 0 the current production is skipped
• if it was 1 the current production is appended to the end of the word.
• the next production becomes active. If this was the last production, go back to the first one.

The system halts when the word becomes empty.

An example (from 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

Your task, if you choose to accept it, is to write a program or function that takes:

• a list of productions,
• the initial word, and
• a generation,

and prints or returns the word at that generation.

For example,

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]

Implementation details:

• The alphabet does not matter. You may use 0 and 1, True and False, T and NIL, A and B, or even 1 and 0, or whatever else you may come up with, as long as you are consistent. All input and output must use the same alphabet, and you must indicate what you are using for 0 and what for 1.

• The length of the word must be theoretically unbounded. That is, you may not hardcode a maximum word length. If I run your program on an ideal computer with an infinite amount of memory, your program must theoretically be able to make use of it. (You may ignore your interpreter's/compiler's limits.)

• If the given system halts before the given generation is reached, you must return or print the empty word.

• The empty production exists, and you must be able to handle it. If you write a full program, your I/O must also be able to handle it.

Edit: I had originally intended for generation 0 to be the input word itself, and generation 1 to be the result of the first step. I.e., I had intended for you to return the before column. However, as I have not been clear enough in stating this, I will accept both options; for each generation you may return the value in either the before or the after column. You must state that you are following the after column, if you are doing so. You must also be consistent in which column you choose.

I will award the smallest code a week from now (10/27/2014).

Answer 1

GolfScript (17 to 19 bytes depending on input format and accepted output format)

18 bytes:

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

Takes input in the form [1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 4 and gives output in the form [1 0 1 0 0 0 0]. (Could be 17 bytes without the last ` if output as 1010000 is acceptable).

Online demo

19 bytes:

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

Takes input in the form "11001" ["010" "000" "1111"] 4.

Online demo

Dissection

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

Credit to Martin Büttner's CJam solution for the idea of generating the list of productions by repetition and truncation.

Answer 2

Haskell, 55 53 51

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

this uses True as 1 and False as 0. example run:

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

Answer 3

CJam, 31 30 28 27 24 18 bytes

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

This defines a block (the closest thing to a functioN), which expects the input to reside on the stack like this

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

It will similarly leave an array of 0s and 1s on the stack.

Test it here. Paste the input one the first line, the code on the third line, and append a ~ to actually evaluate the block. E.g.

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

If output does not have to have the same form as input

Explanation:

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

The final state of the word is left on the stack.

Thanks to Peter Taylor for making me revisit this.

Answer 4

Pyth 22

Requires all 3 arguments as separate inputs.

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

Takes arguments like:

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

Explanation:

                        : 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 answer. Assumes the empty production is [[]].

Thanks to @xnor, for pointing out that golfing at 2 a.m. is a poor decision.

Additional thanks to @xnor, to whom I seem to owe 50% of my score.

Sample:

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

Answer 5

Mathematica, 84 80 77 chars

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

Example:

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

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

Answer 6

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

Looks eerily similar to Fry's answer which just popped up in my browser. (No copying, I do solemnly swear.)

It would appear he went the array route while I went the string/regex route, however.

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

Sample Output

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

Now watch the golf languages come in and massacre both of us. :D