PythonProgrammingPuzzles
1.0.0
このレポは、AIのプログラミング能力を教えて評価するために使用できるPythonプログラミングパズルのデータセットが含まれています。 Openaiによって生成されたコードを提示します
Codex Neural Network
これらのパズルの多くを解決します。このデータセットが急速に成長することを願っています。問題を解決するために必要な問題の難易度、ドメイン、およびアルゴリズムツールの点ですでに多様であることを願っています。新しいパズルを提案するか、新しく提案されたパズルを閲覧するか、プルリクエストを通じて貢献してください。
GPT-3などのAIシステムがこれらの問題を解決できる方法について詳しく知るには、2つの論文を読んでください。
プログラミングパズル。タル・シュスター、アシュウィン・カリャン、オレクサンドル・ポロゾフ、アダム・タウマン・カライ。神経情報処理システムデータセットとベンチマークトラック（ニューリップ）に関する第35回会議の議事録、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}
}
その論文で結果を再現するには、ソルバーフォルダーを参照してください。
新しいセルフエーキング： 2番目の論文では、言語モデル（LMS）が独自のパズルを生成し、Pythonインタープリターとともに独自のパズル解決機能を改善しています。私たちの論文（Arxiv、2022）に続いて、LMが独自のソリューションをチェックすることでそれ自体を改善するいくつかの論文がありました。ただし、LMに独自のソリューションだけでなく、LMが独自の問題を生成しているため、アプローチはより強力です。
言語モデルは、より良いプログラムを教えることができます。パトリック・ハルプゾック、マシュー・バウアーズ、アダム・タウマン・カライ。学習表現に関する第11回国際会議（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フォルダーを参照してください。
いくつかのパズルの解決にすぐに飛び込みたい場合は、AIのベースラインが解決し、どのパズルではなかったかを示すIntro Notebookをバインダーで試してみてください。
各パズルは、引数として答えを得るPython関数の形をとります。答えは、関数を返すTrueにする入力です。これはパズルの満足度と呼ばれ、それがパズルのすべてのsatという名前です。
def sat ( s : str ):
return "Hello " + s == "Hello world"上記のパズルに対する答えはsat("world") Trueであるため、文字列"world"です。パズルは、このような些細な問題から、古典的なパズル、競争の問題をプログラミングするまで、アルゴリズムや数学のオープンな問題を通じて、さまざまです。
ハノイパズルの古典的な塔は、次のように書くことができます。
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に回答を出力するコードを生成するように依頼します。この場合、Codex 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つです。コンピューターが回答を確認して、それが見つかるまで多くの回答を生成できるようにするのは簡単です。このパズルでは、1,000人に約1人のソリューションが満足のいくものでした。明らかに、Codexは以前に他の入力形式でこの問題を見てきました---それはURLを生成しました！ （綿密な検査で、ウェブサイトは存在し、異なる変数名を持つまったく異なる形式でPythonタワーオブハノイコードを含みます。）特定の開始位置から終了位置への移動を必要とするより硬い、標準の少ないハノイパズルバリアントでは、コーデックスは10,000回の試行でそれを解決しませんでした。
次に、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" 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 )繰り返しますが、複数の有効な回答があり、これも多くの試みから外れていました（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グラフの問題は、グラフ理論における未解決の問題です（5つの$ 1,000の問題（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 ))なぜパズル？理由の1つは、人間のプログラマーよりもうまく解決できれば、いくつかの重要なアルゴリズムの問題を進歩させることができるということです。しかし、それまでは、2番目の理由は、AIシステムのトレーニングと評価に役立つ可能性があることです。多くのプログラミングデータセットが長年にわたって提案されており、いくつかは同様の性質の問題を抱えています（競争の問題をプログラミングするなど）。パズルでは、スペックはコードで定義されますが、他のデータセットは通常、英語と入出力ペアの隠されたテストセットの組み合わせを使用します。英語ベースの仕様は曖昧であることで有名であり、システムの英語の理解をテストします。そして、入出力テストのケースでは、ポーズをとる前にパズルを解決しなければならないので、そこでの使用は何ですか？コードベースの仕様には、それらが明確であるという利点があります。AI生成されたコードや、それがあなたが望むことをしないという恐怖をデバッグする必要はありません。パズルを解決した場合、定義上成功します。
動機付けとプログラミングパズルがAIがプログラムを学ぶのに役立つ方法の詳細については、次のようなものを参照してください。
プログラミングパズル、Tal Schuster、Ashwin Kalyan、Alex Polozov、Adam Tauman Kalaiによる。 2021（まもなく追加するリンク）
このリポジトリの問題は以下に基づいています。
ノートブックサブディレクトリには、関連するノートブックがいくつかあります。 Intro.ipynbには、AIがどのAIが解決したかを示すパズルが数十個あり、バインダーでノートブックを試していないことを示し、プログラミングがAIベースラインとどのように比較されるかを確認しませんでした。
Demo.ipynbには、ユーザー調査でユーザーが完了した30の問題があります。デモノートブックを試して、プログラミングがAIベースラインとどのように比較されるかを確認してください！
2020年7月27〜29日にMicrosoft Hackathonで、数人の人々が30のユーザー調査パズルを完了しました。また、hackathon_puzzles.ipynbでパズルを作る楽しいこともたくさんありました。これらは、より頻繁にhacksするので、やや異なる風味です
def sat ( x ):
return x > x xのタイプは明らかに非標準です。これらのパズルの作成者には、Githubユーザーが含まれます。AdamTaumanKalai、Alec Helbling、Alexander Vorobev、Alexander Wei、Alexey Romanov、Keith Battaochi、Kodai Sudo、Maggie Hei、Mariia Mykhailova、Misha Khodak、Monil Mehta Jaiswal、Saikiran Mullaguri、Tal Schuster、Varsha Srinivasan。 （追加するリンク）のノートブックを試すことができます。
ファイルsplit.jsonには、推奨される列車テストの分割が含まれています。この分割は、すべてのパズルに精通しているパズルの著者によって手で選択されたため、次のようになります。2つのスプリットの関連パズル間には最小限のオーバーラップがあります。特に、関連するパズルのペアの場合、両方がトレーニングセットまたはテストセットに配置されました。
このプロジェクトは、貢献と提案を歓迎します。あなたの創造性を使用して、AIのプログラムを教えるのを手伝ってください！パズルを追加する方法については、Wikiをご覧ください。
ほとんどの貢献では、貢献者ライセンス契約（CLA）に同意する必要があります。詳細については、https：//cla.opensource.microsoft.comをご覧ください。
プルリクエストを送信すると、CLAボットはCLAを提供し、PRを適切に飾る必要があるかどうかを自動的に決定します（たとえば、ステータスチェック、コメント）。ボットが提供する指示に従うだけです。 CLAを使用して、すべてのレポでこれを1回だけ行う必要があります。
このプロジェクトは、Microsoftのオープンソース行動規範を採用しています。詳細については、FAQのコードを参照するか、追加の質問やコメントについては[email protected]にお問い合わせください。
データセットのデータシートを参照してください。
このプロジェクトには、プロジェクト、製品、またはサービスの商標またはロゴが含まれる場合があります。 Microsoftの商標またはロゴの承認された使用は、Microsoftの商標およびブランドガイドラインに従うものであり、従わなければなりません。このプロジェクトの変更されたバージョンでのMicrosoft商標またはロゴの使用は、混乱を引き起こしたり、Microsoftのスポンサーシップを暗示したりしてはなりません。サードパーティの商標またはロゴの使用は、これらのサードパーティのポリシーの対象となります。
