PythonProgrammingPuzzles
1.0.0
Ce dépôt contient un ensemble de données de puzzles de programmation Python qui peuvent être utilisés pour enseigner et évaluer la maîtrise de la programmation d'une IA. Nous présentons le code généré par Openai
Réseau neuronal du codex
résoudre bon nombre de ces puzzles. Nous espérons que cet ensemble de données se développera rapidement , et il est déjà diversifié en termes de difficulté problématique, de domaine et d'outils algorithmiques nécessaires pour résoudre les problèmes. Veuillez proposer un nouveau puzzle ou parcourir des puzzles récemment proposés ou contribuer à travers des demandes de traction.
Pour en savoir plus sur la façon dont les systèmes d'IA tels que le GPT-3 peuvent résoudre ces problèmes, lisez nos deux articles:
Programmation des puzzles. Tal Schuster, Ashwin Kalyan, Oleksandr Polozov, Adam Tauman Kalai. Dans les actes de la trente-cinquième conférence sur les ensembles de données de données et de références de traitement de l'information neuronale (INIPS), 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}
}
Pour reproduire les résultats de cet article, consultez le dossier Solvers.
Nouveau auto-enseignement: Dans notre deuxième article, nous avons des modèles de langage (LMS) génèrent leurs propres puzzles et, avec l'interprète Python, améliorent leur propre capacité de résolution de puzzle. Suivant notre article (Arxiv, 2022), il y a eu plusieurs articles où un LM s'améliore en vérifiant ses propres solutions. Cependant, notre approche est potentiellement plus puissante car nous avons le LM générer ses propres problèmes, pas seulement ses propres solutions.
Les modèles linguistiques peuvent s'apprendre à mieux programmer. Patrick Haluptzok, Matthew Bowers, Adam Tauman Kalai. Dans Actes de la onzième Conférence internationale sur les représentations d'apprentissage (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}
}
Pour reproduire les résultats de cet article, consultez le dossier ICLR2023.
Si vous voulez simplement plonger directement dans la résolution de quelques puzzles, essayez le cahier d'introduction à Binder qui montre qui puzzle les lignes de base AI résolues et ce qu'elles ne l'ont pas fait, afin que vous puissiez voir comment votre programmation se compare.
Chaque puzzle prend la forme d'une fonction Python qui prend une réponse comme argument. La réponse est une entrée qui rend la fonction Retour True . C'est ce qu'on appelle satisfaire le puzzle, et c'est pourquoi les puzzles sont tous nommés sat .
def sat ( s : str ):
return "Hello " + s == "Hello world" La réponse au puzzle ci-dessus est la chaîne "world" parce que sat("world") revient True . Les puzzles vont de problèmes triviaux comme celui-ci, aux puzzles classiques, aux problèmes de compétition de programmation, tout au long des problèmes ouverts dans les algorithmes et les mathématiques.
Les tours classiques de Hanoi Puzzle peuvent être écrites comme suit:
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 ] == []La réponse la plus courte est une liste de 255 mouvements, nous demandons donc à la place de l'IA de générer du code qui publie une réponse. Dans ce cas, l'API Codex a généré le code suivant:
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 movesCe n'était pas lors de son premier essai, mais c'est l'un des avantages des puzzles - il est facile pour l'ordinateur de vérifier ses réponses afin qu'il puisse générer de nombreuses réponses jusqu'à ce qu'elle en trouve une. Pour ce puzzle, environ 1 solutions sur 1 000 était satisfaisante. De toute évidence, le codex a déjà vu ce problème dans d'autres formats d'entrée - il a même généré une URL! (Après une inspection plus approfondie, le site Web existe et contient du code de tour de hanoi Python dans un format complètement différent avec différents noms de variables.) Sur une variante de puzzle Hanoi plus difficile et moins standard qui nécessite de passer des positions de début pour fins particulières, Codex ne l'a pas résolu sur 10 000 tentatives.
Ensuite, considérez un puzzle inspiré de ce problème de programmation compétitif facile sur le site Web de 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" Le codex a généré le code ci-dessous, qui lors de l'exécution donne la réponse valide [1, 3, 5, 7, 8, 9, 10, 15, 16] . Cela satisfait ce puzzle parce que c'est une liste croissante d'indices que si vous rejoignez les personnages "Sssuubbstrissiingg" dans ces indices, vous obtenez "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 )Encore une fois, il y a plusieurs réponses valides, et encore une fois, il s'agissait de nombreuses tentatives (seulement 1 succès en 10k).
Un puzzle plus difficile qui nécessite une programmation dynamique est le problème de sous-séquence le plus long que nous pouvons également décrire avec des chaînes:
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 ))Le codex n'a pas résolu celui-ci.
L'ensemble de données a également un certain nombre de problèmes ouverts en informatique et en mathématiques. Par exemple,
Le problème de 99 graphes de Conway est un problème non résolu dans la théorie des graphiques (voir également cinq problèmes de 1 000 $ (mise à jour 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 ))Pourquoi des puzzles? L'une des raisons est que, si nous pouvons les résoudre mieux que les programmeurs humains, nous pourrions progresser sur certains problèmes d'algorithmes importants. Mais jusque-là, une deuxième raison est qu'ils peuvent être précieux pour la formation et l'évaluation des systèmes d'IA. De nombreux ensembles de données de programmation ont été proposés au fil des ans, et plusieurs ont des problèmes de nature similaire (comme des problèmes de compétition de programmation). Dans les puzzles, la spécification est définie par le code, tandis que d'autres ensembles de données utilisent généralement une combinaison d'anglais et un ensemble de tests caché de paires d'entrée-sortie. Les spécifications basées sur l'anglais sont notoirement ambiguës et testent la compréhension du système de l'anglais. Et avec les cas de test d'entrée-sortie, vous auriez dû résoudre un puzzle avant de le poser, alors quelle est l'utilisation là-bas? Les spécifications basées sur le code ont l'avantage qu'elles sont sans ambiguïté, il n'est pas nécessaire de déboguer le code généré par l'AI ou de craindre qu'il ne fasse pas ce que vous voulez. S'il résolvait le puzzle, il a réussi par définition.
Pour plus d'informations sur la motivation et comment la programmation des puzzles peut aider l'IA à apprendre à programmer, voir l'article:
Programmation Puzzles , de Tal Schuster, Ashwin Kalyan, Alex Polozov et Adam Tauman Kalai. 2021 (lien à ajouter sous peu)
Les problèmes de ce dépôt sont basés sur:
Le sous-répertoire des cahiers a quelques cahiers pertinents. Intro.ipynb a une douzaine de puzzles indiquant lesquels l'AI a résolu et n'ont pas essayé le cahier de Binder et voir comment votre programmation se compare aux lignes de base AI!
Demo.ipynb a les 30 problèmes rencontrés par nos utilisateurs dans une étude utilisateur. Essayez le cahier de démonstration et voyez comment votre programmation se compare aux lignes de base AI!
Au cours d'un hackathon Microsoft du 27 au 29 juillet 2020, plusieurs personnes ont terminé 30 puzzles d'étude des utilisateurs. Nous avons également eu des tonnes de plaisir à faire les puzzles dans hackathon_puzzles.ipynb. Ce sont d'une saveur quelque peu différente car ils sont plus souvent hacks comme
def sat ( x ):
return x > x où le type de x est clairement non standard. Les créateurs de ces puzzles incluent les utilisateurs de Github: Adam Tauman Kalai, Alec Helbling, Alexander Vorobev, Alexander Wei, Alexey Romanov, Keith Battaochi, Kodai Sudo, Maggie Hei, Mariia Mykhailova, Misha Khodak, Monil Mehta, Philipp Saikiran Mullaguri, Tal Schuster et Varsha Srinivasan. Vous pouvez essayer le cahier (lien à ajouter).
Le fichier split.json contient une division de test de train suggérée. Cette scission a été sélectionnée à la main par les auteurs du puzzle, qui connaissent tous les puzzles, de sorte que: il y a un chevauchement minimal entre les puzzles connexes dans les deux divisions. En particulier, pour les paires de puzzles connexes, les deux ont été placés dans l'ensemble de formation ou le jeu de test.
Ce projet accueille les contributions et les suggestions. Utilisez votre créativité pour vous aider à enseigner l'IA à programmer! Voir notre wiki sur la façon d'ajouter un puzzle.
La plupart des contributions vous obligent à accepter un accord de licence de contributeur (CLA) déclarant que vous avez le droit de faire et en fait, accordez-nous les droits d'utilisation de votre contribution. Pour plus de détails, visitez https://cla.opensource.microsoft.com.
Lorsque vous soumettez une demande de traction, un bot CLA déterminera automatiquement si vous devez fournir un CLA et décorer le RP de manière appropriée (par exemple, vérification d'état, commentaire). Suivez simplement les instructions fournies par le bot. Vous n'aurez besoin de le faire qu'une seule fois sur tous les dépositions en utilisant notre CLA.
Ce projet a adopté le code de conduite open source Microsoft. Pour plus d'informations, consultez le code de conduite FAQ ou contactez [email protected] avec toute question ou commentaire supplémentaire.
Voir la fiche technique de notre ensemble de données.
Ce projet peut contenir des marques ou des logos pour des projets, des produits ou des services. L'utilisation autorisée de marques ou de logos Microsoft est soumise et doit suivre les directives de marque et de marque de Microsoft. L'utilisation de marques ou de logos de Microsoft dans des versions modifiées de ce projet ne doit pas provoquer de confusion ou impliquer le parrainage de Microsoft. Toute utilisation de marques ou de logos tiers est soumis aux politiques de ces tiers.
