查看“︁iBLP”︁的源代码

== 记号简介 ==
无限基本Laver图案(Infinite Basic Laver Pattern)是由test_alpha0的记号Basic Laver Pattren改造而来。IBLP目前尚不理想，还存在许多的坏图案。test_alpha0规定其极限表达式为(1,0)1(2,1,0)1(3,2,1,0)2(4,3,2)1(5,4,3,2)2(6,5,4)1，因为现在认为在该图案下方不存在坏图案，而其上方不远处就出现了很多坏图案。尽管如此，IBLP仍然被认为是目前最强的记号。本页面介绍的规则对应[https://hypcos.github.io/notation-explorer/ NE]上的DEN2。

== 定义 ==

=== 定义1 （IBLP） ===
一个IBLP是一个四元组<math>A=(n,(A_1,\dots,A_n),(l_1,\dots,l_n),(M_1,\dots,M_n))</math>，

其中：

<math>(1)n\in\N</math>。

<math>(2)</math>对每个<math>i\in\{1,\dots,n\}</math>，<math>A_i</math>是严格递增的非负整数序列，满足<math>\mathrm{len}(A_i)\geq2\text{且}\max(A_i)=i</math>。

<math>(3)</math>对每个<math>i\in\{1,\dots,n\}</math>，步长<math>l_i\in \N</math>。

<math>(4)</math>对每个<math>i\in\{1,\dots,n\}</math>，标记集合<math>M_i\subseteq A_i</math>

约定所有编号从 1 开始；<math>A_i[k]</math> 表示第 ''k'' 个元素，<math>A_i[-j]=A_i[\mathrm{len}(A_i)-j+1]</math>表示倒数第 ''j'' 个元素。

=== 定义2 （长行、中等行、短行） ===
行 <math>i</math> 称为长行若<math>\mathrm{len}(A_i)>2l_i</math>，称为中等行若<math>\mathrm{len}(A_i)=2l_i</math>，称为短行若 <math>\mathrm{len}(A_i)<2l_i</math>。

=== 定义3 （零图案、后继图案、极限图案） ===
若 ''n'' = 0，称 ''A'' 为零图案。若 <math>n>0\text{且}\mathrm{len}(A_n)=2\text{且}\min(A_n)=0</math>，称 ''A'' 为后继图案。否则称 ''A'' 为极限图案。

=== 定义4 （行比较键） ===
令<math>A_i=(A_1<a_2<\dots<a_m)\text{且}L=l_i</math>。定义保留序列

<math>K_i=\begin{cases}(a_1,a_2,\dots,a_m),&L\leq1;\\(a_1,a_{L+1},a_{L+2},\dots,a_m),&2\leq L\leq m;\\(a_1,a_2,\dots,a_m),&L\geq2\text{且}m<L.\end{cases}</math>

定义行键为<math>\overleftarrow{K_i}</math>（即<math>K_i
</math>逆序，从大到小）。

=== 定义5 （IBLP的大小比较） ===
给定两个 ''IBLP'' <math>A\text{、}B</math>，从 <math>i=1</math> 起逐行比较其

行键<math>\overleftarrow{K_i(A)}\text{与}\overleftarrow{K_i(B)}</math> 的字典序；第一处不同决定大小。若前<math>\min(n_a,n_b)</math>行都相等，则行数较小者更小。

=== 定义6 （一行的根<math>p(i)</math>） ===
对<math>i\in\{1,\dots,n\}</math>，定义<math>p(i)=A_i[-(l_i+1)]</math>.

=== 定义7 （传递序列<math>tr_i(j)</math>） ===
固定行 ''i''。若<math>j=A_i[k](1\leq k\leq\mathrm{len}(A_i))\text{且}k\geq l_i</math>，定义阈值 <math>\theta=A_i[k-l_i]</math>。令 <math>t_0=j</math>，并在<math>t_m>\theta\text{且}p(t_m)\text{有定义}</math>时令 <math>t_{m+1}=p(t_m)</math>。若存在最小 <math>m>0</math>使<math>t_m=\theta</math>，则定义<math>tr_i(j)=(t_0,t_1,\dots,t_m)</math>''，''否则称 <math>tr_i(j)</math> 无定义。若 <math>k\leq l_i</math>，亦称无定义。

=== 定义8 （部分函数<math>f_A</math>） ===
设 ''A'' 非零且有至少1行。令 <math>a_1=A_n[1]=\min(A_n)\text{，}L=l_n\text{，}p=p(n)=A_n[-(L+1)]</math>。定义部分函数 <math>f_A:\N\rightharpoonup\N</math>：

<math>(1)</math>若<math>x<a_1</math>，则<math>f_A(x)=x</math>；

<math>(2)</math>若<math>x=A_n[k]\text{且}x<p\text{且}k+L\leq\mathrm{len}(A_n)</math>，则<math>f_A(x)=A_n[k+L]</math>；

<math>(3)</math>若<math>x\geq p</math>，则<math>f_A(x)=x+n-p</math>；

<math>(4)</math>其余情形 <math>f_A(x)</math> 无定义。

=== 定义9 （copy 的行与步长） ===
设 ''A'' 行数为<math>n\geq1</math>，令 <math>p=p(n)</math>。若 copy 过程中出现 <math>f_A(x)</math> 无定义，则<math>copy(A)</math>无定义。否则定义 <math>A'=copy(A)</math> 行数为 <math>n'=2n-p</math>，满足：

<math>(1)</math>对<math>1\leq i\leq n-1\text{：}A_i'=A_i\text{，}l_i'=l_i\text{，}M_i'=M_i</math>；

<math>(2)</math>对每个<math>i\in\{1,\dots,n-p+1\}</math>，令源行<math>\sigma=p+i-1</math>，目标行<math>\tau=n-1+i</math>''i''，定义<math>A_\tau'=\mathrm{sort}(\{f_A(x)|x\in A_\sigma\})\text{，}l_\tau'=l_\sigma</math>，要求<math>\forall x\in A_\sigma\text{，}f_A(x)\text{有定义}</math>。

=== 定义10 （copy的标记过滤） ===
延续上一定义。对目标行<math>\tau</math>中元素<math>x\in A_\tau'</math>，令

<math>y\in A_\sigma</math>为其唯一来源（即 <math>f_A(y)=x</math>）。则 <math>x\in M_\tau'</math> 当且仅当：

<math>y\in M_\sigma</math>，并且满足下列之一：

* <math>tr_\sigma(y)</math>有定义且<math>tr_\sigma(y)[-2]\geq p</math>；
* 令<math>y_0</math>为<math>tr_\sigma(y)</math>中首次出现的<math><p</math>的元素（等价于“最大的
<math><p</math>的元素”）。要么<math>y_0<a_1</math>；要么存在 ''k'' 使<math>y_0=A_n[k]\text{且}k+L\leq\mathrm{len}(A_n)\text{且}A_n[k+L]\in M_n</math>，并且若 ''x'' 在 <math>A_\tau'</math>中的位置  为 ''q''（从 1 开始），则当 <math>q+1-l_\sigma\geq1</math> 时需满足<math>A_\tau'[q+1-l_\sigma]\leq a_1.</math>

=== 定义11 （E(A,0)） ===
若 ''A'' 非零且 ''n ≥'' 1，则 ''E''(''A,'' 0) 为删除最后一行后的图案（行数变为 ''n −'' 1，其余行、步长、标记保持不变）。

=== 定义12 （''E''(''A, m'')的copy阶段 (''m≥1)''） ===
设A是极限图案。令<math>A^{(0)}=A</math>。若第一次<math>copy(A^{(0)})</math> 无定义，则称 ''A'' 为坏图案并定义<math>E(A,m)=E(A,0)</math>。否则定义

<math>A^{(1)}=copy(A^{(0)}),A^{(2)}=copy(A^{(1)}),\dots,A^{(m)}=copy(A^{(m-1)})</math>,

并令<math>B=E(A^{(m)},0)</math>

接下来对B做补全，初始行号 <math>r=n</math>（这里 ''n'' 为原始 ''A'' 的行数）。补全过程允许使用临时记录映射 <math>\rm Rec</math>（行号 <math>\mapsto</math> 有限序列），结束后丢弃。

=== 定义13 （标记补全） ===
固定当前行 ''r''。令<math>\mathcal{B}=\{b\in M_r|b\in A_r\}</math>并按升序枚举其元素<math>b_1<b_2<\dots<b_k</math>（该集合在本轮开始时冻结，新产生标记不加入本轮）。对每个 <math>b_i</math>依次：

<math>(1)</math>若 <math>tr_i(b_i)</math>无定义则跳过；

<math>(2)</math>令<math>t=tr_r(b_i)[-2]</math>。若<math>\mathrm{Rec}(t)</math>不存在或为空则跳过，否则记 <math>s=\mathrm{Rec}(t)</math>；

<math>(3)</math>若对所有<math>j=3,4,\dots,\mathrm{len}(tr_r(b_i))</math>都有<math>tr_r(b_i)[-j+1]+1\in A_{tr_r(b_i)[-j]}</math>，那么把s 及<math>b_i+1,b_i+2,\dots,b_i+\mathrm{len}(s)</math> 加入 <math>A_r</math>，并重新排序去重使

之严格递增。更新标记：''s'' 中元素不标记，<math>b_i+1,b_i+2,\dots,b_i+\mathrm{len}(s)</math> 全标

记，其余标记保留（按上述规则修正）。更新步长：<math>l_r=l_r+len(s)</math>。

=== 定义14 （原生补全） ===
固定当前行 ''r''。若<math>A_r</math>为长行，则原生补全不执行并返回 0。否则令<math>p_r=p(r)=A_r[-(l_r+1)]\text{，}a=A_r[-l_r]</math>.

构造序列 ''s''：令 <math>u_0=a</math>，并在<math>A_{u_m}[-2]</math> 存在且 <math>>p_r</math> 时令 <math>u_{m+1}=A_{u_m}[-2]</math>并把 <math>u_{m+1}</math> 追加到 ''s''，直至无法继续。令 <math>t=\mathrm{len}(s)</math>。若 <math>t=0</math> 返回 0；若<math>t>0</math>，令 <math>\mathrm{Rec}(r)=s</math> 并继续：

<math>(1)</math>在 ''r'' 后插入 ''t'' 行，使原本行号 <math>>r</math> 的行号整体加 ''t''；

<math>(2)</math> 仅对原本行号 <math>>r</math>的那些行，在其中把所有 <math>>r</math> 的元素加 ''t''，并同步

标记集合，步长不变；

<math>(3)</math>令旧行及旧步长为 <math>A_r^{old},l_r^{old}</math>。将旧行替换为 ''t'' + 1 行：

<math>A_{r+t}=\mathrm{sort}(A_r^{old}\cup s\cup\{r+1,r+2,\dots,r+t\})\text{，}l_{r+t}=l_r^{old}+t</math>.

标记规则：除s和r+t外均标记。

<math>(4)</math>对<math>i=t,t-1,\dots,1</math>，由<math>A_{r+i}</math>构造 <math>A_{r+i-1}</math>：删除元素<math>r+i</math>，并删除元素 <math>A_{r+i}[-l_{r+i}]</math>，去除<math>r+i-1</math> 的标记，并令 <math>l_{r+i-1}=l_{r+i}-1</math>。

<math>(5)</math>'''中等行例外：'''若<math>i=t</math> 且 ''<math>A_r^{old}</math>''为中等行，则在构造 <math>A_{r+i-1}</math> 时不删除 <math>A_{r+i}[-l_{r+i}]</math>且不减步长（令 <math>l_{r+i-1}=l_{r+i}</math>），但仍删除 <math>r+i</math> 并去除<math>r+i-1</math> 的标记。

原生补全返回t。

=== 定义15 （补全主循环(用于 ''E''(''A, m''))） ===
令初始<math>r=n</math>（''n'' 为原始 ''A'' 的行数）。当 ''r'' 不超过当前 ''B'' 的行数时循环：先对行 ''r'' 执行标记补全，再执行原生补全得到 ''t''，然后更新 <math>r=r+t+1</math>。当 ''r'' 越界时补全结束，丢弃 <math>\rm Rec</math>，所得 ''B'' 即为<math>E(A,m)</math>。

== 展开器 ==
iblp的展开器在[https://hypcos.github.io/notation-explorer/ NE]上可以找到，同时也可以使用如下Python代码直观地看到每个图案的行为。<syntaxhighlight lang="python3">
import bisect


def _clone_rows(rows):
    return [row[:] for row in rows]


def _clone_mask(mask):
    return [set(s) for s in mask]


def _find_index(sorted_row, val):
    i = bisect.bisect_left(sorted_row, val)
    if i < len(sorted_row) and sorted_row[i] == val:
        return i
    return None


def _shift_sorted_row_inplace(sorted_row, threshold, delta):
    if delta == 0:
        return
    i = bisect.bisect_left(sorted_row, threshold)
    for j in range(i, len(sorted_row)):
        sorted_row[j] += delta


def _shift_mark_set(mark_set, threshold, delta):
    if delta == 0 or not mark_set:
        return mark_set
    new = set()
    for x in mark_set:
        new.add(x + delta if x >= threshold else x)
    return new


class ModifyUnpleasant(Exception):
    pass


MSG_UNPLEASANT = (
    "Something unpleasant happened. Please contact the author (E-mail: qwerasdfyh@126.com) "
    "about the previous pattern so he can improve the rule design."
)


class BasicLaverPattern:
    def __init__(self, rows, mask=None):
        self.rows = _clone_rows(rows)
        if mask is None:
            self.mask = [set() for _ in self.rows]
        else:
            self.mask = _clone_mask(mask)
        if self.mask:
            self.mask[0] = set()
        self._normalize_rows_inplace()

    def _normalize_rows_inplace(self, start_row=1):
        for r in range(max(1, start_row), len(self.rows)):
            row = self.rows[r]
            if row and row[-1] == r + 1:
                row.pop()
                self.mask[r].discard(r + 1)

    def clone(self):
        return BasicLaverPattern(self.rows, self.mask)

    def is_zero(self):
        return len(self.rows) == 1 and len(self.rows[0]) == 0

    def is_successor(self):
        if self.is_zero():
            return False
        last = self.rows[-1]
        return len(last) == 2 and last[0] == 0

    def draw(self):
        if self.is_zero():
            return
        base_list = self.rows[0]
        other_lists = self.rows[1:]
        if not other_lists:
            return
        max_len = max((seq[-1] for seq in other_lists if seq), default=0) + 1
        result = []
        for i, seq in enumerate(other_lists, start=1):
            line = [' '] * max_len
            mset = self.mask[i]
            for num in seq:
                if 0 <= num < max_len:
                    line[num] = 'a' if num in mset else 'o'
            if i <= len(base_list) and seq:
                last_circle_index = seq[-1]
                result.append(''.join(line[:last_circle_index + 1]) + f" {base_list[i-1]}")
        for line in result:
            print(line)

    def to_string(self):
        if self.is_zero():
            return ""
        base_list = self.rows[0]
        out = []
        for i in range(1, len(self.rows)):
            seq = self.rows[i]
            mset = self.mask[i]
            parts = []
            for x in reversed(seq):
                parts.append(f"*{x}" if x in mset else str(x))
            step = base_list[i - 1] if i - 1 < len(base_list) else 0
            out.append("(" + ",".join(parts) + ")" + str(step))
        return "".join(out)

    def cut(self):
        if self.is_zero():
            return False
        if len(self.rows) <= 1:
            return False
        if len(self.rows[0]) == 0:
            self.rows = [[]]
            self.mask = [set()]
            return False
        self.rows[0].pop()
        self.rows.pop()
        self.mask.pop()
        if len(self.rows) == 1 and len(self.rows[0]) == 0:
            self.mask = [set()]
        self._normalize_rows_inplace()
        return True

    def _transmission_penultimate_and_terminal_checked(self, row_idx, n_value):
        rows = self.rows
        base = rows[0]
        if n_value <= 0 or n_value >= len(rows):
            return None
        row = rows[row_idx]
        l_m = base[row_idx - 1]
        k = _find_index(row, n_value)
        if k is None or k - l_m < 0:
            return None
        threshold = row[k - l_m]

        cur = n_value
        visited = {cur}
        while True:
            if cur <= 0 or cur >= len(rows):
                return None
            l_s = base[cur - 1]
            if len(rows[cur]) < l_s + 1:
                return None
            nxt = rows[cur][-l_s - 1]
            if nxt > threshold:
                if nxt + 1 != cur + 1:
                    if _find_index(rows[cur], nxt + 1) is None:
                        return None
            prev, cur = cur, nxt
            if cur <= threshold:
                return (prev, cur)
            if cur in visited:
                return None
            visited.add(cur)

    def _first_not_copied_in_transmission(self, orig_rows, orig_base, copied_set, row_idx, n_value):
        row = orig_rows[row_idx]
        l_m = orig_base[row_idx - 1]
        k = _find_index(row, n_value)
        if k is None or k - l_m < 0:
            raise RuntimeError("Unpleasant.")
        threshold = row[k - l_m]
        cur = n_value
        seq = [cur]
        visited = {cur}
        while True:
            l_s = orig_base[cur - 1]
            if len(orig_rows[cur]) < l_s + 1:
                raise RuntimeError("Unpleasant.")
            nxt = orig_rows[cur][-l_s - 1]
            seq.append(nxt)
            cur = nxt
            if cur <= threshold:
                break
            if cur in visited:
                raise RuntimeError("Unpleasant.")
            visited.add(cur)
        t = seq[-2]
        terminal = seq[-1]
        tprime = None
        for x in seq:
            if x not in copied_set:
                tprime = x
                break
        return tprime, t, terminal

    def _slice_right_block(self, row_idx, anchor, q):
        row = self.rows[row_idx]
        pos = _find_index(row, anchor)
        if pos is None:
            raise RuntimeError("Unpleasant.")
        block = row[pos + 1: pos + 1 + q]
        if len(block) != q:
            raise RuntimeError("Unpleasant.")
        return block

    def _mark_completion_for_row(self, r, meta, native_done):
        base = self.rows[0]
        row0 = self.rows[r]
        initial_marks = [x for x in row0 if x in self.mask[r]]
        before = set(row0)
        added_total = 0

        for n in initial_marks:
            if _find_index(self.rows[r], n) is None:
                continue
            if n <= 0 or n >= len(meta):
                continue
            info = meta[n]
            if not info or not info.get("native_generated", False):
                continue

            tn = self._transmission_penultimate_and_terminal_checked(r, n)
            if tn is None:
                continue
            t, n_terminal = tn
            q = native_done.get(t, 0)
            if q <= 0:
                continue

            target_row = t + q
            left_block = self._slice_right_block(target_row, n_terminal, q)
            right_block = list(range(n + 1, n + q + 1))

            new_vals = set(left_block) | set(right_block)
            truly_new = new_vals - before
            if truly_new:
                added_total += len(truly_new)
                before |= truly_new

            row_set = set(self.rows[r])
            row_set.update(new_vals)
            self.rows[r] = sorted(row_set)

            self.mask[r].difference_update(left_block)
            self.mask[r].update(right_block)

        if added_total > 0:
            base[r - 1] += (added_total // 2)

    def _shift_values_ge(self, start_row_idx, threshold, delta):
        for i in range(start_row_idx, len(self.rows)):
            _shift_sorted_row_inplace(self.rows[i], threshold, delta)
            self.mask[i] = _shift_mark_set(self.mask[i], threshold, delta)

    def _native_completion_step(self, m, meta):
        rows = self.rows
        base = rows[0]
        l = base[m - 1]
        e = len(rows[m])

        if e > 2 * l:
            return False, 0

        if l <= 0 or e < l:
            return False, 0

        s = [rows[m][-l]]
        while True:
            if s[-1] <= 0 or s[-1] >= len(rows):
                return False, 0
            if len(rows[s[-1]]) < 2:
                return False, 0
            s.append(rows[s[-1]][-2])
            if len(rows[m]) < l + 1:
                return False, 0
            if s[-1] <= rows[m][-l - 1]:
                break

        k = len(s) - 1
        if k == 1:
            return False, 0
        s.pop()
        q = k - 1
        if q <= 0:
            return False, 0

        marks_m_orig = set(self.mask[m])
        self._shift_values_ge(m, m + 1, q)

        if e == 2 * l:
            c = rows[m][:]
        else:
            c = rows[m][:l - 1] + rows[m][l:]

        ext = s[1:][::-1] + list(range(m + 1, m + q + 1))
        rows[m].extend(ext)
        rows[m].sort()
        base[m - 1] += q

        d = []
        for i in range(q):
            d_i = c + s[q - i:] + list(range(m + 1, m + i + 2))
            d.append(sorted(d_i))

        old_e = e + 1
        base[:] = base[:m - 1] + list(range(old_e - l, old_e - l + q)) + base[m - 1:]
        rows[:] = rows[:m] + d + rows[m:]
        self.mask[:] = self.mask[:m] + [set() for _ in range(q)] + self.mask[m:]

        meta_insert = [{"native_generated": True, "native_q": q} for _ in range(q)]
        meta[:] = meta[:m] + meta_insert + meta[m:]

        marks_to_propagate = {x + q if x >= m + 1 else x for x in marks_m_orig}
        for row_idx in range(m, m + q + 1):
            self.mask[row_idx].update(marks_to_propagate)
        for j in range(1, q + 1):
            self.mask[m + j].update(range(m, m + j))

        self.mask[m + q].discard(m + 1 + q)
        self._normalize_rows_inplace(start_row=m)
        return True, q

    def modify(self, copy_only=False, silent=False):
        try:
            orig_rows = _clone_rows(self.rows)
            orig_mask = _clone_mask(self.mask)
            orig_base = orig_rows[0][:]
            orig_last_mask = set(orig_mask[-1]) if orig_mask else set()

            rows = self.rows
            base0 = rows[0]
            n_before_cut = len(base0)
            l_last = base0[n_before_cut - 1]
            b = rows[-1][:]
            b0 = b[0]
            p_leftmost = b[0]

            self.cut()
            rows = self.rows
            base0 = rows[0]

            u = b[-l_last - 1]
            v_copy = n_before_cut
            base0.extend(orig_base[u - 1: v_copy])

            b_map = {}
            limit = len(b) - l_last
            for i in range(limit):
                key = b[i]
                if key not in b_map:
                    b_map[key] = b[i + l_last]

            def map_elem(x):
                if x < b0:
                    return x
                if x > u:
                    return x - u + n_before_cut
                return b_map.get(x, -1)

            copied_set = set(range(u, v_copy + 1))

            for row_idx in range(u, v_copy + 1):
                src_row = orig_rows[row_idx]
                new_seq = []
                for elem in src_row:
                    new_val = map_elem(elem)
                    if new_val == -1:
                        if not silent:
                            print(MSG_UNPLEASANT)
                        raise ModifyUnpleasant
                    new_seq.append(new_val)
                new_seq.sort()
                rows.append(new_seq)

                new_marks = set()
                src_marks = orig_mask[row_idx]
                if src_marks:
                    l_m = orig_base[row_idx - 1]
                    for marked_val in src_marks:
                        if _find_index(orig_rows[row_idx], marked_val) is None:
                            continue
                        tprime, t, _terminal = self._first_not_copied_in_transmission(
                            orig_rows, orig_base, copied_set, row_idx, marked_val
                        )
                        keep = False
                        if t in copied_set:
                            keep = True
                        else:
                            if tprime is not None and tprime < p_leftmost:
                                keep = True
                            elif tprime is not None:
                                u_img = b_map.get(tprime, None)
                                if u_img is not None and u_img in orig_last_mask:
                                    mv_img = map_elem(marked_val)
                                    if mv_img != -1:
                                        pos_u = _find_index(new_seq, mv_img)
                                        if pos_u is not None:
                                            idx_check = pos_u - l_m + 1
                                            if idx_check >= 0 and new_seq[idx_check] <= p_leftmost:
                                                keep = True
                        if keep:
                            new_marks.add(map_elem(marked_val))
                self.mask.append(new_marks)

            if copy_only:
                self._normalize_rows_inplace()
                return self.clone()

            meta = [None] * len(self.rows)
            native_done = {}

            m = n_before_cut
            while True:
                base0 = self.rows[0]
                if m > len(base0):
                    break
                self._mark_completion_for_row(m, meta, native_done)
                did, q = self._native_completion_step(m, meta)
                if did:
                    native_done[m] = q
                    m += q + 1
                else:
                    m += 1

            self._normalize_rows_inplace()
            return self.clone()

        except ModifyUnpleasant:
            raise
        except RuntimeError as e:
            if str(e) == "Unpleasant.":
                if not silent:
                    print(MSG_UNPLEASANT)
                raise ModifyUnpleasant
            raise


initial_rows = [
    [1, 1, 2, 2, 2],
    [0, 1],
    [0, 1, 2],
    [0, 1, 2, 3],
    [0, 1, 2, 3, 4],
    [2, 3, 4, 5]
]
initial_mask = [set() for _ in initial_rows]
initial_mask[4] = {3}


def _encode_expr(pat: BasicLaverPattern):
    base = pat.rows[0]
    expr = []
    for i in range(1, len(pat.rows)):
        L = base[i - 1] if (i - 1) < len(base) else 0
        vals_desc = list(reversed(pat.rows[i]))
        mset = pat.mask[i]
        row = [L] + [[v, (v in mset)] for v in vals_desc]
        expr.append(row)
    return expr


def _decode_expr(expr):
    base = [row[0] for row in expr]
    rows = [base]
    mask = [set()]
    for row in expr:
        vals = [x[0] for x in row[1:]]
        vals = sorted(set(vals))
        rows.append(vals)
        mask.append({x[0] for x in row[1:] if x[1]})
    return BasicLaverPattern(rows, mask)


def _deepcopy_expr(expr):
    return [[row[0]] + [[x[0], bool(x[1])] for x in row[1:]] for row in expr]


def _values(row):
    return [row[0]] + [x[0] for x in row[1:]]


def _cut_expr(expr):
    return _deepcopy_expr(expr[:-1])


def _pleasant_until(rows, t):
    tv = _values(t)
    L = t[0]
    tcheck = tv[1 + L:]
    if not tcheck:
        return -1

    tmax = tcheck[0]
    tmin = tcheck[-1]
    tset = set(tcheck)

    for n, s in enumerate(rows):
        scheck = _values(s)[1:]
        i1 = -1
        for idx, x in enumerate(scheck):
            if x < tmax:
                i1 = idx
                break
        i2 = -1
        for idx in range(len(scheck) - 1, -1, -1):
            if scheck[idx] > tmin:
                i2 = idx
                break

        if i1 != -1 and i2 != -1 and i1 <= i2:
            mid = scheck[i1:i2 + 1]
            if any(x not in tset for x in mid):
                return n
    return -1


def _seq_from(expr, i, j):
    row = expr[i]
    val = row[j][0]
    L = row[0]
    threshold = row[j + L][0] if (j + L) < len(row) else 0

    record = [[i + 1, j], [val]]
    while val > threshold:
        row = expr[val - 1]
        idx = 1 + row[0]
        record[-1].append(idx)
        val = row[idx][0] if idx < len(row) else 0
        record.append([val])

    record.pop()
    return record


def _apv(s_vals, t_vals):
    L = t_vals[0]
    t_last = t_vals[-1]
    t_1 = t_vals[1]
    t_1L = t_vals[1 + L] if (1 + L) < len(t_vals) else 0

    out = []
    for x in s_vals:
        if x < t_last:
            out.append(x)
        elif x >= t_1L:
            out.append(x - t_1L + t_1)
        else:
            k = -1
            for idx in range(len(t_vals) - 1, -1, -1):
                if t_vals[idx] == x:
                    k = idx
                    break
            out.append(None if k == -1 else t_vals[k - L])
    return out


def _ap(row_s, row_t):
    svals = _values(row_s)[1:]
    tvals = _values(row_t)
    mapped = _apv(svals, tvals)
    return [row_s[0]] + [[x, False] for x in mapped]


def _copy_block(raw, flag):
    active = raw[-1]
    expr = _cut_expr(raw)

    begin = active[1 + active[0]][0]
    end = (begin + flag) if (flag != -1) else (len(raw) + 1)
    offset = len(raw) - begin

    expr.extend([_ap(row, active) for row in raw[begin - 1:end - 1]])

    active_min = active[-1][0]
    begin_rowno = begin

    for i in range(begin - 1, end - 1):
        row = raw[i]
        target_row = expr[i + offset]
        for j in range(1, len(row)):
            if not row[j][1]:
                continue

            seq = _seq_from(raw, i, j)

            nomove = -1
            for k, item in enumerate(seq):
                if item[0] < begin_rowno:
                    nomove = k
                    break

            if nomove == -1:
                target_row[j][1] = True
                continue

            if seq[nomove][0] < active_min:
                target_row[j][1] = True
                continue

            c = seq[nomove - 1][0] + offset
            rowc = expr[c - 1]
            b = rowc[seq[nomove - 1][1]][0]

            idx_check = j + target_row[0] - 1
            left_ok = (idx_check < len(target_row)) and (target_row[idx_check][0] <= active_min)
            active_has_b_mark = any((x[0] == b and x[1]) for x in active[1:])

            if left_ok and active_has_b_mark:
                target_row[j][1] = True

    return expr


def _comp_to(raw, r, already):
    expr = _deepcopy_expr(raw)
    for j in range(len(raw[r]) - 1, 0, -1):
        if not raw[r][j][1]:
            continue
        n = raw[r][j][0]
        seq = _seq_from(raw, r, j)
        t = seq[-1][0]
        T = already[t - 1] if (t - 1) < len(already) else None
        if not T:
            continue
        q = len(T)
        entries = (
            [[x[0], bool(x[1])] for x in expr[r][1:]] +
            [[x, False] for x in T] +
            [[n + 1 + uu, True] for uu in range(q)]
        )
        entries.sort(key=lambda z: z[0], reverse=True)
        expr[r] = [expr[r][0] + q] + entries
    return expr


def _comp_from(raw, r, T):
    q = len(T)

    expr = [[row[0]] + [[x[0], bool(x[1])] for x in row[1:]] for row in raw[:r]]

    if len(raw[r]) < raw[r][0] * 2 + 1:
        lr = raw[r][0]
        cr = raw[r][1:-raw[r][0]] + raw[r][1 + raw[r][0]:]
    else:
        lr = raw[r][0] + 1
        cr = raw[r][1:]

    need_len = r + q + 1
    if len(expr) < need_len:
        expr.extend([None] * (need_len - len(expr)))

    for qq in range(q):
        entries = (
            [[x[0], bool(x[1])] for x in cr] +
            [[x, False] for x in T[:1 + qq]] +
            [[raw[r][1][0] + 1 + uu, False] for uu in range(qq)]
        )
        entries.sort(key=lambda z: z[0], reverse=True)
        expr[r + qq] = [lr + qq] + entries

    entries = (
        [[x[0], bool(x[1])] for x in raw[r][1:]] +
        [[x, False] for x in T] +
        [[raw[r][1][0] + 1 + uu, False] for uu in range(q)]
    )
    entries.sort(key=lambda z: z[0], reverse=True)
    expr[r + q] = [raw[r][0] + q] + entries

    for qq in range(1, q + 1):
        for uu in range(2, 1 + qq + 1):
            expr[r + qq][uu][1] = True

    threshold = raw[r][1][0]

    def m(entry, idx):
        if idx == 0:
            return entry
        vv = entry[0]
        if vv <= threshold:
            return [vv, bool(entry[1])]
        return [vv + q, bool(entry[1])]

    for row in raw[r + 1:]:
        new_row = []
        for idx, entry in enumerate(row):
            new_row.append(m(entry, idx))
        expr.append(new_row)

    return expr


def _expand_pleasant_only(raw, FSterm, longer=False):
    if FSterm < 0:
        FSterm = 0

    active = raw[-1]
    L = active[0]
    if (1 + L) >= len(active) or (active[1 + L][0] == 0):
        return _cut_expr(raw)

    begin = active[1 + L][0]
    flag = _pleasant_until(raw[begin - 1:-1], active)
    if flag != -1:
        raise ModifyUnpleasant

    expr = _deepcopy_expr(raw)
    for _ in range(FSterm):
        expr = _copy_block(expr, -1)

    expr = _copy_block(expr, 1) if longer else _cut_expr(expr)

    already = []
    r = len(raw) - 1
    while r < len(expr):
        expr = _comp_to(expr, r, already)

        if not (len(expr[r]) <= expr[r][0] * 2 + 1):
            r += 1
            continue

        idx0 = expr[r][expr[r][0]][0]
        T = [idx0]
        bound = expr[r][expr[r][0] + 1][0]

        while T[0] > bound:
            rr = T[0] - 1
            T.insert(0, expr[rr][2][0])

        T = T[1:-1]
        if len(T) < 1:
            r += 1
            continue

        expr = _comp_from(expr, r, T)

        while len(already) <= r:
            already.append(None)
        already[r] = T

        r += len(T) + 1

    return expr


def _expand_like_model(pattern: BasicLaverPattern, FSterm: int, longer: bool, silent: bool):
    if pattern.is_zero():
        return pattern.clone(), 0
    if pattern.is_successor():
        q = pattern.clone()
        q.cut()
        return q, 0

    base0 = pattern.rows[0]
    if not base0:
        q = pattern.clone()
        q.cut()
        return q, 0

    if FSterm <= 0:
        q = pattern.clone()
        q.cut()
        return q, 0

    try:
        raw = _encode_expr(pattern)
        res = _expand_pleasant_only(raw, FSterm=FSterm, longer=longer)
        p2 = _decode_expr(res)
        return p2.clone(), 1
    except ModifyUnpleasant:
        if not silent:
            print(MSG_UNPLEASANT)
        q = pattern.clone()
        q.cut()
        return q, 0


def _apply_special_one(pattern: BasicLaverPattern, silent=False):
    if pattern.is_zero():
        return pattern.clone(), 0
    if pattern.is_successor():
        p = pattern.clone()
        p.cut()
        return p, 0

    p = pattern.clone()
    try:
        orig_rows = _clone_rows(p.rows)
        orig_mask = _clone_mask(p.mask)
        orig_base = orig_rows[0][:]
        orig_last_mask = set(orig_mask[-1]) if orig_mask else set()

        rows = p.rows
        base0 = rows[0]
        n_before_cut = len(base0)
        if n_before_cut <= 0:
            p2 = p.clone()
            p2.cut()
            return p2, 0

        original_total_rows = len(rows)

        l_last = base0[n_before_cut - 1]
        b = rows[-1][:]
        if not b:
            p2 = p.clone()
            p2.cut()
            return p2, 0
        b0 = b[0]
        p_leftmost = b[0]

        p.cut()
        rows = p.rows
        base0 = rows[0]

        if l_last < 0 or len(b) < l_last + 1:
            if not silent:
                print(MSG_UNPLEASANT)
            raise ModifyUnpleasant
        u = b[-l_last - 1]

        if u - 1 < 0 or u - 1 >= len(orig_base):
            if not silent:
                print(MSG_UNPLEASANT)
            raise ModifyUnpleasant
        base0.append(orig_base[u - 1])

        b_map = {}
        limit = len(b) - l_last
        for i in range(limit):
            key = b[i]
            if key not in b_map:
                b_map[key] = b[i + l_last]

        def map_elem(x):
            if x < b0:
                return x
            if x > u:
                return x - u + n_before_cut
            return b_map.get(x, -1)

        copied_set = {u}

        if u <= 0 or u >= len(orig_rows):
            if not silent:
                print(MSG_UNPLEASANT)
            raise ModifyUnpleasant

        src_row = orig_rows[u]
        new_seq = []
        for elem in src_row:
            new_val = map_elem(elem)
            if new_val == -1:
                if not silent:
                    print(MSG_UNPLEASANT)
                raise ModifyUnpleasant
            new_seq.append(new_val)
        new_seq.sort()
        rows.append(new_seq)

        new_marks = set()
        src_marks = orig_mask[u]
        if src_marks:
            l_m = orig_base[u - 1]
            for marked_val in src_marks:
                if _find_index(orig_rows[u], marked_val) is None:
                    continue
                tprime, t, _terminal = p._first_not_copied_in_transmission(
                    orig_rows, orig_base, copied_set, u, marked_val
                )
                keep = False
                if t in copied_set:
                    keep = True
                else:
                    if tprime is not None and tprime < p_leftmost:
                        keep = True
                    elif tprime is not None:
                        u_img = b_map.get(tprime, None)
                        if u_img is not None and u_img in orig_last_mask:
                            mv_img = map_elem(marked_val)
                            if mv_img != -1:
                                pos_u = _find_index(new_seq, mv_img)
                                if pos_u is not None:
                                    idx_check = pos_u - l_m + 1
                                    if idx_check >= 0 and new_seq[idx_check] <= p_leftmost:
                                        keep = True
                if keep:
                    mv = map_elem(marked_val)
                    if mv != -1:
                        new_marks.add(mv)

        p.mask.append(new_marks)
        p._normalize_rows_inplace(start_row=len(p.rows) - 1)

        meta = [None] * len(p.rows)
        m = len(p.rows[0])
        did, q = p._native_completion_step(m, meta)

        if did and q > 0:
            for _ in range(q):
                p.cut()

        while len(p.rows) > original_total_rows:
            p.cut()

        p._normalize_rows_inplace()
        return p.clone(), 1

    except ModifyUnpleasant:
        q = pattern.clone()
        q.cut()
        return q, 0
    except RuntimeError as e:
        if str(e) == "Unpleasant.":
            if not silent:
                print(MSG_UNPLEASANT)
            q = pattern.clone()
            q.cut()
            return q, 0
        raise


def _apply_number(pattern, n, silent=False):
    if pattern.is_zero():
        return pattern.clone(), 0

    if n == 0:
        p = pattern.clone()
        p.cut()
        return p, 0

    if pattern.is_successor():
        p = pattern.clone()
        p.cut()
        return p, 0

    if n == 1:
        return _apply_special_one(pattern, silent=silent)

    FSterm = n - 1
    nxt, ok = _expand_like_model(pattern, FSterm=FSterm, longer=False, silent=silent)
    if ok == 0:
        return nxt, 0
    return nxt, n


def reconstruct_pattern_list(op_numbers, silent=False):
    pattern_list = [BasicLaverPattern(initial_rows, initial_mask)]
    executed = []
    for n in op_numbers:
        cur = pattern_list[-1]
        nxt, actual = _apply_number(cur, n, silent=silent)
        executed.append(actual)
        pattern_list.append(nxt)
    return executed, pattern_list, None


def _cmp_lists(a, b):
    la, lb = len(a), len(b)
    m = la if la < lb else lb
    for i in range(m):
        if a[i] < b[i]:
            return -1
        if a[i] > b[i]:
            return 1
    if la < lb:
        return -1
    if la > lb:
        return 1
    return 0


def _row_key_for_compare(pat, row_idx):
    base = pat.rows[0]
    row = pat.rows[row_idx]
    l = base[row_idx - 1] if row_idx - 1 < len(base) else 0
    if l <= 1:
        keep = row[:]
    else:
        if len(row) < l:
            keep = row[:]
        else:
            keep = [row[0]] + row[l:]
    keep = keep[::-1]
    return keep


def compare_patterns(a, b):
    ra = len(a.rows) - 1
    rb = len(b.rows) - 1
    m = ra if ra < rb else rb
    for i in range(1, m + 1):
        ka = _row_key_for_compare(a, i)
        kb = _row_key_for_compare(b, i)
        c = _cmp_lists(ka, kb)
        if c != 0:
            return c
    if ra < rb:
        return -1
    if ra > rb:
        return 1
    return 0


def _is_prefix(seg, full):
    if len(seg.rows) > len(full.rows):
        return False
    if seg.rows[0] != full.rows[0][:len(seg.rows[0])]:
        return False
    for i in range(1, len(seg.rows)):
        if seg.rows[i] != full.rows[i]:
            return False
    return True


def _is_proper_prefix(seg, full):
    return _is_prefix(seg, full) and (len(seg.rows) < len(full.rows))


def _pattern_equal(a: BasicLaverPattern, b: BasicLaverPattern):
    return a.rows == b.rows and a.mask == b.mask


def _pattern_signature(p: BasicLaverPattern):
    rows_sig = tuple(tuple(r) for r in p.rows)
    mask_sig = tuple(tuple(sorted(s)) for s in p.mask)
    return rows_sig, mask_sig


_EXPAND_COUNTS_CACHE = {}


def _expand_row_counts_from(start_pat: BasicLaverPattern, n: int):
    if n < 0:
        n = 0
    key = (_pattern_signature(start_pat), n)
    if key in _EXPAND_COUNTS_CACHE:
        return _EXPAND_COUNTS_CACHE[key][:]

    counts = [len(start_pat.rows)]
    for k in range(1, n + 1):
        res, _act = _apply_number(start_pat, k, silent=True)
        counts.append(len(res.rows))

    _EXPAND_COUNTS_CACHE[key] = counts[:]
    return counts


def _simplify(op_numbers, pattern_list):
    target = pattern_list[-1].clone()

    s = op_numbers[:]
    executed, pats, _ = reconstruct_pattern_list(s, silent=True)
    s = executed
    pattern_list = pats

    i = len(s) - 1
    while i >= 0:
        if i >= len(s):
            i = len(s) - 1
        if i < 0:
            break
        if s[i] == 0:
            i -= 1
            continue

        while True:
            if i >= len(s):
                break
            n = s[i]

            z = 0
            j = i + 1
            while j < len(s) and s[j] == 0:
                z += 1
                j += 1

            candidate = None
            need = None

            if n == 1:
                if z >= 1:
                    candidate = s[:i] + s[i + 1:]
                else:
                    break
            else:
                start_pat = pattern_list[i]
                counts = _expand_row_counts_from(start_pat, n)
                need = counts[n] - counts[n - 1]
                if need < 0:
                    need = 0

                if z < need:
                    break

                candidate = s[:]
                candidate[i] = n - 1
                if need > 0:
                    del candidate[i + 1: i + 1 + need]

            cand_exec, cand_pats, _ = reconstruct_pattern_list(candidate, silent=True)
            if not cand_pats or not _pattern_equal(cand_pats[-1], target):
                break

            s = cand_exec
            pattern_list = cand_pats

            if i >= len(s):
                break
            if s[i] == 0:
                break

        i = min(i, len(s) - 1)
        i -= 1
        while i >= 0 and s[i] == 0:
            i -= 1

    executed, pattern_list, _ = reconstruct_pattern_list(s, silent=True)
    return executed, pattern_list


def _seq_str(nums):
    return ",".join(str(x) for x in nums)


def _parse_o_string(s):
    s = s.strip()
    if s == "":
        return BasicLaverPattern([[]], [set()]), None

    pos = 0
    rows_desc = []
    steps = []
    n = len(s)

    while pos < n:
        if s[pos] != "(":
            return None, "error"
        pos += 1
        close = s.find(")", pos)
        if close == -1:
            return None, "error"
        inside = s[pos:close].strip()
        pos = close + 1

        nums = []
        if inside != "":
            parts = inside.split(",")
            for part in parts:
                part = part.strip()
                if part.startswith("*"):
                    part = part[1:].strip()
                if part == "" or (not part.isdigit()):
                    return None, "error"
                nums.append(int(part))

        nums_asc = sorted(nums)
        for i in range(1, len(nums_asc)):
            if nums_asc[i] == nums_asc[i - 1]:
                return None, "error"

        if pos >= n or (not s[pos].isdigit()):
            return None, "error"
        j = pos
        while j < n and s[j].isdigit():
            j += 1
        step = int(s[pos:j])
        pos = j

        rows_desc.append(nums_asc)
        steps.append(step)

    rows = [steps[:]] + rows_desc
    mask = [set()] + [set() for _ in rows_desc]
    return BasicLaverPattern(rows, mask), None


def _read_find_pattern(I):
    initial = BasicLaverPattern(initial_rows, initial_mask)
    C = initial.clone()

    ops = []
    pats = [C.clone()]

    if compare_patterns(C, I) <= 0:
        return C, ops, pats

    MAX_OUTER = 50000
    MAX_N = 20000
    outer = 0

    while outer < MAX_OUTER:
        outer += 1

        if compare_patterns(C, I) == 0:
            return C, ops, pats

        n = 0
        while n <= MAX_N:
            Cn, actual = _apply_number(C, n, silent=True)

            if _is_proper_prefix(Cn, I):
                n += 1
                continue

            if (compare_patterns(Cn, I) < 0) and (not _is_prefix(Cn, I)):
                return C, ops, pats

            if compare_patterns(Cn, I) >= 0:
                if Cn.rows == C.rows and Cn.mask == C.mask:
                    return C, ops, pats
                C = Cn
                ops.append(actual)
                pats.append(C.clone())
                break

            n += 1

        else:
            return C, ops, pats

    return C, ops, pats


def main_program():
    op_numbers = []
    executed, pattern_list, _ = reconstruct_pattern_list(op_numbers, silent=True)
    op_numbers = executed

    while True:
        cur = pattern_list[-1]
        print("\nCurrent pattern:")
        if cur.is_zero():
            print("(empty)")
        else:
            cur.draw()

        print(f"Operation sequence: {_seq_str(op_numbers)}")

        if cur.is_zero():
            pattern_type = "Zero"
        elif cur.is_successor():
            pattern_type = "Successor"
        else:
            pattern_type = "Limit"

        msg = f"This is a {pattern_type} pattern."
        msg += " Natural Number: Operation."
        msg += " O: Output."
        msg += " R: Read."
        if len(pattern_list) > 1:
            msg += " U: Undo."
        msg += " S: Simplify."
        msg += " I: Input operations."
        print(msg)

        user_input = input("Enter your operation: ").strip().upper()

        if user_input.isdigit():
            n_in = int(user_input)
            nxt, actual = _apply_number(cur, n_in, silent=False)
            pattern_list.append(nxt)
            op_numbers.append(actual)
            if actual == 0:
                print("Applied cut operation.")
            else:
                print(f"Applied operation {actual}.")
            continue

        if user_input == 'O':
            print(cur.to_string())
            continue

        if user_input == 'R':
            raw = input("Input pattern string (from O): ").strip()
            pat, err = _parse_o_string(raw)
            if err:
                print("error")
                continue
            found, ops, pats = _read_find_pattern(pat)
            op_numbers = ops
            pattern_list = pats
            print(found.to_string())
            continue

        if user_input == 'U' and len(pattern_list) > 1:
            op_numbers = op_numbers[:-1]
            executed, pattern_list, _ = reconstruct_pattern_list(op_numbers, silent=True)
            op_numbers = executed
            print("Undo the last operation.")
            continue

        if user_input == 'S':
            new_ops, new_patterns = _simplify(op_numbers, pattern_list)
            if new_ops != op_numbers:
                op_numbers = new_ops
                pattern_list = new_patterns
                print(f"Simplified operation sequence: {_seq_str(op_numbers)}")
            else:
                print("No further simplifications possible.")
            continue

        if user_input == 'I':
            raw = input("Input the operation sequence (comma-separated natural numbers, e.g., 3,0,2,1): ").strip()
            if raw == "":
                parsed = []
            else:
                parts = [p.strip() for p in raw.split(",")]
                if any(p == "" or (not p.isdigit()) for p in parts):
                    print("error")
                    continue
                parsed = [int(p) for p in parts]
            executed, pattern_list, _ = reconstruct_pattern_list(parsed, silent=True)
            op_numbers = executed
            continue

        print("Invalid operation. Please try again.")


if __name__ == "__main__":
    main_program()
    
</syntaxhighlight>{{默认排序:序数记号}}
[[分类:记号]]