第一名解题报告：Code Golf International

首先，我们非常感谢竞赛的组织者提供了这样一个独特的机会，让我们能与更广泛的 Kaggle 社区一起参与竞争性代码高尔夫。过去的三个月对我们所有人来说都是一次激动人心的经历，获得第一名是一项巨大的荣誉。

概述

解决方案

我们的代码仓库在 这里。最终的竞赛提交来自 这个 commit。要复现我们的条目，您可以下载仓库并简单地运行 python auto_zip.py，这将创建 submission.zip 文件。

方法

我们的团队由 5 名经验丰富的代码高尔夫选手组成。我们对待这次竞赛的方法非常手动，所有解决方案均为手写。唯一的自动化是基于 zlib 的压缩，应用于 400 个任务中的 21 个（详见下文）。

结果

我们在竞赛中取得的好成绩主要归功于高尔夫 coding 的专业知识和大量的时间投入。为了帮助理解时间投入，平均每个任务可能需要几个小时来手动优化到高水平（包括原作者和审查者的时间），此外，随着我们发现新的或改进的技术，许多任务需要重新审视。乘以 400 个任务，即使对于 5 人团队分工合作来说，也是一项相当大的任务。

前 3 名团队之间的竞争非常激烈，我们没有任何特定的技术或策略比第 2 名或第 3 名具有决定性优势。事实上，赛后 review 其他人的解决方案时，我们发现错过了一些其他团队拥有的有用技术。

技巧

因为所有问题都是基于网格的，我们的解决方案中有许多重复出现的技术。在本节中，我们概述了一些亮点，重点关注本次竞赛特有的技术，而不是标准的 Python 高尔夫知识。然而，这绝不是完整的列表：每个问题都经过手动优化，因此有许多独特的技巧。

简短的网格操作

因为这些操作非常简短，它们是解决方案的基本构建块。

网格操作

• zip(*g) 转置网格
• g[::-1] 垂直镜像网格
• zip(*g[::-1]) 旋转 90 度
• sum(g,[]) 将 2D 网格展平为 1D 列表。注意在许多情况下 sum(g,g) 可以节省一个字节。
• filter(any,g) 移除空行

行操作

• min, max, any, all, 和 sorted 内置函数被普遍使用。对于 min, max, 和 sorted, key 参数经常被利用，例如，获取最少/最常见的颜色。
• {}.fromkeys(r) 将获取唯一颜色，按首次出现的顺序排序。或者，可以使用字典推导式：{v:0for v in r}
• filter(int,r) 移除黑色单元格

递归与循环

另一个基本构建块是使用递归或循环来重复操作。许多解决方案的形式是“执行操作 X，旋转 90 度，再重复 3 次”。

基线递归模板是 p=lambda g,n=3:-n*g or F(p(g,n-1))，利用 -n*g 在 n=0...3 时为 falsy 的特性。这比写出诸如 for n in range(4) 的循环更有效。在特殊情况下，有更短的方法或有用的替代方案：

• 如果递归深度仅为 2，则可以写 p=lambda g,h=0:F(h or p(g,g))，在大多数情况下节省 4 个字节。变体 p=lambda g,*h:F(*h or p(*g)) 再节省 2 个字节，但会移除第一行。
• 带有转置的深度 2 递归有时可以写成 p=lambda g:[*map(F:=lambda*r:...,*map(F,*g))]，再节省 1 个字节。
• 如果网格高度固定，则有一种“切片递归”技术，每次迭代将网格加倍，并使用切片在达到所需深度时停止递归：p=lambda g:F(g[70:]or p(g*2)) 将在 10x10 网格上迭代 4 次。这节省了字节，因为它消除了 p 的额外参数。例如，task 093 使用 p=lambda g:g[57330:]or ... 在 14x14 网格上迭代 12 次，因为 57330 = 14 * (2^12 - 1)。
• 作为递归的替代方案，有一个技巧可以制作短循环：p=lambda g:[g:=F(g)for _ in g][3]。当 g 需要在 F 内部多次使用时，这很有用。
• exec/eval 可以与字符串乘法一起使用来重复代码，例如 exec("F(x);"*9)。它是否有用非常取决于具体情况，但它可以在许多情况下导致少量的字节节省。一个例子是 task 007：

p=lambda g:eval(f'[{"max(sum(g:=g[1:3]+g,[])[2::3]),"*7}],'*7)

在这个任务中，有一个长度为 3 的模式重复，我们必须填入缺失的单元格。为此，我们在按步长 3 切片后取展平网格的最大元素，并且我们突变网格，以便我们可以始终使用相同的切片，避免任何循环变量的需要。因为网格始终是 7x7，我们可以使用带有 eval 的字符串乘法来执行每个单元格操作 7 次和每个行操作 7 次。

列表推导式

我们解决方案最常见的结构是使用列表推导式来转换网格。代码的最基本形式如下：

p=lambda g:[[F(x)for x in r]for r in g]

这仅操作单个单元格，相当有限。为了执行需要查看单个单元格之外的更复杂操作，可以使用海象 := 运算符引入状态变量。例如，要包含行的累积和，可以写：

