To quote http://brainfuck.org/utm.b:

A tag-system transforms strings over an alphabet A = {a[1], a[2], ... a[n], a[n+1]} as follows: a positive integer m is chosen, and so is a function P that maps each a[i] for 1<=i<=n to a string P(a[i]) over the alphabet A. Now:

  1. if the string being transformed has fewer than m elements, the whole process stops now.
  2. m elements are removed from the beginning of the string
  3. Call the first element removed a[k]; if k=n+1 the whole process stops now.
  4. P(a[k]) is appended to the string.
  5. steps 1-5 are repeated.

A more extensive definition is at https://en.wikipedia.org/wiki/Tag_system.

We will call a[n + 1] the "Halting symbol". Alphabet symbols (symbols in a) are ASCII alphanumeric chars.

2-tag systems are those where m=2.

The simulator should take two inputs.

  1. A definition for P, which doubles as a definition for the alphabet. The definition format is given below.
  2. An "initial word" to be transformed.

If it halts, it should output the "halting word", the word that is shorter then 2 alphabet symbols long or which has the halting symbol in its front.


If possible, the input should be read from stdin or passed to a function in the following format (Or something equivalent).

symbol:listofsymbols symbol:listofsymbols symbol:listofsymbols [and so on]

The listofsymbols may be assumed to contain only valid symbols. Any symbol that is not explicitly defined should be treated as the halting symbol.

The test cases (from Wikipedia) are:

  a:bc b:a c:aaa

  a:ccbaH b:cca c:cc
#This test case uses H as the halting symbol, but it might as well be using any alphanumeric ASCII char other than the defined a, b, and c.

Example implementation in Nim:

import tables, strutils
proc runTag(P: Table[char, string], inputstr: string): string =
  var haltingword: string;
  var str = inputstr
  while true:
    haltingword = str
    if str.len() < 2:
    var cur = str[0]
    if not P.hasKey(cur):
  return haltingword

var ruleinput = readLine(stdin).split(' ')
var rules: Table[char, string]
for i in ruleinput:
  var pair = i.split(':')
  rules[pair[0][0]] = pair[1]
var str = readLine(stdin)

echo runTag(P=rules, inputstr=str)
  • 1
    \$\begingroup\$ Are the : essential (could we take abc ba caaa for example)? Could we just take say, [['a', "bc"], ['b', "a"], ['c', "aaa"]] and equivalents? \$\endgroup\$ Commented Sep 12, 2021 at 17:00
  • 2
    \$\begingroup\$ Also, may languages with maps/dictionaries take these as input? \$\endgroup\$ Commented Sep 12, 2021 at 17:04
  • 3
    \$\begingroup\$ Yes, and yes. The point is (when reading from stdin) to present it in a format similar to the one shown. The details are not to relevant. I will clarify. \$\endgroup\$
    – Qaziquza
    Commented Sep 12, 2021 at 17:14

9 Answers 9


Python 3.8 (pre-release), 56 bytes

f=lambda a,d:a[:len(a)>1]in d and f(a[2:]+d[a[0]],d)or a

Try it online!

-4 thanks to @JonathanAllan

-3 thanks to @Neil

Normal recursive approach

Takes a string and a dictionary of transformations

  • \$\begingroup\$ ~-len(a)and a[0]in d could be golfed to either a[:len(a)>1]in d or a[:a[1:]>'']in d both of which shave off four bytes. \$\endgroup\$ Commented Sep 13, 2021 at 9:19
  • \$\begingroup\$ @JonathanAllan thanks !! \$\endgroup\$
    – Wasif
    Commented Sep 13, 2021 at 16:49
  • 1
    \$\begingroup\$ Do you need the a:=? \$\endgroup\$
    – Neil
    Commented Oct 1, 2021 at 14:09
  • \$\begingroup\$ Oh I didn't need the walrus, nice catch @Neil!!! \$\endgroup\$
    – Wasif
    Commented Oct 1, 2021 at 14:12

05AB1E, 20 19 bytes


Inputs in the order string, map, where the map are key-value pairs as space-delimited strings.

Try it online or verify both test cases.


[               # Start an infinite loop:
 D              #  Duplicate the current string (or the implicit first input-string in
                #  the first iteration)
  g             #  Pop and get its length
   #            #  If its length is 1: stop the infinite loop
                #  (after which the duplicated string is output implicitly as result)
   ¬            #  Else: get the first character (without popping the string)
    U           #  Pop and store this head in variable `X`
     I          #  Push the second input-list of pairs
      .Δ        #  Find the first which is truthy for:
        н       #   Where its first item (the key)
         XQ     #   Equals head `X`
       }        #  Close the find-first (this will result in -1 if none were found)
        Ä       #  Get the absolute value (no-op for a pair of strings)
         #      #  If this is 1: stop the infinite loop
                #  (after which the string is output implicitly as result)
         #      #  Else: the `#` will act as a 'split-on-spaces' instead
          θ     #  Pop and leave last item (the value)
           «    #  Append it to the string
            ¦¦  #  And remove the first two characters

PowerShell Core, 68 60 bytes

for($a,$d=$args;$a[1]-and($u=$d[$a[0]])){$a=$a+$u|% Su* 2}$a

Try it online!

Takes two parameters:

  • the string to process
  • a dictionary of char / strings


for($a,$d=$args;   # Sets the variables $a, the string to process and $d the dictionary of transformations
$a[1]-and          # While there is more than 1 character left
($u=$d[$a[0]])){   # And there is a transformation for the first character of $a, store the transformation in $u
$a=$a+$u|% Su* 2}  # Concatenates $a and $u and takes all the characters from the second position
$a                 # return $a when it is 1 char long or we hit a halting symbol

