Python 编程谜题 (P3)

本仓库包含一个 Python 编程谜题数据集，可用于教学和评估 AI 的编程能力。我们展示了 OpenAI 的 codex 神经网络在解决这些谜题时生成的代码。我们希望这个数据集能快速增长，它在问题难度、领域和解决问题所需的算法工具方面已经很多样化。请提出新谜题或浏览新提出的谜题，或通过拉取请求贡献。

要了解 GPT-3 等 AI 系统如何解决这些问题，请阅读我们的两篇论文：

编程谜题。Tal Schuster、Ashwin Kalyan、Oleksandr Polozov、Adam Tauman Kalai。发表于第三十五届神经信息处理系统会议数据集和基准轨道 (NeurIPS)，2021年。

@inproceedings{
schuster2021programming,
title={Programming Puzzles},
author={Tal Schuster and Ashwin Kalyan and Alex Polozov and Adam Tauman Kalai},
booktitle={Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track},
year={2021},
url={https://arxiv.org/abs/2106.05784}
}

要复现该论文的结果，请查看 solvers 文件夹。

新的自学方法： 在我们的第二篇论文中，我们让语言模型(LMs)生成自己的谜题，并与 Python 解释器一起提高自身解谜能力。继我们的论文(arXiv，2022年)之后，出现了几篇论文，其中 LM 通过检查自己的解决方案来改进自身。然而，我们的方法可能更强大，因为我们让 LM 生成自己的问题，而不仅仅是自己的解决方案。

语言模型可以自学编程以提高能力。Patrick Haluptzok、Matthew Bowers、Adam Tauman Kalai。发表于第十一届国际学习表示会议 (ICLR)，2023年。

@inproceedings{
haluptzok2022selfteach,
title={Language Models Can Teach Themselves to Program Better},
author={Patrick Haluptzok, Matthew Bowers, Adam Tauman Kalai},
booktitle={Eleventh International Conference on Learning Representations (ICLR)},
year={2023},
url=https://arxiv.org/abs/2207.14502}
}

要复现该论文的结果，请查看 ICLR2023 文件夹。

如果你想直接开始解决一些谜题，可以尝试 Binder 上的入门笔记本，它展示了 AI 基线解决和未解决的谜题，让你可以比较自己的编程水平。

什么是 Python 编程谜题？

每个谜题都是一个 Python 函数的形式，该函数接受一个答案作为参数。答案是一个输入，使函数返回 True。这被称为满足谜题，这就是为什么所有谜题都命名为 sat。

def sat(s: str):
    return "Hello " + s == "Hello world"

上面谜题的答案是字符串 "world"，因为 sat("world") 返回 True。谜题的范围从像这样的琐碎问题，到经典谜题，再到编程竞赛问题，甚至包括算法和数学中的未解决问题。

经典的汉诺塔谜题可以这样写：

def sat(moves: List[List[int]]):  
    """
    八个大小为 1-8 的圆盘堆叠在三个塔上，每个塔上的圆盘按从大到小的顺序排列。移动 [i, j] 对应于从塔 i 取下最小的圆盘并放在塔 j 上，只要塔保持排序顺序，这种移动就是合法的。找到一系列移动，将所有圆盘从第一个塔移动到最后一个塔。
    """
    rods = ([8, 7, 6, 5, 4, 3, 2, 1], [], [])
    for [i, j] in moves:
        rods[j].append(rods[i].pop())
        assert rods[j][-1] == min(rods[j]), "较大的圆盘在较小圆盘上面"
    return rods[0] == rods[1] == []

最短的答案是一个包含 255 个移动的列表，所以我们要求 AI 生成输出答案的代码。在这种情况下，codex API 生成了以下代码：

def sol():
    # 来自 https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/
    moves = []
    def hanoi(n, source, temp, dest):
        if n > 0:
            hanoi(n - 1, source, dest, temp)
            moves.append([source, dest])
            hanoi(n - 1, temp, source, dest)
    hanoi(8, 0, 1, 2)
    return moves

这不是它的第一次尝试，但这就是谜题的优势之一——计算机很容易检查答案，所以它可以生成许多答案，直到找到一个满意的答案。对于这个谜题，大约每 1,000 个解决方案中有 1 个是令人满意的。显然，codex 以前在其他输入格式中见过这个问题——它甚至生成了一个 url！（仔细检查后，该网站确实存在，并包含完全不同格式和不同变量名的 Python 汉诺塔代码。）在一个更难、不太标准的汉诺塔谜题变体中，需要从特定的起始位置移动到结束位置，codex 在 10,000 次尝试中都没有解决它。

接下来，考虑一个受 codeforces.com 网站上这个简单的竞赛编程问题启发的谜题：

def sat(inds: List[int], string="Sssuubbstrissiingg"):
    """找到递增的索引，使其构成子字符串 "substring" """
    return inds == sorted(inds) and "".join(string[i] for i in inds) == "substring"

Codex 生成了以下代码，运行后给出了有效答案 [1, 3, 5, 7, 8, 9, 10, 15, 16]。这满足了谜题，因为它是一个递增的索引列表，如果你连接这些索引处 "Sssuubbstrissiingg" 的字符，你会得到 "substring"。

def sol(string="Sssuubbstrissiingg"):
    x = "substring"
    pos = string.index(x[0])
    inds = [pos]
    while True:
        x = x[1:]
        if not x:
            return inds
        pos = string.find(x[0], pos+1)
        if pos == -1:
            return inds
        inds.append(pos)

同样，这里有多个有效答案，而且这也是经过多次尝试的结果（10,000 次中只有 1 次成功）。

一个更具挑战性的谜题，需要动态规划的是最长递增子序列问题，我们也可以用字符串来描述：

def sat(x: List[int], length=20, s="Dynamic programming solves this classic job-interview puzzle!!!"):
    """找到字符按排序顺序的最长子串的索引"""
    return all(s[x[i]] <= s[x[i + 1]] and x[i + 1] > x[i] for i in range(length - 1))

Codex 没有解决这个问题。

该数据集还包含一些计算机科学和数学中的未解决问题。例如，Conway 的 99 图问题是图论中一个未解决的问题（另见五个 $1,000 问题（2017 年更新））

def sat(edges: List[List[int]]):
    """
    找到一个有 99 个顶点的无向图，其中每两个相邻顶点恰好有一个共同邻居，每两个不相邻顶点恰好有两个共同邻居。
    """
    # 首先计算邻居集合 N：
    N = {i: {j for j in range(99) if j != i and ([i, j] in edges or [j, i] in edges)} for i in range(99)}
    return all(len(N[i].intersection(N[j])) == (1 if j in N[i] else 2) for i in range(99) for j in range(i))

为什么是谜题？一个原因是，如果我们能比人类程序员更好地解决它们，那么我们就可以在一些重要的算法问题上取得进展。但在此之前，第二个原因是它们可以用于训练和评估 AI 系统。多年来，人们提出了许多编程数据集，其中几个包含类似性质的问题（如编程竞赛问题）。在谜题中，规范是由代码定义的，而其他数据集通常使用英语和隐藏的输入-输出对测试集的组合。基于英语的规范众所周知是模糊的，并测试系统对英语的理解。而对于输入-输出测试用例，你必须在提出谜题之前就解决了它，那么这有什么用呢？基于代码的规范的优势在于它们是明确的，不需要调试 AI 生成的代码或担心它不能做你想要的事。如果它解决了谜题，那么根据定义它就成功了。

有关动机以及编程谜题如何帮助 AI 学习编程的更多信息，请参阅论文： 编程谜题，作者：Tal Schuster、Ashwin Kalyan、Alex Polozov 和 Adam Tauman Kalai。2021 年（链接将很快添加）

点击此处浏览谜题和解决方案

本仓库中的问题基于：

关于算法、谜题和数学问题的维基百科文章。
网站 codeforces.com，一个流行的编程竞赛问题网站。
来自国际大学生程序设计竞赛和国际数学奥林匹克的奥林匹克问题。
（新增！）受 codex 论文中 human-eval 数据集启发的问题。

笔记本

notebooks 子目录包含一些相关的笔记本。Intro.ipynb 包含十几个谜题，指出了 AI 解决和未解决的谜题在 Binder 上尝试笔记本，看看你的编程水平如何与 AI 基线相比较！

Demo.ipynb 包含我们用户在用户研究中完成的 30 个问题。尝试演示笔记本，看看你的编程水平如何与 AI 基线相比较！

黑客马拉松

2020年7月27日至29日，在微软举办的黑客马拉松期间，多人完成了30个用户研究谜题。我们还在Hackathon_puzzles.ipynb中创造谜题时玩得很开心。这些谜题风格略有不同，因为它们更多的是"黑客"式的，比如：

def sat(x):
    return x > x

这里x的类型显然是非标准的。这些谜题的创作者包括以下GitHub用户： Adam Tauman Kalai、 Alec Helbling、 Alexander Vorobev、 Alexander Wei、 Alexey Romanov、 Keith Battaochi、 Kodai Sudo、 Maggie Hei、 Mariia Mykhailova、 Misha Khodak、 Monil Mehta、 Philip Rosenfield、 Qida Ma、 Raj Bhargava、 Rishi Jaiswal、 Saikiran Mullaguri、 Tal Schuster和 Varsha Srinivasan。你可以在（链接待添加）尝试这个notebook。

亮点

许多简单的谜题，如反转列表，对学习编程很有帮助
经典谜题如：
- 汉诺塔
- 字母算术（解决数字替换问题，如SEND + MORE = MONEY）
- 生命游戏（例如，找出给定周期的振荡器，一些未解决）
- 国际象棋谜题（如骑士巡游和N皇后问题变体）
双人游戏
- 找出井字游戏、石头剪刀布、大师心眼的最优策略（待添加：四子棋？）
- 找出零和双矩阵游戏的极小极大策略，等同于线性规划
- 找出一般和游戏的纳什均衡（未解决，PPAD完全问题）
数学和编程竞赛
- 国际数学奥林匹克（IMO）题目
- 国际大学生程序设计竞赛（ICPC）题目
- 来自codeforces.com的竞赛编程题目
图论算法谜题
- 最短路径
- 植入团（未解决）
初等代数
- 解方程
- 解二次、三次和四次方程
数论算法谜题：
- 找出公约数（如使用欧几里得算法）
- 因数分解（小因数容易，大数未解决，已颁发超过10万美元奖金）
- 离散对数（一般情况未解决，某些情况容易）
格
- 学习奇偶性（通常用高斯消元法解决）
- 带噪声的奇偶性学习（未解决）
压缩
- 给定解压缩算法（但不给压缩算法）压缩给定字符串，或仅给定压缩算法解压缩给定的压缩字符串
- （待添加：计算霍夫曼树）
困难数学问题
- Conway的99图问题（未解决）
- 在Collatz过程中找到一个循环（未解决）