p=lambda g:[(s:=0)or[F(x,s:=s+x)for x in r]for r in g]

初始化状态变量有时可以使用 map 和 lambda 更有效地完成：

[(a:=0)or[F(x,a:=...)for x in r)for*r,in zip(*g)]
#缩短为
[*map(lambda*r,a=0:[F(x,a:=...)for x in r],*g)]

另一种技术是在操作时突变列表。特别是，list.pop() 是多个技巧的来源。例如，它可以促进列表推导式中的“前瞻”，例如测试行中稍后是否出现某种颜色：

#原始版本，检查当前单元格右侧的行中是否有灰色单元格
p=lambda g:[[F(x,5in r[i:])for i,x in enumerate(r)]for r in g]
#使用 pop() 优化
p=lambda g:[[F(r.pop(0),5in r)for _ in r*1]for r in g]

list.pop() 也可以通过从后面而不是前面弹出隐式地反转列表：

p=lambda g:[[F(r.pop(0))for _ in r*1][::-1]for r in g] 
#缩短为
p=lambda g:[[F(r.pop())for _ in r*1]for r in g]

正则表达式

正则表达式，特别是 re.sub，对于简洁地编辑字符串非常强大。因此，将给定的输入矩阵转换为字符串，执行替换，然后使用 eval 转换回矩阵通常更短。我们的最终提交在总共 46 个解决方案中使用了正则表达式。

一个简单的正则表达式例子可以在 Task 294 中看到：

import re
p=lambda g:eval(re.sub("(?<=5.{34})5(?=.{34}5)","2",str(g)))

上述替换将所有灰色像素替换为红色，如果它们位于三个灰色像素的对角线中间。由于网格大小固定（10x10），我们知道对角线连接的像素相距 34 个字符。

对于更复杂的绘图任务，经常使用旋转和替换策略：

p=lambda g:[g:=eval(re.sub("...","...",f"{*zip(*g[::-1]),}"))for _ in g][3]

我们根据任务采用了这种方法的不同变体（列表推导式、递归或循环）。 我们发现的一个有趣的节省一个字节的技巧是 f-string 允许解包，即 f"{*zip(*g[::-1]),}" 对比 str([*zip(*g[::-1])])。

在一些最复杂的任务中，我们利用具有不同表达式的多个替换。一种这样做的方法是：

p=lambda g:[g:=eval(re.sub(*s,f"{*zip(*g[::-1]),}"))for s in[("...","...")]*16+[("...","...")]*4][-1]

因为 re.sub 之后的结果被 eval，替换可以是任何 Python 表达式。这是一些有趣技巧的来源。例如，在 task 154 中，我们使用替换 *[\g<0>][::-1] 来反转匹配的子串。

import re
p=lambda g,k=0:eval(re.sub("[^(2]{9}2"*2+"?","*[\\g<0>][::-1]",f"{*zip(*k or p(g,g)),}"))

“维度”递归

一个概念上困难但非常强大的技术是为不同形状的输入重用函数 p：2D 网格 (list[list[int]])、1D 行 (list[int]) 或 0D 单元格 (int)。在 2D 操作和 1D 操作可以使用重叠代码的情况下，这可以导致显著的节省。有几种变体，但一个模板是：

p=lambda g:g*0!=0and[p(r)for r in g]or F(g)

其中 F 是 int -> int 操作。条件 g*0!=0 检查输入是否是列表，并将 2D/1D 情况与 int 情况分开。例如，task 021：

p=lambda g:g*-1*-1or[p(g:=r)for r in g if g!=r][::2]

在这个任务中，行和列操作可以使用完全相同的代码：跳过相同的连续元素并按 2 下采样。注意这里可以使用公式 g*-1*-1 代替 g*0!=0，因为在此任务中单元格从未有值 0（黑色）。

当利用 p 的额外参数时，此技术变得非常有效。例如，task 040：

p=lambda g,h=[]:g*0!=0and[*map(p,g[:1]*5+g[9:]*5,h+g)]or h%~h&g

此解决方案背后的高级思想是根据网格的最近角落为每个单元格着色。技巧是递归应用 g[:1]*5+g[9:]*5 将产生最近角落的颜色（利用网格始终是 10x10）。在递归结束时，h 将包含当前单元格，g 将包含最近角落。注意 h%~h&g 是一个数学技巧，用于有效地表达 h and g。

猜测与验证

在某些问题中，很难搜索对象，但很容易验证对象是否正确。因此，简单地不断猜测对象直到找到正确的对象更有效。一个例子是 task 124：

