第五名解题报告（附带更优压缩算法与种子破解）
首先，我们要感谢组织者举办这样的比赛，感谢所有参与者与我们角逐。过去的三个月对我们来说令人兴奋。
我们团队的背景主要是 competitive programming 和 CTF。因此这次比赛对我们来说是踏入未知领域，因为我们几乎没有代码高尔夫（code golf）的经验，几乎没有 Kaggle 的经验。事实上，这次比赛中的许多团队似乎也是 Kaggle 新手。我们是一个学生团队（有人质疑我们奇怪的队名，这是与我们大学相关的内部玩笑），我们在 8 月和 9 月的暑假期间特别努力。
这份写作报告解释了我们的方法，并突出了一些有趣的解决方案。我们使用的可视化工具和 GitHub 仓库列在最后。
我们的解决方案概述
我们的方法是 90% 打磨代码高尔夫，9% 工具开发，1% 奇怪的黑客技巧。由于 90% 的打磨是许多团队都在做的事情，我们将只展示我们两个最难忘的解决方案。
1. 任务 111 (62 字节，最佳 +2)
p=lambda g:[[*iter(sum(g,g).pop,5)][3-i:-i:-1]for i in b'\x0c\x16\x20']iter(l.pop, n) 会反向遍历 l 直到弹出 n。这是唯一一个我们可以利用这种行为的任务。
a = [3,1,4,1,5,9,2]
print([*map(str,iter(a.pop,4))]) # ['2', '9', '5', '1']
print(a) # [3, 1]2. 任务 270 (115 字节，最佳 +2)
import re;p=lambda g,c=-7:c*g or[*zip(*eval(re.sub("((3)|7)([^[(]+)0(, (?(2)2|1))",r"0\3\1\4",str(p(g,c+1)))))][::-1]这是我们看到的唯一一个使用条件组语法 (?(id/name)yes-pattern|no-pattern) 根据组是否匹配来更改正则表达式模式的解决方案。
工具与一些奇怪的黑客技巧
这是我们在过程中构建的工具和奇怪的黑客技巧。
压缩优化
甚至在比赛开始之前，我们就怀疑会有 cases 使用压缩策略。这个直觉被证明是正确的。我们构建了自己的压缩器和优化器，比 Zopfli（Google 开发的更好的 zlib 压缩器）更强，相对于原生 zlib，我们的得分提高了约 700 分。
压缩基础
首先，快速概述一下压缩代码设置。压缩代码需要在运行时解压并执行。一个关键的考虑因素是如何将压缩 payload 嵌入到源代码中。Python 字节字面量不能包含 ≥ 0x80 的字符，所以我们需要从另一种格式转换。
我们通过将 payload 嵌入字符串字面量并将其转换为字节来处理这个问题。在 Python 中，文件编码可以通过注释指定，如 # -*- coding: latin-1 -*- (PEP 263)。匹配正则表达式 ^[ \t\f]*#.*?coding[:=][ \t]*([-_.a-zA-Z0-9]+) 的最短形式是 #coding:L1。L1 是 latin_1 编码的别名 (文档)，它将每个字符从 ord(0) 到 ord(255) 直接映射到其字节值。使用这个，解压存根变为：
#coding:L1
import zlib
exec(zlib.decompress(bytes("<compressed code>",'L1')))我们使用 zlib 是因为它最适合我们的用例。Python 提供 zlib、lzma 和 bzip。zlib 和 lzma 是 LZ77 系列压缩器，bzip 基于 Burrows–Wheeler Transform。对于这些输入，BWT 可能比 LZ77 弱，lzma 很强但其头部开销很大，所以除非代码超过约 1000 字节，否则它无法击败 zlib。更新的 zstd 将在 Python 3.14 中可用 (文档)，但遗憾的是这次无法使用。
zlib 基本上是 deflate 加上 2 字节头部和 4 字节 CRC 校验和。zlib.decompress() 支持原始 deflate，当你传递负的第二参数时，所以 zlib.decompress(code,-15) 节省了 6 字节，代价是 4 额外字节，净赚胜利。对于小的 zlib 流，zlib.decompress(code,-9) 有时也有效，再削掉一个字节。我们最终的解压存根如下所示：
#coding:L1
import zlib
exec(zlib.decompress(bytes("<compressed code>",'L1'),-9))deflate 的结构
在谈论 deflate 特定优化之前，这里是最基本的结构。Deflate 将数据编码为先前子串的副本加上单字符添加。例如，abracadabra 变为 [a][b][r][a][c][a][d][copy(distance=7,length=4)]。将每个部分视为一个因子。最小化因子数量很容易通过贪婪方法实现。在实践中，我们还必须将这些因子编码到位流中，这个编码步骤使事情变得复杂。仅最小化因子计数并不总是最小化最终的 deflate 大小。
对于编码，deflate 对字面量使用 Huffman 代码，对长度/距离对也使用 Huffman 代码。你可以使用预设的 Huffman 树或嵌入你自己的。在我们的用例中，预设效率低下，所以我们大多嵌入自己的。中途切换树是可能的，但嵌入树的成本约为 300 位（~40 字节），所以这里通常一棵树最好。（很少情况下，对最后一个块使用预设树更好。但你可以暴力破解边界来轻松补偿这一点。）
有两棵 Huffman 树，一棵用于字面量/长度，另一棵用于距离。这些树本身经过游程编码 (RLE)，然后由另一棵 Huffman 树（"cl-code"）编码并作为头部插入。
我们构建了一个 deflate 可视化应用 (deflate-viz, 仓库)。通过查询参数附加 deflate 或 zlib payload，你可以检查内部结构。
代码级优化
通过探索可视化，我们获得了一些关键见解。
尽可能让相同的代码片段出现
显而易见，但这是压缩高尔夫的黄金法则。此外，循环展开有时比循环产生更好的结果。
避免大写变量名 / 重用出现在关键字中的名称
如前所述，Huffman 树由按字节值排序的代码长度表示，然后进行 RLE 压缩。更长的游程有帮助。Python 语法不使用大写字母，所以这些字节在代码长度流中理想情况下应全为零；引入大写会破坏 RLE。此外，为了帮助字面量 Huffman 分布，最好重用在常见关键字如 def 和 return 中出现的字母，或内置函数如 zip，并避免引入 stray 字符。
缩进首选 Tab 而不是空格 / 首选 ' 而不是 "
同样是 RLE 意识。Tab 在 ASCII 中靠近换行符，往往比空格更少破坏 RLE。单引号往往效果更好，因为 ' 与 ( 相邻。
优化压缩 Payload
我们首先着手生成对编码友好的 deflate payload。由于 payload 作为字符串嵌入，某些字符需要转义，例如用于字符串分隔符的引号字符，或 \x00。每个这样的字符成本额外一个字节；我们想避免它们。经验上，大约 1/100 的字节需要转义。
所以我们尝试随机扰动 deflate payload 的部分来躲避这些字符。最大的杠杆来自嵌入的 Huffman 树，它影响许多字节。在乐观假设所有字节独立随机化的情况下，~200 字节的 payload 避免转义的概率约为 (99/100)^200 ≈ 0.13。现实没那么仁慈，所以需要更多试验。
我们实现了一个 deflate 解析器并在 Zopfli 的输出之上执行爬山算法 (实现)。这在实践中效果很好，通常将转义数量减少到零。
超越 Zopfli
在此过程中，我们生成的 payload 击败了 Zopfli 的大小，最初是作为消除转义的爬山副作用。这表明我们实际上可以构建一个优于 Zopfli 的压缩器。
完整的故事很长，所以细节在队友的写作报告中（待写）。这里是方法的高层概述。
我们首先尝试通过遗传算法和模拟退火等元启发式方法改进 Huffman 树，但这表现不佳。我们怀疑这是因为搜索 landscape 不平滑，且目标（bits）是离散的。
重大突破是意识到当除了Huffman 树之外的一切固定时，我们可以通过动态规划 (DP) 计算最优 Huffman 代码长度。具体来说，固定因式分解和 cl-code（Huffman 代码的 Huffman 代码）允许 DP 找到最优代码长度。实现这一点让我们缩小了 Zopfli 生成的 Huffman 树 (实现)。以下是对比：
自动变量名优化
观察表明变量名分配强烈影响压缩。为了机械化这一点，我们静态分析代码以提取依赖关系，然后添加了一个例程重新分配变量名以提高可压缩性。这是单个最有影响力的优化，总体净赚数百字节。
遗传算法
我们还运行了一个 GA，其状态结合了变量名分配和 deflate payload 本身，交错进行因式分解和 Huffman 优化。这获得了约 100 字节 (实现)。
恢复测试用例的随机种子
据披露，测试用例是使用 ARC-GEN 生成的。生成器给定种子是确定性的。来自 arc_gen.py：
# https://github.com/google/ARC-GEN/blob/main/arc_gen.py
def generate_benchmarks(task_num, num_examples):
"""Creates a benchmark suite for a given task."""
task_info = task_list.task_list()[task_num]
_, generator, _ = task_info
examples = []
for example_id in range(num_examples):
random.seed(task_num + example_id)
examples.append(generator())
print(examples)然而，运行 arc_gen 并没有重现确切的测试用例。
当 task100 中的异常被修复且测试用例在几乎所有情况下保持不变时，这表明某种种子机制在起作用。我们推断泄漏随机性的高质量来源是通过 randint。跳过繁琐的细节，如果生成器仅使用像 randint(a, b) 这样的调用，其中 b - a + 1 是 2 的幂，这些输出可以泄漏 PRNG 状态的干净位。
我们过滤了 ARC-GEN 并确定了三个任务，即 task043, task127, task142，作为好的候选者。从每个 ARC-GEN case 中我们提取了使用的随机序列。
LEAK_CASES = 3
# https://github.com/google/ARC-GEN/blob/main/tasks/training/task043.py
# rows = [item for item in range(1, size) if common.randint(0, 1) == 0]
# cols = [item for item in range(0, size - 1) if common.randint(0, 1) == 0]
cases = get_task(43)['arc-gen']
leak_43 = []
for case in cases[:LEAK_CASES]:
g = case['input']
leak = [1*(0==r[-1])for r in g[1:]] + [1*(0==c)for c in g[0][:-1]]
leak_43.append(leak)
# https://github.com/google/ARC-GEN/blob/main/tasks/training/task127.py
# colors = [common.randint(1, 4) for _ in range(3 * common.randint(1, 2))]
cases = get_task(127)['arc-gen']
leaks_127 = []
for case in cases[:LEAK_CASES]:
g = case['input']
leak = []
leak.append([0, 1][len(g)==7])
leak.extend([v-1 for v in g[1][1::4]])
if len(g) == 7:
leak.extend([v-1 for v in g[5][1::4]])
leaks_127.append(leak)
# https://github.com/google/ARC-GEN/blob/main/tasks/training/task142.py
# colors = [common.randint(0, 3) for _ in range(size * size)]
# grid, output = common.grid(size, size), common.grid(2 * size, 2 * size)
# for r in range(size):
# for c in range(size):
# grid[r][c] = colors[r * size + c]
cases = get_task(142)['arc-gen']
leaks_142 = []
for case in cases[:LEAK_CASES]:
g = case['input']
leak = []
for s in g:
for v in s:
leak.append(v)
leaks_142.append(leak)
print(leaks_127)
print(leaks_142)
# [[0, 3, 1, 0], [0, 2, 0, 1], [0, 3, 0, 0]]
# [[0, 3, 1, 0, 2, 3, 1, 0, 3], [0, 2, 0, 1, 3, 3, 3, 1, 0], [0, 3, 0, 0, 2, 3, 1, 3, 1]]一点检查显示随机序列共享相同的前缀。换句话说， across all tasks, 每个索引使用了相同的种子！
考虑到这一点，我们搜索了会产生上述序列的种子。
for i in range(10000):
random.seed(i)
r = [random.randint(0,1) for i in range(18)]
if r in leak_43:
print(i, leak_43.index(r))
# 2025 0
# 2026 1
# 2027 2所以种子是 2025 + i。这提示我们可能通过从种子再生来 dramatically 压缩某些任务。为此有用，必须满足以下条件：
- 很难直接在 Python 中提取 vital 信息（更容易从随机性再生）。
- 生成代码简单。
- 训练和测试都可以从同一算法和短种子派生。
- 种子可以从可用信息中恢复。
- 从恢复的信息构建解决方案很简单。
通过侦察任务，只有 task096 符合这些标准。此任务有大量 corner cases，是最难优化的任务之一。
在此任务中，网格宽度/高度、背景颜色、准星颜色和每个段长度是随机生成的。以下是这些算法的简化版本：
# ref. https://github.com/google/ARC-GEN/blob/main/tasks/training/task096.py
width, height = random.randint(13, 19), random.randint(13, 19)
b = random.randint(1, 9) # background
colors = random.sample(sorted(set(range(1, 10))-{b}), random.randint(4, 6))
lengths = []
for i in range(len(colors)):
min_length, max_length = min(i + 1, 2), i + (0 if i > 1 else 1)
lengths.append(random.randint(min_length, max_length))这些正是你需要确定种子并构建输出的信息片段。我们的实验表明，宽度、高度、颜色集和背景颜色足以识别种子。并且，对于非 ARC-GEN 训练和测试 cases，我们也通过 exhaustive search 找到了种子。
这是我们使用此策略构建的代码：
from random import*
def p(r,l=4):
seed([2024-l,'+u-)+e[','41-efe[','41*l}{','f(3,+e['][l*(0<l)])
d,t,f=randrange(13,20)==len(r[0]),randrange(13,20)==len(r),randrange(1,10)
s=sample([*{*range(1,10)}^{f*(l<0)}],o:=randrange(4,7))
u=[1+randrange(0<m,(m<2)+m)for m in range(o)]
n=[(o*2-1)*[f]for m in range(o)]
for m in range(o):
for e in range(u[m]):e-=m;n[e-1][o+m-1]=n[e-1][o-m-1]=n[-m-1][o+e-1]=n[-m-1][o-e-1]=s[m]
return all([d,t,{*sum(r,[])}=={*s,f},f in r[2]])and n+n[:-1][::-1]or p(r,l-1)压缩后这最终达到 best+48，这不是我们想要的，但我们很自豪我们有这种解决方案。
GX (Golf Experience) / 生活质量功能
鉴于比赛的马拉松性质，我们构建了生活质量工具：主要是 CI/CD 和本地 Web UI。
CI/CD
在每次推送（和计划）上，我们运行作业来执行以下操作。
生成 README
我们生成 Markdown 中的统计摘要作为 README。后来 Web UI 取代了它，但在路上很方便。
生成每文件横幅
我们自动更新文件中的横幅以显示大小目标，如下所示：
# best: 51(LogicLynx, ALE-Agent) / others: 53(Ravi Annaswamy), 54(jonas ryno kg583 kabutack), 54(cubbus), 54(jacekwl Potatoman nauti), 54(jacekw Potatoman nauti natte)
# ====================== 51 ======================Discord 集成
我们在每次队友推送时通知我们的 Discord。这使得很容易发现错过的缩小机会并挑选低垂的果实。
观看排名 / 电子表格
我们自动更新横幅和 Web UI 引用的最佳已知大小。
Web UI
我们创建了（99% vibe-coded）本地 Web UI 用于日常高尔夫。
顶部页面
我们可以跟踪我们的进度。直方图突出了哪些任务值得压缩 attention。
任务列表
缩略图概述，按与最佳值的 delta 颜色编码。我们添加了手动标签和搜索。
任务详情
如图所示：标签和代码，所有 cases，以及按团队分的得分轨迹。我们还添加了一个"Open current best in VSCode"按钮。
Judge 视图
与 checker.py 集成以显示最新运行结果。通过 identity 函数 DUMP 传递值打印其参数，这有助于调试递归解决方案。
我们尝试的其他事情
- 早期，我们使用 GPT-o4-mini 自动生成解决方案，这就是为什么我们开始时排名很高。那些代码生活在 base_code。不过，最终幸存的解决方案都没有依赖 AI。
- 我们还发现了通过
__eq__的通用解决方案，该方案于 8 月中旬发布。我们的短版本是：class p:__init__=help;__eq__=any
- 直到 8 月下旬，我们使用 arc-dsl 和 re-arc 的 minified 版本来追逐 400/400。有些压缩到 ~2000 字节。到 9 月初，我们删除了它们全部，并用手写解决方案替换。
数据
我们的比赛仓库（非常混乱；它本不打算公开）在这里：
https://github.com/key-moon/golf
仓库概述：
dist: 结果base_[name]: 每个成员的"golf course"
如果你想运行任何东西，执行 source tools/setup.sh 来设置环境。