# Implement a 2-tag system simulator

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.

## IO

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]
initialword

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:

input:
a:bc b:a c:aaa
aaaa
output:
a

input:
a:ccbaH b:cca c:cc
baa
output:
Hcccccca
#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:
break
var cur = str[0]
str.delete(0..1)
break
return haltingword

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

echo runTag(P=rules, inputstr=str)

• Are the : essential (could we take abc ba caaa for example)? Could we just take say, [['a', "bc"], ['b', "a"], ['c', "aaa"]] and equivalents? Sep 12, 2021 at 17:00
• Also, may languages with maps/dictionaries take these as input? Sep 12, 2021 at 17:04
• 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. Sep 12, 2021 at 17:14

# 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

• ~-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. Sep 13, 2021 at 9:19
• @JonathanAllan thanks !! Sep 13, 2021 at 16:49
• Do you need the a:=?
– Neil
Oct 1, 2021 at 14:09
• Oh I didn't need the walrus, nice catch @Neil!!! Oct 1, 2021 at 14:12

# 05AB1E, 20 19 bytes

[Dg#¬UI.ΔнXQ}Ä#θ«¦¦


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

Explanation:

[               # 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 ### Explanations 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 bytes Sep 13, 2021 at 4:25 • Ah yeah! The length will never be 0, good find @wasif! Sep 13, 2021 at 5:06 • -6 bytes? Sep 13, 2021 at 20:02 • Nice one @ZaelinGoodman, I didn't think this would not raise an error! Sep 13, 2021 at 20:55 # Jelly, 29 bytes Feels clunky to me at present. ZḢiȧị¥⁸0ị ;1ịç@ɗ¥⁹ḊḊʋḊȦ$¡ƬẠƇṪ


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

### How?

ZḢiȧị¥⁸0ị - Link 1, get new characters (or zero): rules, R; character, C
Z         - transpose (R)
i       - first 1-indexed index of (C) in (alphabet) or, when C=Halt, zero
ị     -   (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)
⁹            -     right argument, R
1                  -         one
ị                 -         index into (current) -> head 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:x,y,*z=a;a[:]=*z,*d[x];f(a,d)
except:0


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&a~@b.s.C 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. ### Explanation W#Sb&a~@b.s.C 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!

### Explanation

.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

p=>g=a=>p[[x,y,...z]=a,x]&&y?g([...z,...p[x]]):a


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.