p=lambda g,x=0,y=2:(G:=[(i//y*x*[0]+g[i%y])[:10]for i in range(10)])*(G[:4]<g<G)or p(g,~-x%3,y^1)

此任务的目标是扩展高度为 2–3 且水平偏移为 0–2 的模式。在此解决方案中，我们猜测高度 y 和偏移 x 并使用 G[:4]<g<G 检查它是否与输入一致。如果条件为真，函数返回，否则将继续下一个猜测 p(g,~-x%3,y^1)。

内置函数如 max 和 min 也可用于选择正确的猜测。例如，task 216：

p=lambda g:max((-(c:=sum(l:=[r[x%17:x%21]for r in g[x%19:x%22]],g).count)(0),c(2),c(1),l)for x in range(8**6))[3]

很难仅枚举蓝色矩形；枚举每个矩形区域并检查它是否是有效的蓝色矩形要容易得多。为了枚举每个矩形区域，我们使用数学技巧，即 x%17, x%21, x%19, x%22 遍历每个值组合（通过中国剩余定理）。为了挑选出答案，我们使用 max 同时找到最多的红色单元格（通过 c(2)）并验证区域实际上是完整的蓝色矩形，即没有黑色单元格 -c(0) 并且不能用更多蓝色单元格扩展 c(1)。

3x3 邻域迭代器

一种紧凑的迭代网格中所有 3x3 邻域的方法是：

[F(i)for*h,in map(zip,g,g[1:],g[2:])for*i,in map(zip,h,h[1:],h[2:])]

使用 eval/exec，两个 for 子句中的重复可以减少，如我们在 task 271 的解决方案中所见：

exec(f"p=lambda g:max([str(g).count('1'),g]{'for*g,in map(zip,g,g[1:],g[2:])'*2})[1]")

pysearch

许多问题需要小的查找表，例如，一种颜色到另一种颜色的映射。我们广泛使用工具 pysearch 来寻找重现所需输入 - 输出关系的最短表达式。

pysearch 的一个更复杂的用法是寻找可以迭代以产生所需转换的公式。一个例子是 task 282：

使用 pysearch 和自定义代码模拟四次旋转和转换操作，我们发现所需的模式可以用公式 p//5|p^c 产生，其中 p 是前一个颜色（当从左到右扫描每一行时），c 是当前颜色。通过一些巧妙的 eval 和切片递归用法，我们的解决方案是：

p=lambda g:g[99:]or[eval(8*"+(x:=r.pop()),x//5|x^0")for*r,in zip(*p(g*2))]

取巧 (Cheese) 与硬编码

在代码高尔夫术语中，"cheese" 指的是利用评判系统弱点的解决方案，而不是坚持预期的解决方案（类似于机器学习中的过拟合概念）。在这次竞赛中，大多数任务都有数百个测试，所以取巧的机会有限。然而，严重取巧的一个例子是 task 346：

对于人眼来说，意图显然是选择被另一种颜色包围的点的颜色。但这通常是网格中最不频繁的颜色，这在 Python 中更容易表达。通过优化要查看的网格切片，我们可以强制最不频繁的颜色始终与解决方案匹配：

p=lambda g:[[min(f:=sum(g[:6]+g,[])[11:],key=f.count)]]

此外，我们通过硬编码查找表解决了两个问题：task 048 和 task 319。这两个任务只需要 1 位来解决，所以硬编码位表相当有效。（事实上，task 048 每个测试用例需要少于 1 位，因为答案更可能是 8 而不是 0，比例约为 2:1，其熵为 0.92 位。）我们的硬编码技术本身非常有趣，使用网格的哈希与存储在字节字符串中的数据相结合：

(o:=hash((*b"%a"%g,)))//b'data_goes_here'[o%14]%2

可以将额外字节添加到哈希数据 b"%a"%g 以优化查找表的效率，这可以通过暴力搜索。

zlib 压缩

结合 Python 的 zlib 和 exec，可以运行压缩代码。此技术对于长约 200 字节以上的解决方案很有用。为了获得尽可能好的压缩，我们有两个基础设施：

1. 我们使用 zopfli 或 libdeflate 进行初始压缩传递。然而，这些工具不考虑将数据嵌入 Python 脚本的额外成本，即某些字节必须转义。我们编写了一个重新编码器，使用来自 zopfli 或 libdeflate 的相同霍夫曼树，然后使用动态规划寻找最佳编码。
2. 我们使用临时脚本尝试不同的变量名组合，以找到压缩效果最好的。

使用压缩进行高尔夫完全改变了最佳代码大小的技术。压缩使代码重复几乎免费，所以 zlib 高尔夫的目标是反复使用相同的结构，而不是试图为算法的每个步骤寻找最短的结构。

不使用 Shell

值得一提的是，虽然竞赛中允许 Shell 命令（例如 os.popen），并且在某些任务中可能很有用（例如，perl 可用且是一种优秀的高尔夫语言），但根据前 3 名团队之间的相互协议，我们没有使用此技术。原因是该技术的合法性在竞赛后期才得到澄清，而充分探索此技术将为已经很大的工作量增加相当多的工作。

致谢

我们感谢 @garrymoss 的 困难问题的高尔夫解决方案和解释，@kenkrige 的 Chipping skills 3: Regex，以及那里的评论者分享了当时改进了我们最佳方案的解决方案。我们还要感谢所有为公共分数表格做出贡献的人，这是一个宝贵的分数基准来源。