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, and Varsha Srinivasan.您可以在（要添加鏈接）上嘗試筆記本。
文件split.json包含建議的火車測試拆分。這種拆分是由拼圖作者手工選擇的，他們熟悉所有難題，因此：兩個分裂中相關的難題之間的重疊最少。特別是，對於成對的相關難題，都將兩者都放在訓練集中或測試集中。
該項目歡迎貢獻和建議。利用您的創造力幫助教授AI進行編程！請參閱我們有關如何添加難題的Wiki。
大多數捐款要求您同意撰寫貢獻者許可協議（CLA），宣布您有權並實際上授予我們使用您的貢獻的權利。有關詳細信息，請訪問https://cla.opensource.microsoft.com。
當您提交拉動請求時，CLA機器人將自動確定您是否需要提供CLA並適當裝飾PR（例如狀態檢查，評論）。只需按照機器人提供的說明即可。您只需要使用我們的CLA在所有存儲庫中進行一次。
該項目採用了Microsoft開源的行為代碼。有關更多信息，請參見《行為守則常見問題守則》或與其他問題或評論聯繫[email protected]。
請參閱數據集的數據表。
該項目可能包含用於項目，產品或服務的商標或徽標。 Microsoft商標或徽標的授權使用受到了Microsoft的商標和品牌準則的約束。在此項目的修改版本中使用Microsoft商標或徽標不得引起混亂或暗示Microsoft贊助。任何使用第三方商標或徽標都遵守這些第三方政策。
