解读树语

Question

概述

Shue (Simplified )是AnttiP为这一挑战设计的一种语言。Shue程序由可能的输出和字符串替换列表组成。例如，如果一元字符串是偶数，下面的程序会打印"yes“：

yes
no
11=2
12=1
22=2
1=no
2=yes

在网上试试！

这里可能的产出分为“是”和“否”。接下来是替换名单。在这里，"11“改为"2"，"22”改为"2"，"12“改为"1"，"1”改为“否”，"2“改为”是“。所有的替换都是不确定的。一旦程序达到一个状态，其中一个替换是输出，它终止和打印输出。

树的

精确定义

复制自最初的post

源代码被解释为字节列表。唯一有特殊意义的字符是换行符、等号和反斜杠。\n对应于文字换行符，\=对应于文字等号，\\对应于文字反斜杠。\的任何其他使用都是一个错误。每一行必须包含0或1未转义的等号。

换句话说，要使程序在语法上有效，程序必须匹配以下正则表达式：/([^\n=\\]|\\=|\\n|\\\\)*(=([^\n=\\]|\\=|\\n|\\\\)*)?(\n([^\n=\\]|\\=|\\n|\\\\)*(=([^\n=\\]|\\=|\\n|\\\\)*)?)*/

以下是Shue程序的数学定义：

Shue程序是一组终止符字符串T_e，以及一组转换规则T_r，它们是一对字符串。

在输入字符串i上执行Shue程序的定义如下。设U是最小集，因此i\in U和\forall a,x,y,b: axb \in U \land (x,y) \in T_r \rightarrow ayb \in U。让S=U\cap T_e。

如果是S=\{x\}，那么程序将终止，x将被打印到stdout。

如果是S=\emptyset和|U|=\aleph_0，那么程序将进入无限循环。

在所有其他情况下，行为都是未定义的(是的，Shue并不是内存安全的)。

但是，由于大多数esolangs不能处理字节数组，所以可以将字符串或行列表作为输入。请参阅链接的原始挑战，以获得更好的定义和更多的示例。

参考实现

下面是Python参考实现：

import re, sys
re1 = re.compile(rb"(([^=]|\\=)*)(=([^=]|\\=)*)?")

def unescape(i):
    ret = b""
    esc = 0
    for c in i:
        if esc and c == b"\\":
            ret+= b"\\"
            esc = 0
        elif esc and c == b"=":
            ret+= b"="
            esc = 0
        elif esc and c == b"n":
            ret+= b"\n"
            esc = 0
        elif esc:
            raise ValueError(f"Parser error: got character {c} after \\")
        elif c == b"\\":
            esc = 1
        else:
            ret+= bytes([c])
    if esc:
        raise ValueError(f"Parser error: got EOL/EOF after \\")
    return ret


def parse(i):
    terminators = set()
    rules = set()
    lines = i.split(b"\n")
    for l in lines:
        m = re1.match(l)
        if m.group(3):
            rules|= {(unescape(m.group(1)), unescape(m.group(3)[1:]))}
        else:
            terminators|= {unescape(m.group(1))}
    return terminators, rules

def execute(c, i):
    terms, rules = parse(c)
    universe = {i}
    mod = True
    while mod:
        mod = False
        new_universe = set()
        for s in universe:
            if s in terms:return s
        for s in universe:
            for a,b in rules:
                for o in range(len(s)+1):
                    if s[o:o+len(a)] == a:
                        new_universe|= {s[:o]+b+s[o+len(a):]}
                        mod = True
        universe = new_universe
    raise ValueError(f"Program error: no replacements are possible (undefined behaviour)")


code = input().encode()
inp = sys.stdin.read().encode()

res = execute(code, inp)
print(res.decode())

规则

• 标准漏洞被禁止。
• 您可以将输入作为字节列表、单个字符串或行列表。
• 由于这是密码-高尔夫，以字节为单位的最短程序将获胜。

Answer 1

Python3,264个字节：

lambda x,y:next(M(x,p(y)))
def M(s,g):
 if s in g[0]:yield s
 for a,b in g[1]:
  for i in range(len(s)):
   if a==s[i:i+len(a)]:yield from M(s[:i]+b+s[i+len(a):],g)
def p(s):
 d={}
 for i in s.split('\n'):d[c]=d.get((c:='='in i),[])+[[i,i.split('=')][c]]
 return d

在网上试试！