PythonProgrammingPuzzles
1.0.0
Repo ini berisi dataset teka -teki pemrograman Python yang dapat digunakan untuk mengajar dan mengevaluasi kemahiran pemrograman AI. Kami menyajikan kode yang dihasilkan oleh Openai
Jaringan Saraf Codex
Memecahkan banyak teka -teki ini. Kami berharap dataset ini akan tumbuh dengan cepat , dan sudah beragam dalam hal kesulitan masalah, domain, dan alat algoritmik yang diperlukan untuk menyelesaikan masalah. Harap usulkan teka -teki baru atau telusuri teka -teki yang baru diusulkan atau berkontribusi melalui permintaan tarik.
Untuk mempelajari lebih lanjut tentang seberapa baik sistem AI seperti GPT-3 dapat menyelesaikan masalah ini, baca dua makalah kami:
Teka -teki pemrograman. Tal Schuster, Ashwin Kalyan, Oleksandr Polozov, Adam Tauman Kalai. Dalam Prosiding Konferensi Ketiga Puluh Lima tentang Dataset Sistem Pemrosesan Informasi Saraf dan Lintasan Benchmarks (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}
}
Untuk mereproduksi hasil di kertas itu, lihat folder Solver.
Pengajaran diri baru: Dalam makalah kedua kami, kami memiliki model bahasa (LMS) menghasilkan teka-teki mereka sendiri dan, bersama dengan penerjemah Python, meningkatkan kemampuan pemecahan teka-teki mereka sendiri. Mengikuti makalah kami (Arxiv, 2022), ada beberapa makalah di mana LM meningkatkan dirinya dengan memeriksa solusinya sendiri. Namun, pendekatan kami berpotensi lebih kuat karena kami memiliki LM menghasilkan masalahnya sendiri, tidak hanya solusinya sendiri.
Model bahasa dapat mengajar diri mereka sendiri untuk memprogram dengan lebih baik. Patrick Haluptzok, Matthew Bowers, Adam Tauman Kalai. Dalam Prosiding Konferensi Internasional Kesebelas tentang Representasi Pembelajaran (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}
}
Untuk mereproduksi hasil di kertas itu, lihat folder ICLR2023.
Jika Anda hanya ingin menyelam untuk memecahkan beberapa teka -teki, cobalah notebook intro di binder yang menunjukkan teka -teki mana yang dipecahkan oleh baseline AI dan yang tidak mereka miliki, sehingga Anda dapat melihat bagaimana pemrograman Anda membandingkan.
Setiap teka -teki mengambil bentuk fungsi python yang mengambil jawaban sebagai argumen. Jawabannya adalah input yang membuat fungsi mengembalikan True . Ini disebut memuaskan teka -teki, dan itulah sebabnya teka -teki itu semua bernama sat .
def sat ( s : str ):
return "Hello " + s == "Hello world" Jawaban untuk teka -teki di atas adalah string "world" karena sat("world") kembali True . Teka -teki berkisar dari masalah sepele seperti ini, hingga teka -teki klasik, hingga masalah kompetisi pemrograman, sepanjang jalan melalui masalah terbuka dalam algoritma dan matematika.
Menara klasik teka -teki Hanoi dapat ditulis sebagai berikut:
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 ] == []Jawaban terpendek adalah daftar 255 gerakan, jadi sebaliknya kami meminta AI untuk menghasilkan kode yang menghasilkan jawaban. Dalam hal ini, API Codex menghasilkan kode berikut:
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 movesIni bukan pada percobaan pertama, tetapi itu adalah salah satu keuntungan dari teka-teki --- mudah bagi komputer untuk memeriksa jawabannya sehingga dapat menghasilkan banyak jawaban sampai menemukannya. Untuk teka -teki ini, sekitar 1 dari 1.000 solusi memuaskan. Jelas, Codex telah melihat masalah ini sebelumnya dalam format input lain --- bahkan menghasilkan URL! ;
Selanjutnya, pertimbangkan teka -teki yang terinspirasi oleh masalah pemrograman kompetitif yang mudah ini dari situs web 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 menghasilkan kode di bawah ini, yang saat dijalankan memberikan jawaban yang valid [1, 3, 5, 7, 8, 9, 10, 15, 16] . Ini memenuhi teka -teki ini karena ini adalah daftar indeks yang meningkat yang jika Anda bergabung dengan karakter "Sssuubbstrissiingg" dalam indeks ini Anda mendapatkan "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 )Sekali lagi, ada beberapa jawaban yang valid, dan sekali lagi ini keluar dari banyak upaya (hanya 1 keberhasilan dalam 10k).
Teka -teki yang lebih menantang yang membutuhkan pemrograman dinamis adalah masalah selanjutnya yang semakin meningkat yang juga dapat kita gambarkan dengan string:
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 ))Codex tidak menyelesaikan yang ini.
Dataset juga memiliki sejumlah masalah terbuka dalam ilmu komputer dan matematika. Misalnya,
Masalah 99-grafik Conway adalah masalah yang belum terpecahkan dalam teori grafik (lihat juga lima masalah $ 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 ))Mengapa teka -teki? Salah satu alasannya adalah, jika kita dapat menyelesaikannya lebih baik daripada pemrogram manusia, maka kita dapat membuat kemajuan pada beberapa masalah algoritma penting. Tetapi sampai saat itu, alasan kedua adalah karena mereka dapat berharga untuk melatih dan mengevaluasi sistem AI. Banyak set data pemrograman telah diusulkan selama bertahun -tahun, dan beberapa memiliki masalah yang sama (seperti masalah kompetisi pemrograman). Dalam teka-teki, spesifikasi didefinisikan oleh kode, sedangkan set data lainnya biasanya menggunakan kombinasi bahasa Inggris dan set tes tersembunyi dari pasangan input-output. Spesifikasi berbasis bahasa Inggris terkenal ambigu dan menguji pemahaman sistem tentang bahasa Inggris. Dan dengan kasus uji input-output, Anda harus memecahkan teka-teki sebelum Anda berpose, jadi apa gunanya di sana? Spesifikasi berbasis kode memiliki keuntungan bahwa mereka tidak ambigu, tidak perlu men-debug kode yang dihasilkan AI atau khawatir itu tidak melakukan apa yang Anda inginkan. Jika memecahkan teka -teki, maka itu berhasil menurut definisi.
Untuk informasi lebih lanjut tentang motivasi dan bagaimana teka -teki pemrograman dapat membantu AI belajar memprogram, lihat makalah:
Pemrograman Teka -teki , oleh Tal Schuster, Ashwin Kalyan, Alex Polozov, dan Adam Tauman Kalai. 2021 (tautan yang akan ditambahkan segera)
Masalah dalam repo ini didasarkan pada:
Subdirektori notebook memiliki beberapa buku catatan yang relevan. Intro.ipynb memiliki selusin teka -teki yang menunjukkan mana yang diselesaikan AI dan tidak mencoba notebook di binder dan lihat bagaimana pemrograman Anda dibandingkan dengan garis dasar AI!
Demo.ipynb memiliki 30 masalah yang diselesaikan oleh pengguna kami dalam studi pengguna. Coba Demo Notebook dan lihat bagaimana pemrograman Anda dibandingkan dengan AI Baselines!
Selama Microsoft Hackathon 27-29 Juli 2020, beberapa orang menyelesaikan 30 teka-teki studi pengguna. Kami juga bersenang -senang membuat teka -teki di hackathon_puzzles.ipynb. Ini adalah rasa yang agak berbeda karena lebih sering hacks
def sat ( x ):
return x > x di mana jenis x jelas tidak standar. Pencipta teka -teki ini termasuk pengguna 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, MoniP Mykhailova, Misha Jaiswal, Saikiran Mullaguri, Tal Schuster, dan Varsha Srinivasan. Anda dapat mencoba notebook di (tautan yang akan ditambahkan).
File split.json berisi perpecahan uji-kereta yang disarankan. Perpecahan ini dipilih dengan tangan oleh penulis puzzle, yang akrab dengan semua teka-teki, sehingga: ada tumpang tindih minimal antara teka-teki terkait dalam dua pemisahan. Secara khusus, untuk pasangan teka -teki terkait, keduanya ditempatkan di set pelatihan atau set tes.
Proyek ini menyambut kontribusi dan saran. Gunakan kreativitas Anda untuk membantu mengajar AI untuk memprogram! Lihat wiki kami tentang cara menambahkan teka -teki.
Sebagian besar kontribusi mengharuskan Anda untuk menyetujui perjanjian lisensi kontributor (CLA) yang menyatakan bahwa Anda memiliki hak untuk, dan benar -benar melakukannya, beri kami hak untuk menggunakan kontribusi Anda. Untuk detailnya, kunjungi https://cla.opensource.microsoft.com.
Saat Anda mengirimkan permintaan tarik, bot CLA akan secara otomatis menentukan apakah Anda perlu memberikan CLA dan menghiasi PR secara tepat (misalnya, pemeriksaan status, komentar). Cukup ikuti instruksi yang disediakan oleh bot. Anda hanya perlu melakukan ini sekali di semua repo menggunakan CLA kami.
Proyek ini telah mengadopsi kode perilaku open source Microsoft. Untuk informasi lebih lanjut, lihat FAQ Kode Perilaku atau hubungi [email protected] dengan pertanyaan atau komentar tambahan.
Lihat lembar data untuk dataset kami.
Proyek ini dapat berisi merek dagang atau logo untuk proyek, produk, atau layanan. Penggunaan resmi merek dagang atau logo Microsoft tunduk dan harus mengikuti pedoman merek dagang & merek Microsoft. Penggunaan merek dagang atau logo Microsoft dalam versi yang dimodifikasi dari proyek ini tidak boleh menyebabkan kebingungan atau menyiratkan sponsor Microsoft. Setiap penggunaan merek dagang atau logo pihak ketiga tunduk pada kebijakan pihak ketiga tersebut.
