PythonProgrammingPuzzles
1.0.0
repo นี้มีชุดข้อมูลของปริศนาการเขียนโปรแกรม Python ซึ่งสามารถใช้ในการสอนและประเมินความสามารถในการเขียนโปรแกรมของ AI เรานำเสนอรหัสที่สร้างโดย Openai's
เครือข่ายประสาท Codex
การแก้ปริศนาเหล่านี้มากมาย เราหวังว่าชุดข้อมูลนี้จะ เติบโตอย่างรวดเร็ว และมีความหลากหลายในแง่ของปัญหาปัญหาโดเมนและเครื่องมืออัลกอริทึมที่จำเป็นในการแก้ปัญหา โปรดเสนอปริศนาใหม่หรือเรียกดูปริศนาที่เสนอใหม่หรือมีส่วนร่วมผ่านคำขอดึง
หากต้องการเรียนรู้เพิ่มเติมเกี่ยวกับระบบ AI ที่ดีเช่น GPT-3 สามารถแก้ปัญหาเหล่านี้ได้อ่านเอกสารสองฉบับของเรา:
การเขียนโปรแกรมปริศนา 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 baselines แก้ไขและสิ่งที่พวกเขาไม่ได้ดังนั้นคุณจะเห็นว่าการเขียนโปรแกรมของคุณเปรียบเทียบอย่างไร
ปริศนาแต่ละตัวใช้รูปแบบของฟังก์ชัน 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 สร้าง รหัส ที่ส่งออกคำตอบ ในกรณีนี้ 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 โซลูชั่นเป็นที่น่าพอใจ เห็นได้ชัดว่า Codex เคยเห็นปัญหานี้มาก่อนในรูปแบบอินพุตอื่น ๆ --- มันสร้าง URL! (เมื่อตรวจสอบอย่างใกล้ชิดเว็บไซต์มีอยู่และมีรหัส Python Tower-of-Hanoi ในรูปแบบที่แตกต่างกันอย่างสิ้นเชิงกับชื่อตัวแปรที่แตกต่างกัน) ในตัวแปรปริศนาฮานอยที่ยากและมาตรฐานที่ยากขึ้นซึ่งต้องการการย้ายจากจุดเริ่มต้นโดยเฉพาะ
ถัดไปพิจารณาปริศนาที่ได้รับแรงบันดาลใจจากปัญหาการเขียนโปรแกรมที่แข่งขันได้ง่ายจากเว็บไซต์ 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 )อีกครั้งมีคำตอบที่ถูกต้องหลายคำและอีกครั้งนี่เป็นความพยายามหลายครั้ง (เพียง 1 ความสำเร็จใน 10k)
ปริศนาที่ท้าทายมากขึ้นที่ต้องใช้การเขียนโปรแกรมแบบไดนามิกคือปัญหาที่เพิ่มขึ้นนานที่สุดซึ่งเราสามารถอธิบายได้ด้วยสตริง:
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 ไม่ได้แก้ปัญหานี้
ชุดข้อมูลยังมีปัญหาเปิดกว้างในวิทยาศาสตร์คอมพิวเตอร์และคณิตศาสตร์ ตัวอย่างเช่น,
ปัญหา 99 กราฟของ Conway เป็นปัญหาที่ยังไม่ได้แก้ไขในทฤษฎีกราฟ (ดูปัญหาห้า $ 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 ))ทำไมต้องปริศนา? เหตุผลหนึ่งคือถ้าเราสามารถแก้ปัญหาได้ดีกว่าโปรแกรมเมอร์ของมนุษย์เราก็สามารถดำเนินการตามปัญหาอัลกอริทึมที่สำคัญบางอย่างได้ แต่ก่อนหน้านี้เหตุผลที่สองคือพวกเขามีค่าสำหรับการฝึกอบรมและประเมินระบบ AI ชุดข้อมูลการเขียนโปรแกรมจำนวนมากได้รับการเสนอในช่วงหลายปีที่ผ่านมาและหลายชุดมีปัญหาในลักษณะที่คล้ายกัน (เช่นปัญหาการแข่งขันการเขียนโปรแกรม) ในปริศนาข้อมูลจำเพาะถูกกำหนดโดยรหัสในขณะที่ชุดข้อมูลอื่น ๆ มักจะใช้การรวมกันของภาษาอังกฤษและชุดทดสอบที่ซ่อนอยู่ของคู่อินพุตเอาต์พุต สเป็คที่ใช้ภาษาอังกฤษมีความคลุมเครืออย่างฉาวโฉ่และทดสอบความเข้าใจของระบบภาษาอังกฤษ และด้วยกรณีทดสอบอินพุตเอาท์พุตคุณจะต้องแก้ไขปริศนาก่อนที่คุณจะโพสต์ดังนั้นการใช้งานที่นั่นคืออะไร? ข้อมูลจำเพาะที่ใช้รหัสมีข้อได้เปรียบที่ไม่คลุมเครือไม่จำเป็นต้องดีบักรหัส Ai-Generated หรือกลัวว่ามันไม่ได้ทำในสิ่งที่คุณต้องการ ถ้ามันแก้ไขปริศนาก็จะประสบความสำเร็จโดยนิยาม
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับแรงจูงใจและวิธีการที่การเขียนโปรแกรมปริศนาสามารถช่วย AI เรียนรู้การโปรแกรมดูกระดาษ:
การเขียนโปรแกรมปริศนา โดย Tal Schuster, Ashwin Kalyan, Alex Polozov และ Adam Tauman Kalai 2021 (ลิงก์ที่จะเพิ่มในไม่ช้า)
ปัญหาใน repo นี้ขึ้นอยู่กับ:
ไดเรกทอรีย่อยโน้ตบุ๊กมีสมุดบันทึกที่เกี่ยวข้อง Intro.ipynb มีปริศนาโหลที่ระบุว่าอันไหนที่ AI แก้ไขและไม่ได้ลองสมุดบันทึกที่ Binder และดูว่าการเขียนโปรแกรมของคุณเปรียบเทียบกับ AI baselines ได้อย่างไร!
Demo.ipynb มีปัญหา 30 ครั้งที่ผู้ใช้ของเราเสร็จสิ้นในการศึกษาผู้ใช้ ลองสมุดบันทึกการสาธิตและดูว่าการเขียนโปรแกรมของคุณเปรียบเทียบกับ AI baselines ได้อย่างไร!
ในช่วง Microsoft Hackathon 27-29 กรกฎาคม 2020 หลายคนเสร็จสิ้นการศึกษาผู้ใช้ 30 คน นอกจากนี้เรายังมีความสนุกสนานมากมายในการสร้างปริศนาใน hackathon_puzzles.ipynb เหล่านี้มีรสชาติที่แตกต่าง hacks บ้าง
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 Jaiswal, Saikiran Mullaguri, Tal Schuster และ Varsha Srinivasan คุณสามารถลองโน้ตบุ๊กที่ (ลิงก์ที่จะเพิ่ม)
File split.json มีการแยกการทดสอบรถไฟที่แนะนำ การแยกนี้ถูกเลือกด้วยมือโดยผู้เขียนปริศนาที่คุ้นเคยกับปริศนาทั้งหมดดังนั้น: มีการทับซ้อนกันน้อยที่สุดระหว่างปริศนาที่เกี่ยวข้องในการแยกทั้งสอง โดยเฉพาะอย่างยิ่งสำหรับคู่ของปริศนาที่เกี่ยวข้องทั้งสองถูกวางไว้ในชุดการฝึกอบรมหรือชุดทดสอบ
โครงการนี้ยินดีต้อนรับการมีส่วนร่วมและข้อเสนอแนะ ใช้ความคิดสร้างสรรค์ของคุณเพื่อช่วยสอนโปรแกรมให้ AI! ดูวิกิของเราเกี่ยวกับวิธีการเพิ่มปริศนา
การมีส่วนร่วมส่วนใหญ่กำหนดให้คุณต้องยอมรับข้อตกลงใบอนุญาตผู้มีส่วนร่วม (CLA) ประกาศว่าคุณมีสิทธิ์และทำจริงให้สิทธิ์ในการใช้การบริจาคของคุณ สำหรับรายละเอียดเยี่ยมชม https://cla.opensource.microsoft.com
เมื่อคุณส่งคำขอดึง CLA บอทจะพิจารณาโดยอัตโนมัติว่าคุณจำเป็นต้องให้ CLA และตกแต่ง PR อย่างเหมาะสม (เช่นการตรวจสอบสถานะแสดงความคิดเห็น) เพียงทำตามคำแนะนำที่จัดทำโดยบอท คุณจะต้องทำสิ่งนี้เพียงครั้งเดียวใน repos ทั้งหมดโดยใช้ CLA ของเรา
โครงการนี้ได้นำรหัสการดำเนินงานของ Microsoft โอเพ่นซอร์สมาใช้ สำหรับข้อมูลเพิ่มเติมโปรดดูจรรยาบรรณคำถามที่พบบ่อยหรือติดต่อ [email protected] พร้อมคำถามหรือความคิดเห็นเพิ่มเติมใด ๆ
ดูแผ่นข้อมูลสำหรับชุดข้อมูลของเรา
โครงการนี้อาจมีเครื่องหมายการค้าหรือโลโก้สำหรับโครงการผลิตภัณฑ์หรือบริการ การใช้เครื่องหมายการค้าหรือโลโก้ของ Microsoft ที่ได้รับอนุญาตขึ้นอยู่กับและต้องปฏิบัติตามแนวทางเครื่องหมายการค้าและแบรนด์ของ Microsoft การใช้เครื่องหมายการค้าหรือโลโก้ของ Microsoft ในรุ่นที่แก้ไขของโครงการนี้จะต้องไม่ทำให้เกิดความสับสนหรือบอกเป็นสปอนเซอร์ของ Microsoft การใช้เครื่องหมายการค้าหรือโลโก้ของบุคคลที่สามจะอยู่ภายใต้นโยบายของบุคคลที่สามเหล่านั้น
