PythonProgrammingPuzzles
1.0.0
该回购包含一个Python编程难题的数据集，可用于教授和评估AI的编程熟练度。我们介绍Openai生成的代码
法典神经网络
解决了许多这些难题。我们希望该数据集将迅速增长，并且在问题难度，域和解决问题所需的算法工具方面已经多样化。请提出一个新的难题或浏览新提出的难题或通过拉动请求做出贡献。
要了解有关GPT-3等AI系统如何解决这些问题的更多信息，请阅读我们的两篇论文：
编程难题。 Tal Schuster，Ashwin Kalyan，Oleksandr Polozov，Adam Tauman Kalai。在第35届神经信息处理系统数据集和基准轨迹（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}
}
要重现该论文中的结果，请参见“求解器”文件夹。
新的自学教学：在我们的第二篇论文中，我们有语言模型（LMS）产生自己的难题，并与Python解释器一起提高了自己的拼图解决能力。遵循我们的论文（Arxiv，2022），有几篇论文通过检查自己的解决方案来改善自身。但是，我们的方法可能会更强大，因为我们的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函数的形式，该功能以答案为论点。答案是一个使函数True的输入。这称为满足难题，这就是为什么难题都被命名为sat的原因。
def sat ( s : str ):
return "Hello " + s == "Hello world"上述难题的答案是字符串"world" ，因为sat("world")返回True 。拼图范围从像这样的琐碎问题到经典难题，到编程竞争问题，一直通过算法和数学的开放问题。
河内难题的经典塔可以写如下：
def sat ( moves : List [ List [ int ]]):
"""
Eight disks of sizes 1-8 are stacked on three towers, with each tower having disks in order of largest to
smallest. Move [i, j] corresponds to taking the smallest disk off tower i and putting it on tower j, and it
is legal as long as the towers remain in sorted order. Find a sequence of moves that moves all the disks
from the first to last towers.
"""
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 ]), "larger disk on top of smaller disk"
return rods [ 0 ] == rods [ 1 ] == []最短的答案是255个动作的列表，因此我们要求AI生成输出答案的代码。在这种情况下，法典API生成以下代码：
def sol ():
# taken from 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个解决方案令人满意。显然，Codex以其他输入格式之前已经看到了这个问题 - 甚至生成了一个URL！ （经过仔细检查，该网站的存在并包含完全不同格式的Hanoi Tower tower代码。
接下来，考虑一个来自CodeForces.com的简单竞争编程问题启发的难题：
def sat ( inds : List [ int ], string = "Sssuubbstrissiingg" ):
"""Find increasing indices to make the substring "substring"""
return inds == sorted ( inds ) and "" . join ( string [ i ] for i in inds ) == "substring"法典生成了下面的代码，当运行时给出有效的答案[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 )同样，有多个有效的答案，这同样是在许多尝试中进行的（10k中只有1个成功）。
需要动态编程的一个更具挑战性的难题是最长增加的子序列问题，我们也可以用字符串描述：
def sat ( x : List [ int ], length = 20 , s = "Dynamic programming solves this classic job-interview puzzle!!!" ):
"""Find the indices of the longest substring with characters in sorted order"""
return all ( s [ x [ i ]] <= s [ x [ i + 1 ]] and x [ i + 1 ] > x [ i ] for i in range ( length - 1 ))法典没有解决这个问题。
该数据集在计算机科学和数学方面也有许多开放问题。例如，
Conway的99-Gaph问题是图理论中未解决的问题（另请参见五个$ 1,000问题（Update 2017））
def sat ( edges : List [ List [ int ]]):
"""
Find an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common
neighbor, and in which each two non-adjacent vertices have exactly two common neighbors.
"""
# first compute neighbors sets, 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（链接将很快添加）
此存储库中的问题基于：
笔记本子目录具有一些相关的笔记本。 Intro.ipynb有十二个难题，指示AI解决了哪些拼图，并且没有在Binder上尝试笔记本，并查看您的编程与AI基线的比较！
Demo.ipynb在用户研究中使用了30个问题。尝试演示笔记本，看看您的编程与AI基线的比较！
在2020年7月27日至29日的Microsoft Hackathon期间，几个人完成了30个用户学习难题。在Hackathon_puzzles.ipynb中，我们也有很多乐趣。这些味道有些不同，因为它们经常被hacks
def sat ( x ):
return x > x x的类型显然是非标准。 The creators of these puzzles include github users: 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。您可以在（要添加链接）上尝试笔记本。
文件split.json包含建议的火车测试拆分。这种拆分是由拼图作者手工选择的，他们熟悉所有难题，因此：两个分裂中相关的难题之间的重叠最少。特别是，对于成对的相关难题，都将两者都放在训练集中或测试集中。
该项目欢迎贡献和建议。利用您的创造力帮助教授AI进行编程！请参阅我们有关如何添加难题的Wiki。
大多数捐款要求您同意撰写贡献者许可协议（CLA），宣布您有权并实际上授予我们使用您的贡献的权利。有关详细信息，请访问https://cla.opensource.microsoft.com。
当您提交拉动请求时，CLA机器人将自动确定您是否需要提供CLA并适当装饰PR（例如状态检查，评论）。只需按照机器人提供的说明即可。您只需要使用我们的CLA在所有存储库中进行一次。
该项目采用了Microsoft开源的行为代码。有关更多信息，请参见《行为守则常见问题守则》或与其他问题或评论联系[email protected]。
请参阅数据集的数据表。
该项目可能包含用于项目，产品或服务的商标或徽标。 Microsoft商标或徽标的授权使用受到了Microsoft的商标和品牌准则的约束。在此项目的修改版本中使用Microsoft商标或徽标不得引起混乱或暗示Microsoft赞助。任何使用第三方商标或徽标都遵守这些第三方政策。
