15
\$\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\$
4
  • \$\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\$ Oct 25, 2014 at 2:44
  • \$\begingroup\$ Can we take the input in a different order? \$\endgroup\$ Oct 25, 2014 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, 2014 at 6:08
  • \$\begingroup\$ @MartinBüttner: as long as you specify the order, it does not matter. \$\endgroup\$
    – marinus
    Oct 27, 2014 at 6:08

6 Answers 6

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\$
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\$
3
  • \$\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, 2014 at 12:15
  • \$\begingroup\$ @marinus, do you accept the 17 byte version I refer to in the text of my answer? \$\endgroup\$ Nov 6, 2014 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, 2014 at 13:16
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\$
6
  • 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, 2014 at 11:39
  • \$\begingroup\$ @Optimizer Ah, good idea. Thank you. And yeah, the :P is also annoying me :D \$\endgroup\$ Oct 25, 2014 at 11:55
  • \$\begingroup\$ l~{_,g{(si@(:Pa+@@P*+}*}*\; : 27 and after looking into it, :P is actually efficient :P \$\endgroup\$
    – Optimizer
    Oct 25, 2014 at 11:56
  • \$\begingroup\$ _,g can also be replaced with _!! but same bytes. \$\endgroup\$
    – Optimizer
    Oct 25, 2014 at 11:58
  • \$\begingroup\$ @Optimizer I might as well use _{...}{}? then. \$\endgroup\$ Oct 25, 2014 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\$
0
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\$
8
  • 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, 2014 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, 2014 at 6:52
  • \$\begingroup\$ @xnor Surely, you are entirely correct :) \$\endgroup\$ Oct 27, 2014 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, 2014 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\$ Oct 27, 2014 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\$
5
  • \$\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\$ Oct 25, 2014 at 3:28
  • \$\begingroup\$ And don't worry, I believe you didn't copy me :P \$\endgroup\$ Oct 25, 2014 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, 2014 at 3:39
  • \$\begingroup\$ Ok, I guess if either of us is wrong, we're both wrong! United we stand. \$\endgroup\$ Oct 25, 2014 at 3:48
  • \$\begingroup\$ @FryAmTheEggman: You weren't wrong about Mr. Peppe. ;) \$\endgroup\$
    – COTO
    Oct 25, 2014 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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