14
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Um, are you sure your output in the example is correct? Based on the other example you gave, I think that is gen 5... \$\endgroup\$ – FryAmTheEggman Oct 25 '14 at 2:44
  • \$\begingroup\$ Can we take the input in a different order? \$\endgroup\$ – Martin Ender Oct 25 '14 at 12:44
  • 1
    \$\begingroup\$ @FryAmTheEggman: It's correct, I meant the 'before' column. If more people have made this mistake, I will change my question to accept either. I admit I wasn't very clear. \$\endgroup\$ – marinus Oct 27 '14 at 6:08
  • \$\begingroup\$ @MartinBüttner: as long as you specify the order, it does not matter. \$\endgroup\$ – marinus Oct 27 '14 at 6:08
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You are tied with the CJam solution you cite, so I've chosen that answer. If you shave another byte off I'll reconsider :) \$\endgroup\$ – marinus Nov 6 '14 at 12:15
  • \$\begingroup\$ @marinus, do you accept the 17 byte version I refer to in the text of my answer? \$\endgroup\$ – Peter Taylor Nov 6 '14 at 12:35
  • \$\begingroup\$ Hadn't seen that, but it looks valid. You should perhaps mark it a bit more clearly. \$\endgroup\$ – marinus Nov 6 '14 at 13:16
5
\$\begingroup\$

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]
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ l~{_,g{('1=@(:Pa+@@P*+}*}*\; 28 and still scope for improvement (specially the (:P part), but time for lunch \$\endgroup\$ – Optimizer Oct 25 '14 at 11:39
  • \$\begingroup\$ @Optimizer Ah, good idea. Thank you. And yeah, the :P is also annoying me :D \$\endgroup\$ – Martin Ender Oct 25 '14 at 11:55
  • \$\begingroup\$ l~{_,g{(si@(:Pa+@@P*+}*}*\; : 27 and after looking into it, :P is actually efficient :P \$\endgroup\$ – Optimizer Oct 25 '14 at 11:56
  • \$\begingroup\$ _,g can also be replaced with _!! but same bytes. \$\endgroup\$ – Optimizer Oct 25 '14 at 11:58
  • \$\begingroup\$ @Optimizer I might as well use _{...}{}? then. \$\endgroup\$ – Martin Ender Oct 25 '14 at 12:01
2
\$\begingroup\$

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}

\$\endgroup\$
2
\$\begingroup\$

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]
\$\endgroup\$
  • 1
    \$\begingroup\$ Surely it's shorter to use a lambda and just write g and w for x? Also, I think g*w should work to give a truthy value when both g is nonzero and w is nonempty. \$\endgroup\$ – xnor Oct 27 '14 at 6:45
  • \$\begingroup\$ Also, I don't understand the inner if x else w. Won't x always be true because this code is only run if x, or am I missing something? \$\endgroup\$ – xnor Oct 27 '14 at 6:52
  • \$\begingroup\$ @xnor Surely, you are entirely correct :) \$\endgroup\$ – FryAmTheEggman Oct 27 '14 at 12:44
  • 1
    \$\begingroup\$ Some more golfing with the and/or trick and rotating p instead of incrementing n: c=lambda p,w,g:g*w and c(p[1:]+p[:1],w[1:]+w[0]*p[0],g-1)or w \$\endgroup\$ – xnor Oct 27 '14 at 18:34
  • \$\begingroup\$ @xnor Thanks :) Also, now that you made it a function of 3 variables, I think I translate it to Pyth... \$\endgroup\$ – FryAmTheEggman Oct 27 '14 at 19:20
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I actually deleted my post because I was getting different answers for the two examples. Have you tried the example where he goes generation by generation? It seems to be off by one compared to the full call example he gave... \$\endgroup\$ – FryAmTheEggman Oct 25 '14 at 3:28
  • \$\begingroup\$ And don't worry, I believe you didn't copy me :P \$\endgroup\$ – FryAmTheEggman Oct 25 '14 at 3:29
  • \$\begingroup\$ @FryAmTheEggman: Mine consistently generates the "before" column for the numbered generation. This is consistent with the example in the OP, and it seems logical that "generation 0" would simply return the input without processing it, which is consistent with this interpretation. Incidentally, I added the "copy" disclaimer because the solutions were uncannily similar in some respects. We used the same argument names, the same basic recursive structure, and we even added the same phantom fourth argument, n. Great minds, eh? :D \$\endgroup\$ – COTO Oct 25 '14 at 3:39
  • \$\begingroup\$ Ok, I guess if either of us is wrong, we're both wrong! United we stand. \$\endgroup\$ – FryAmTheEggman Oct 25 '14 at 3:48
  • \$\begingroup\$ @FryAmTheEggman: You weren't wrong about Mr. Peppe. ;) \$\endgroup\$ – COTO Oct 25 '14 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.