-2 bytes thanks to wasif!
-6 bytes thanks to Zaelin Goodman!

  • 2
    \$\begingroup\$ -2 bytes \$\endgroup\$
    – Wasif
    Commented Sep 13, 2021 at 4:25
  • 1
    \$\begingroup\$ Ah yeah! The length will never be 0, good find @wasif! \$\endgroup\$
    – Julian
    Commented Sep 13, 2021 at 5:06
  • 3
    \$\begingroup\$ -6 bytes? \$\endgroup\$ Commented Sep 13, 2021 at 20:02
  • 2
    \$\begingroup\$ Nice one @ZaelinGoodman, I didn't think this would not raise an error! \$\endgroup\$
    – Julian
    Commented Sep 13, 2021 at 20:55

Jelly, 29 bytes

Feels clunky to me at present.


A dyadic Link that accepts the initial word on the left and the production rules (\$P\$) on the right and yields the result.

Try it online! (Each production rule is [chr, [chr, ...]], but a list of these cannot be passed as an argument to a program so the footer translates them from a list of [[chr], [chr, ...]])


ZḢiȧị¥⁸0ị - Link 1, get new characters (or zero): rules, R; character, C
Z         - transpose (R)
 Ḣ        - head -> alphabet
  i       - first 1-indexed index of (C) in (alphabet) or, when C=Halt, zero
     ¥⁸   - last two links as a dyad, f(I=that, R)
    ị     -   (I) index into (R)
   ȧ      -   (I) logical AND (that) -> relevant rule or zero
       0ị - tail -> new characters or zero

;1ịç@ɗ¥⁹ḊḊʋḊȦ$¡ƬẠƇṪ - Link: initial word, W; rules, R
               Ƭ    - collect up, starting with W, while no duplicates found with:
              ¡     -   repeat...
             $      -   ...number of times: last two links as a monad, f(current):
           Ḋ        -     dequeue
            Ȧ       -     has elements and none are zero (found when processing a halt)
          ʋ         -   ...what: last four links as a dyad, f(current, R)
       ⁹            -     right argument, R
      ¥             -     last two links as a dyad, f(current, R)
     ɗ              -       last three links as a dyad, f(current, R)
 1                  -         one
  ị                 -         index into (current) -> head character
   ç@               -         call Link 1 as a dyad, f(R, character)
;                   -       (current) concatenate (that)
        Ḋ           -     dequeue
         Ḋ          -     dequeue
                 Ƈ  - keep those for which:
                Ạ   -   all truthy (are not the result of processing a halt)
                  Ṫ - tail

Python 3, 56 bytes

def f(a,d):

Try it online!

This function take input as a list of chars, and a dict of char to list of chars. And it returns by modify a in-place.

And if terminating the function by an exception is allowed, it could be even shorter:

Python 3, 40 bytes

def f(a,d):x,y,*z=a;a[:]=*z,*d[x];f(a,d)

Try it online!


Pip, 27 bytes

W#Sb&[email protected] KXWb:b@>2.$1b

Try it here! Or, here's a 28-byte equivalent in Pip Classic: Try it online!

The tag definitions and the initial word are taken as command-line arguments. Each definition is given as alphabet symbol + space + string, and definitions are separated by any non-space non-alphanumeric symbol. For example:

a bc;b a;c aaa

This will need to be quoted so the command-line treats it as a single argument.


W#Sb&[email protected] KXWb:b@>2.$1b
                             ; a, b are cmdline args; s is space; XW is `\w` (implicit)
W                            ; While
 #                           ;  length of
  Sb                         ;  longest suffix of b (the current word)
                             ;  is nonzero (i.e. length of b is at least 2)
    &                        ; and
       @b                    ;  first character of b
         .s                  ;  concatenated to a space
           .                 ;  concatenated to the following regex...
               XW            ;   word character: \w
              K              ;   with Kleene star operator: \w*
            C                ;   wrapped in a capture group: (\w*)
     a~                      ;  matches somewhere in a (the definitions)
                             ; do:
                 b:          ;   Assign to b
                   b@>2      ;   all but the first two characters of b
                       .$1   ;   concatenated to the contents of the regex capture group
                          b  ; Output the final value of b

jq, 62 bytes

.P as$P|.w|until(length<2//(.[:1]|in($P)|not);.[2:]+$P[.[:1]])

Takes input as a JSON object with keys P and w. The value of P is an object whose keys are alphabet symbols and whose values are their associated strings. The value of w is the initial word. Try it online!


.P as $P |    Store the P mapping in the variable $P
.w |          The rest of the program will manipulate the input word
until (       Until this condition is true...
  length < 2    The length of the word is less than 2
  // (          or:
    .[:1] |       The first character of the word
    in($P) |      Is a key in $P
    not)          Make that "is NOT a key in $P"
  ;           ...update the word to be the following:
  .[2:] +       The word minus its first two characters, plus
  $P[           the value in $P at this key:
    .[:1]         The first character in the word
              When the loop exits, return the final value of the word

JavaScript (Node.js), 48 bytes


Try it online!


Charcoal, 35 bytes


Try it online! Link is to verbose version of code. Takes input as the string to be transformed followed by a list of transformations in the form symbol:stringofsymbols. Explanation:


Input the string to be transformed.


Input the list of transformations.


Repeat while the string is longer than a single character and the first character is the first character of one of the transformations.


Remove the first two characters from the string and the matching transformation and concatenate the result.


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.