Implement a 2-tag system simulator

Question

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)
    if not P.hasKey(cur):
      break
    str.add(P[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)

Answer 1

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

Answer 2

05AB1E, 20 19 bytes

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

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.

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

Answer 3

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!

Answer 4

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

Answer 5

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!

Answer 6

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.

Explanation

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

Answer 7

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

Answer 8

JavaScript (Node.js), 48 bytes

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

Try it online!

Answer 9

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.