CodeShell.kr - Undo History

Challenge

一份账本与撤销规则，其中撤销操作自身也能被撤销。难点在于事件存亡是递归的，必须解不动点而不是单遍扫描。

What remains

剩下什么。

https://codeshell.kr/challenges/misc-undo-history/

Solution

附件含 initial.txt、ledger.csv（660 行）与规则：VOID 撤销更早的事件，但 VOID 自身也可以被更晚的 VOID 撤销。

Step 1：事件存亡不是单遍扫描能确定的：alive[e] = 1 XOR (⊕ alive[v], v 指向 e) 的不动点才是自洽解，6 轮收敛，189 个 VOID 中 152 个存活。

Step 2：用两种独立方法交叉验证：不动点法与按 tick 降序贪心法得到同一结果；忽略 VOID 或只做单遍处理都得到无意义的字母串。

Step 3：把存活的非 VOID 事件按 tick 升序作用到初始屏：

initial.txt  TAWISHEOLRWTNDS
final        THELASTWORDWINS

最终屏与初始屏是同字母重排，且是完整英文短语，与题面 "What remains" 自洽。

Script

#!/usr/bin/env python3
"""CodeShell.kr - Undo History (Misc, 200p) solver.

A VOID undoes an earlier event, but a VOID can itself be undone by a later VOID,
so the survival of each event is the fixpoint of
    alive[e] = 1 XOR (XOR of alive[v] for v pointing at e).
Iterating to the fixpoint and then applying the surviving non-VOID events in
ascending tick order to the initial screen gives the answer.
"""
import csv

LEDGER = "extracted/misc-undo-history/ledger.csv"
INITIAL = "TAWISHEOLRWTNDS"


def main():
    rows = sorted(csv.DictReader(open(LEDGER)), key=lambda r: int(r["tick"]))
    voids = {int(r["id"]): int(r["a"]) for r in rows if r["op"] == "VOID"}

    alive = {int(r["id"]): 1 for r in rows}
    updates = 0
    while True:
        new = {i: 1 ^ (sum(alive[v] for v, t in voids.items() if t == i) & 1)
               for i in alive}
        if new == alive:
            break
        alive = new
        updates += 1
    print(f"fixpoint after {updates} updates; surviving VOIDs "
          f"{sum(alive[v] for v in voids)}/{len(voids)}")

    s = list(INITIAL)
    for r in rows:
        if not alive[int(r["id"])] or r["op"] == "VOID":
            continue
        a, b = int(r["a"]), (int(r["b"]) if r["b"] else None)
        if r["op"] == "SWAP":
            s[a], s[b] = s[b], s[a]
        elif r["op"] == "REVERSE":
            s[a:b + 1] = s[a:b + 1][::-1]
        elif r["op"] == "ROTATE":
            n = a % 15
            s = s[-n:] + s[:-n] if n else s
    print("".join(s))


if __name__ == "__main__":
    main()

CodeShell{THELASTWORDWINS}