PythonProgrammingPuzzles
1.0.0
Este repositorio contiene un conjunto de datos de acertijos de programación de Python que se pueden utilizar para enseñar y evaluar la competencia de programación de una IA. Presentamos el código generado por Operai's
red neuronal del códice
Resolviendo muchos de estos rompecabezas. Esperamos que este conjunto de datos crezca rápidamente , y ya es diverso en términos de dificultad para problemas, dominio y herramientas algorítmicas necesarias para resolver los problemas. Proponga un nuevo rompecabezas o explore rompecabezas recién propuestos o contribuya a través de solicitudes de extracción.
Para obtener más información sobre qué tan bien los sistemas AI como GPT-3 pueden resolver estos problemas, lea nuestros dos documentos:
Rompecabezas de programación. Tal Schuster, Ashwin Kalyan, Oleksandr Polozov, Adam Tauman Kalai. En los procedimientos de la trigésima quinta conferencia sobre conjuntos de datos de sistemas de procesamiento de información neural y seguimiento de los puntos de referencia (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}
}
Para reproducir los resultados en ese documento, vea la carpeta Solvers.
Nuevo autolodido: en nuestro segundo artículo, tenemos modelos de idiomas (LMS) generando sus propios rompecabezas y, junto con el intérprete de Python, mejoran su propia capacidad de resolución de rompecabezas. Después de nuestro artículo (ARXIV, 2022), ha habido varios documentos en los que un LM se mejora al verificar sus propias soluciones. Sin embargo, nuestro enfoque es potencialmente más poderoso porque tenemos el LM generar sus propios problemas, no solo sus propias soluciones.
Los modelos de idiomas pueden enseñarse a programarse mejor. Patrick Haluptzok, Matthew Bowers, Adam Tauman Kalai. En Actas de la Undécima Conferencia Internacional sobre Representaciones de Aprendizaje (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}
}
Para reproducir los resultados en ese documento, consulte la carpeta ICLR2023.
Si solo desea sumergirse directamente para resolver algunos rompecabezas, pruebe el cuaderno de introducción en Binder que muestra qué rompecolinos se resuelven las líneas de base de IA y cuáles no, para que pueda ver cómo se compara su programación.
Cada rompecabezas toma la forma de una función de pitón que toma una respuesta como argumento. La respuesta es una entrada que hace que la función vuelva True . Esto se llama satisfacer el rompecabezas, y es por eso que los rompecabezas se llaman sat .
def sat ( s : str ):
return "Hello " + s == "Hello world" La respuesta al rompecabezas anterior es la cadena "world" porque sat("world") devuelve True . Los rompecabezas van desde problemas triviales como este, hasta rompecabezas clásicos, hasta problemas de competencia de programación, hasta los problemas abiertos en algoritmos y matemáticas.
Las torres clásicas de Hanoi Puzzle se pueden escribir de la siguiente manera:
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 respuesta más corta es una lista de 255 movimientos, por lo que, en cambio, pedimos que la IA genere un código que genere una respuesta. En este caso, la API de Codex generó el siguiente código:
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 movesEsto no fue en su primer intento, pero esa es una de las ventajas de los rompecabezas: es fácil para la computadora verificar sus respuestas para que pueda generar muchas respuestas hasta que encuentre una. Para este rompecabezas, aproximadamente 1 de cada 1,000 soluciones fueron satisfactorias. Claramente, Codex ha visto este problema antes en otros formatos de entrada, ¡incluso generó una URL! (Tras una inspección más cercana, el sitio web existe y contiene un código de la Torre de Hanoi de Python en un formato completamente diferente con diferentes nombres variables). En una variante de rompecabezas Hanoi más difícil y menos estándar que requiere moverse de posiciones de inicio a final particulares, Codex no lo resolvió en 10,000 intentos.
A continuación, considere un rompecabezas inspirado en este fácil problema de programación competitiva en el sitio 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" Codex generó el código a continuación, que cuando se ejecuta da la respuesta válida [1, 3, 5, 7, 8, 9, 10, 15, 16] . Esto satisface este rompecabezas porque es una lista cada vez mayor de índices que si te unes a los personajes "Sssuubbstrissiingg" en estos índices obtienes "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 )Nuevamente, hay múltiples respuestas válidas, y nuevamente esto fue fuera de muchos intentos (solo 1 éxito en 10k).
Un rompecabezas más desafiante que requiere una programación dinámica es el problema posterior más largo que también podemos describir con cadenas:
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 no resolvió este.
El conjunto de datos también tiene una serie de problemas abiertos en informática y matemáticas. Por ejemplo,
El problema de 99 grifos de Conway es un problema sin resolver en la teoría de gráficos (ver también cinco problemas de $ 1,000 (actualización 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 ))¿Por qué rompecabezas? Una razón es que, si podemos resolverlos mejor que los programadores humanos, entonces podríamos avanzar en algunos problemas importantes de algoritmos. Pero hasta entonces, una segunda razón es que pueden ser valiosos para capacitar y evaluar los sistemas de IA. Se han propuesto muchos conjuntos de datos de programación a lo largo de los años, y varios tienen problemas de naturaleza similar (como problemas de competencia de programación). En los rompecabezas, la especificación se define por código, mientras que otros conjuntos de datos generalmente usan una combinación de inglés y un conjunto de pruebas ocultas de pares de entrada-salida. Las especificaciones basadas en inglés son notoriamente ambiguas y prueban la comprensión del inglés del sistema. Y con los casos de prueba de entrada-salida, tendría que haber resuelto un rompecabezas antes de posarlo, entonces, ¿de qué sirve? Las especificaciones basadas en el código tienen la ventaja de que son inequívocas, no hay necesidad de depurar el código generado por la IA o temer que no haga lo que desea. Si resolvió el rompecabezas, entonces tuvo éxito por definición.
Para obtener más información sobre la motivación y cómo los rompecabezas de programación pueden ayudar a la IA a aprender a programar, consulte el documento:
Rompecabezas de programación , de Tal Schuster, Ashwin Kalyan, Alex Polozov y Adam Tauman Kalai. 2021 (enlace a agregar en breve)
Los problemas en este repositorio se basan en:
El subdirectorio de cuadernos tiene algunos cuadernos relevantes. Intro.ipynb tiene una docena de rompecabezas que indican cuáles resolvieron la IA y no probó el cuaderno en Binder y vea cómo se compara su programación con las líneas de base de IA.
Demo.ipynb tiene los 30 problemas completados por nuestros usuarios en un estudio de usuario. ¡Pruebe el cuaderno de demostración y vea cómo se compara su programación con las líneas de base de IA!
Durante un Hackathon de Microsoft del 27 al 29 de julio de 2020, varias personas completaron 30 rompecabezas de estudio de usuarios. También nos divertimos mucho haciendo los rompecabezas en Hackathon_Puzzles.ipynb. Estos son de un sabor algo diferente, ya que a menudo son hacks como
def sat ( x ):
return x > x donde el tipo de x es claramente no estándar. The creators of these puzzles include github users: Adam Tauman Kalai, Alec Helbling, Alexander Vorobev, Alexander Wei, Alexey Romanov, Keith Battaochi, Kodai Sudo, Maggie Hei, Mariia Mykhailova, Misha Khodak, Monil Mehta, Philip Rosenfield, Qida Ma, Raj Bhargava, Rishi Jaiswal, Saikiran Mullaguri, Tal Schuster y Varsha Srinivasan. Puede probar el cuaderno en (enlace a agregar).
El archivo split.json contiene una división de prueba de tren sugerida. Esta división fue seleccionada a mano por los autores de rompecabezas, que están familiarizados con todos los rompecabezas, de modo que: hay una superposición mínima entre los rompecabezas relacionados en las dos divisiones. En particular, para pares de rompecabezas relacionados, ambos se colocaron en el conjunto de entrenamiento o en el conjunto de pruebas.
Este proyecto da la bienvenida a las contribuciones y sugerencias. ¡Usa tu creatividad para ayudar a enseñar a AI a programar! Vea nuestro wiki sobre cómo agregar un rompecabezas.
La mayoría de las contribuciones requieren que acepte un Acuerdo de Licencia de Contributor (CLA) que declare que tiene derecho y realmente hacernos los derechos para utilizar su contribución. Para más detalles, visite https://cla.opensource.microsoft.com.
Cuando envíe una solicitud de extracción, un BOT CLA determinará automáticamente si necesita proporcionar un CLA y decorar el PR adecuadamente (por ejemplo, verificación de estado, comentario). Simplemente siga las instrucciones proporcionadas por el bot. Solo necesitará hacer esto una vez en todos los reposos usando nuestro CLA.
Este proyecto ha adoptado el Código de Conducta Open Open Microsoft. Para obtener más información, consulte el Código de Conducta Preguntas frecuentes o comuníquese con [email protected] con cualquier pregunta o comentario adicional.
Vea la hoja de datos para nuestro conjunto de datos.
Este proyecto puede contener marcas comerciales o logotipos para proyectos, productos o servicios. El uso autorizado de marcas o logotipos de Microsoft está sujeto y debe seguir las pautas de marca y marca de Microsoft. El uso de marcas registradas de Microsoft o logotipos en versiones modificadas de este proyecto no debe causar confusión o implicar el patrocinio de Microsoft. Cualquier uso de marcas comerciales o logotipos de terceros está sujeto a las políticas de esas partes de terceros.
