PythonProgrammingPuzzles
1.0.0
Dieses Repo enthält einen Datensatz von Python -Programmierpuzzles, mit denen die Programmierkenntnisse einer KI unterrichtet und bewertet werden können. Wir präsentieren Code, der von OpenAI generiert wird
Codex Neurales Netzwerk
viele dieser Rätsel lösen. Wir hoffen, dass dieser Datensatz schnell wächst und in Bezug auf Problemschwierigkeits-, Domänen- und algorithmische Tools, die zur Lösung der Probleme benötigt werden, bereits unterschiedlich ist. Bitte schlagen Sie ein neues Puzzle vor oder stöbern Sie neu vorgeschlagene Rätsel oder tragen Sie durch Pull -Anfragen bei.
Um mehr darüber zu erfahren, wie gut KI-Systeme wie GPT-3 diese Probleme lösen können, lesen Sie unsere beiden Papiere:
Programmierrätsel. Tal Schuster, Ashwin Kalyan, Oleksandr Polozov, Adam Tauman Kalai. In Proceedings der fünfunddreißigsten Konferenz über Datensätze und Benchmarks (Neurips), 2021, in neuronalen Informationsverarbeitungssystemen .
@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}
}
Um die Ergebnisse in diesem Papier zu reproduzieren, finden Sie im Ordner Solvers.
Neue Selbstunterricht: In unserem zweiten Papier haben wir Sprachmodelle (LMS) ihre eigenen Rätsel und verbessern zusammen mit dem Python-Dolmetscher ihre eigene Rätsellösung. Nach unserem Papier (Arxiv, 2022) gab es mehrere Papiere, in denen sich ein LM durch die Überprüfung seiner eigenen Lösungen verbessert. Unser Ansatz ist jedoch potenziell leistungsfähiger, da wir das LM haben, dass er seine eigenen Probleme und nicht nur seine eigenen Lösungen erzeugt.
Sprachmodelle können sich selbst beibringen, besser zu programmieren. Patrick Halumpzok, Matthew Bowers, Adam Tauman Kalai. In Proceedings der elften Internationalen Konferenz über Lernrepräsentationen (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}
}
Um die Ergebnisse in diesem Papier zu reproduzieren, siehe ICLR2023 -Ordner.
Wenn Sie nur ein paar Rätsel lösen möchten, probieren Sie das Intro -Notizbuch am Binder aus, das zeigt, welche Rätsel die KI -Basislinien gelöst haben und welche nicht, damit Sie sehen können, wie Ihre Programmierung vergleicht.
Jedes Puzzle hat die Form einer Python -Funktion, die als Argument eine Antwort nimmt. Die Antwort ist eine Eingabe, die die Funktion True . Dies nennt man das Puzzle, und deshalb werden die Rätsel alle sat genannt.
def sat ( s : str ):
return "Hello " + s == "Hello world" Die Antwort auf das obige Puzzle ist die Zeichenfolge "world" weil sat("world") True zurückkehrt. Die Rätsel reichen von trivialen Problemen wie diesem über klassische Rätsel bis hin zu Problemen mit dem Programmierwettbewerb bis hin zu offenen Problemen in Algorithmen und Mathematik.
Die klassischen Türme des Hanoi -Puzzles können wie folgt geschrieben werden:
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 ] == []Die kürzeste Antwort ist eine Liste von 255 Zügen. Stattdessen bitten wir die KI, Code zu generieren, der eine Antwort ausgibt. In diesem Fall hat die Codex -API den folgenden Code generiert:
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 movesDies war nicht in seinem ersten Versuch, aber das ist einer der Vorteile von Rätseln-es ist für den Computer einfach, seine Antworten zu überprüfen, damit er viele Antworten generieren kann, bis er einen findet. Für dieses Puzzle waren etwa 1 von 1.000 Lösungen zufriedenstellend. Es ist klar, dass Codex dieses Problem in anderen Eingabeformaten schon einmal gesehen hat-es hat sogar eine URL generiert! (Bei näherer Betrachtung existiert die Website und enthält den Python-Tower-of-Hanoi-Code in einem völlig anderen Format mit unterschiedlichen Variablennamen.) In einer härteren, weniger Standard-Hanoi-Puzzle-Variante, für die sich Codex von bestimmten Start-End-Positionen bewegen muss, hat Codex es nicht auf 10.000 Versuchen gelöst.
Betrachten Sie als nächstes ein Puzzle, das von diesem einfachen Programm für wettbewerbsfähige Programme von Codeforces.com inspiriert ist:
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 generierte den folgenden Code, der beim Ausführen die gültige Antwort [1, 3, 5, 7, 8, 9, 10, 15, 16] enthält. Dies erfüllt dieses Rätsel, da es sich um eine zunehmende Liste von Indizes handelt, die Sie in diesen Indizes "Sssuubbstrissiingg" in diesen Indizes "substring" anschließen.
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 )Auch hier gibt es mehrere gültige Antworten, und dies gab es auch nicht aus vielen Versuchen (nur 1 Erfolg in 10k).
Ein anspruchsvolleres Puzzle, das eine dynamische Programmierung erfordert, ist das am längsten zunehmende Subsequenzproblem, das wir auch mit Zeichenfolgen beschreiben können:
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 hat diesen nicht gelöst.
Der Datensatz hat auch eine Reihe offener Probleme in Informatik und Mathematik. Zum Beispiel,
Conways 99-Grad-Problem ist ein ungelöderes Problem in der Graphentheorie (siehe auch fünf Probleme von 1.000 USD (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 ))Warum Rätsel? Ein Grund dafür ist, dass wir bei einigen wichtigen Algorithmenproblemen Fortschritte machen können, wenn wir sie besser lösen können als menschliche Programmierer. Bis dahin ist jedoch ein zweiter Grund, dass sie für die Ausbildung und Bewertung von KI -Systemen wertvoll sein können. Im Laufe der Jahre wurden viele Programmierdatensätze vorgeschlagen, und einige haben Probleme mit ähnlicher Weise (wie Probleme mit dem Programmierwettbewerb). In Rätseln wird die Spezifikation durch Code definiert, während andere Datensätze normalerweise eine Kombination aus Englisch und einem versteckten Testsatz von Eingabe-Output-Paaren verwenden. Englischbasierte Spezifikationen sind notorisch mehrdeutig und testen das Verständnis des Systems für Englisch. Und bei Testfällen mit Eingabe-Output-Tests müssten Sie ein Puzzle gelöst, bevor Sie es posieren. Wie verwendet es also dort? Code-basierte Spezifikationen haben den Vorteil, dass sie eindeutig sind. Es besteht keine Notwendigkeit, den Code zu debuggen oder zu befürchten, dass er nicht das tut, was Sie wollen. Wenn es das Rätsel löste, gelang es per Definition.
Weitere Informationen zur Motivation und wie Programmierrätsel helfen kann, das Programm zu lernen, siehe Papier:
Programmierrätsel von Tal Schuster, Ashwin Kalyan, Alex Polozov und Adam Tauman Kalai. 2021 (Link, der in Kürze hinzugefügt werden soll)
Die Probleme in diesem Repo basieren auf:
Das Notebooks -Unterverzeichnis verfügt über einige relevante Notizbücher. Intro.ipynb hat ein Dutzend Rätsel, die angeben, welche die KI gelöst und das Notizbuch bei Binder nicht probiert hat, und sehen Sie, wie Ihre Programmierung mit den AI -Basislinien vergleichbar ist!
Demo.Ipynb hat die 30 Probleme, die unsere Benutzer in einer Benutzerstudie erledigt haben. Probieren Sie das Demo -Notizbuch aus und sehen Sie, wie Ihre Programmierung mit den KI -Basislinien vergleichbar ist!
Während eines Microsoft-Hackathons vom 27. bis 29. Juli 2020 haben mehrere Personen 30 User-Study-Rätsel abgeschlossen. Wir hatten auch unzählige Spaß, die Rätsel in Hackathon_puzzles.ipynb zu machen. Diese sind von einem etwas anderen Geschmack, da es häufiger hacks wie sind
def sat ( x ):
return x > x wo die Art des x eindeutig nicht standardmäßig ist. Zu den Schöpfer dieser Rätsel gehören Github -Benutzer: Adam Tauman Kalai, Alec Helbling, Alexander Vorobev, Alexander Wei, Alexey Romanov, Keith Battaochi, Kodai Sudo, Maggie Hei, Mariia Mykhailova, Misha Khodak, Monil Mahta, Philipsfield, Qida Mai, Qida Mai, Raj. Jaiswal, Saikiran Mullaguri, Tal Schuster und Varsha Srinivasan. Sie können das Notizbuch unter (zum hinzugefügten Link) ausprobieren.
Die Datei split.json enthält einen vorgeschlagenen Zug-Test-Split. Diese Spaltung wurde von den Puzzle-Autoren von Hand ausgewählt, die mit allen Rätseln vertraut sind, so dass: Es gibt minimale Überlappung zwischen verwandten Rätseln in den beiden Spaltungen. Insbesondere für Paare verwandter Rätsel wurden beide entweder in den Trainingssatz oder im Testsatz platziert.
Dieses Projekt begrüßt Beiträge und Vorschläge. Verwenden Sie Ihre Kreativität, um KIs zum Programmieren beizubringen! Sehen Sie unser Wiki, wie man ein Puzzle hinzufügt.
In den meisten Beiträgen müssen Sie einer Mitarbeiters Lizenzvereinbarung (CLA) zustimmen, in der Sie erklären, dass Sie das Recht haben und uns tatsächlich tun, um uns die Rechte zu gewähren, Ihren Beitrag zu verwenden. Weitere Informationen finden Sie unter https://cla.opensource.microsoft.com.
Wenn Sie eine Pull -Anfrage einreichen, bestimmt ein CLA -Bot automatisch, ob Sie eine CLA angeben und die PR angemessen dekorieren müssen (z. B. Statusprüfung, Kommentar). Befolgen Sie einfach die vom Bot bereitgestellten Anweisungen. Sie müssen dies nur einmal über alle Repos mit unserem CLA tun.
Dieses Projekt hat den Microsoft Open Source -Verhaltenscode übernommen. Weitere Informationen finden Sie im FAQ oder wenden Sie sich an [email protected] mit zusätzlichen Fragen oder Kommentaren.
Siehe das Datenblatt für unseren Datensatz.
Dieses Projekt kann Marken oder Logos für Projekte, Produkte oder Dienstleistungen enthalten. Die autorisierte Verwendung von Microsoft -Marken oder Logos unterliegt den Marken- und Markenrichtlinien von Microsoft und muss folgen. Die Verwendung von Microsoft -Marken oder Logos in geänderten Versionen dieses Projekts darf keine Verwirrung verursachen oder Microsoft -Sponsoring implizieren. Jede Verwendung von Marken oder Logos von Drittanbietern unterliegt den Richtlinien dieses Drittanbieters.
