PythonProgrammingPuzzles
1.0.0
Este repositório contém um conjunto de dados de quebra -cabeças de programação Python, que podem ser usados para ensinar e avaliar a proficiência de programação de uma IA. Apresentamos o código gerado pelo OpenAI's
Rede Neural Codex
resolvendo muitos desses quebra -cabeças. Esperamos que esse conjunto de dados cresça rapidamente e já seja diverso em termos de dificuldade de dificuldade, domínio e ferramentas algorítmicas necessárias para resolver os problemas. Por favor, proponha um novo quebra -cabeça ou navegue com quebra -cabeças recentemente propostos ou contribua através de solicitações de tração.
Para saber mais sobre o quão bem os sistemas de IA como o GPT-3 podem resolver esses problemas, leia nossos dois artigos:
Quebra -cabeças de programação. Tal Schuster, Ashwin Kalyan, Oleksandr Polozov, Adam Tauman Kalai. Em Anais da Trigésima Quinta Conferência sobre Conjuntos de Conjuntos de Dados de Sistemas de Processamento de Informações Neurais e Rastrear (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 reproduzir os resultados nesse artigo, consulte a pasta Solvers.
Novo auto-ensino: em nosso segundo artigo, temos modelos de idiomas (LMS) geram seus próprios quebra-cabeças e, juntamente com o intérprete Python, melhoram sua própria capacidade de resolução de quebra-cabeça. Seguindo nosso artigo (Arxiv, 2022), houve vários artigos onde um LM se melhora, verificando suas próprias soluções. No entanto, nossa abordagem é potencialmente mais poderosa porque temos o LM gera seus próprios problemas, não apenas suas próprias soluções.
Os modelos de idiomas podem se ensinar a programar melhor. Patrick Haluptzok, Matthew Bowers, Adam Tauman Kalai. Em Anais da Décima Primeira Conferência Internacional sobre Representações de Aprendizagem (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 reproduzir os resultados nesse artigo, consulte a pasta ICLR2023.
Se você deseja apenas mergulhar para resolver alguns quebra -cabeças, tente o caderno de introdução no Binder que mostra quais intrigos as linhas de base da IA resolvidas e que elas não fizeram, para que você possa ver como sua programação se compara.
Cada quebra -cabeça assume a forma de uma função python que toma uma resposta como argumento. A resposta é uma entrada que torna a função retornar True . Isso é chamado de satisfazer o quebra -cabeça, e é por isso que os quebra -cabeças são todos nomeados sat .
def sat ( s : str ):
return "Hello " + s == "Hello world" A resposta para o quebra -cabeça acima é a string "world" porque sat("world") retorna True . Os quebra -cabeças variam de problemas triviais como esse, a quebra -cabeças clássicos, a problemas de concorrência de programação, desde problemas abertos em algoritmos e matemática.
As torres clássicas do quebra -cabeça de Hanói podem ser escritas da seguinte forma:
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 ] == []A resposta mais curta é uma lista de 255 movimentos; portanto, solicitamos que a IA gere código que gera uma resposta. Nesse caso, a API Codex gerou o seguinte 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 movesIsso não foi em sua primeira tentativa, mas essa é uma das vantagens dos quebra-cabeças-é fácil para o computador verificar suas respostas para que possa gerar muitas respostas até encontrar uma. Para esse quebra -cabeça, cerca de 1 em 1.000 soluções foram satisfatórias. Claramente, o Codex já viu esse problema antes em outros formatos de entrada-até gerou um URL! (Após uma inspeção mais detalhada, o site existe e contém o código da torre de hanoi do Python em um formato completamente diferente, com nomes de variáveis diferentes.) Em uma variante de quebra-cabeça mais difícil e menos padrão do Hanoi, que exige que a mudança de posições de início a final específicas, o Codex não o resolvesse em 10.000 tentativas.
Em seguida, considere um quebra -cabeça inspirado nesse problema de programação competitivo fácil do site 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" O Codex gerou o código abaixo, que, quando executado, fornece a resposta válida [1, 3, 5, 7, 8, 9, 10, 15, 16] . Isso satisfaz esse quebra -cabeça, porque é uma lista crescente de índices que se você ingressar nos caracteres "Sssuubbstrissiingg" nesses índices que você obtém "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 )Novamente, existem várias respostas válidas e, novamente, isso foi de muitas tentativas (apenas 1 sucesso em 10k).
Um quebra -cabeça mais desafiador que requer programação dinâmica é o problema subseqüente mais crescente que também podemos descrever com strings:
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 não resolveu este.
O conjunto de dados também tem vários problemas abertos na ciência da computação e na matemática. Por exemplo,
O problema de 99 grafias de Conway é um problema não resolvido na teoria dos gráficos (ver também cinco problemas de US $ 1.000 (atualização 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 que quebra -cabeças? Uma razão é que, se pudermos resolvê -los melhor do que os programadores humanos, poderíamos progredir em alguns problemas importantes de algoritmos. Mas até então, uma segunda razão é que eles podem ser valiosos para treinar e avaliar os sistemas de IA. Muitos conjuntos de dados de programação foram propostos ao longo dos anos e vários têm problemas de natureza semelhante (como problemas de concorrência de programação). Nos quebra-cabeças, a especificação é definida pelo código, enquanto outros conjuntos de dados geralmente usam uma combinação de inglês e um conjunto de testes ocultos de pares de entrada e saída. As especificações em inglês são notoriamente ambíguas e testam a compreensão do sistema do inglês. E com os casos de teste de entrada e saída, você teria que resolver um quebra-cabeça antes de colocá-lo, então qual é o uso lá? As especificações baseadas em código têm a vantagem de que não são ambíguas, não há necessidade de depurar o código gerado pela IA ou os temores de que ele não faça o que você deseja. Se resolveu o quebra -cabeça, foi bem -sucedido por definição.
Para obter mais informações sobre a motivação e como os quebra -cabeças de programação podem ajudar a IA a aprender a programar, consulte o artigo:
Programação quebra -cabeças , de Tal Schuster, Ashwin Kalyan, Alex Polozov e Adam Tauman Kalai. 2021 (link a ser adicionado em breve)
Os problemas neste repositório são baseados em:
O subdiretório de notebooks possui alguns notebooks relevantes. O Intro.ipynb tem uma dúzia de quebra -cabeças indicando quais a IA resolveu e não experimentou o caderno no Binder e ver como sua programação se compara às linhas de base da IA!
Demo.ipynb tem os 30 problemas concluídos por nossos usuários em um estudo de usuário. Experimente o caderno de demonstração e veja como sua programação se compara às linhas de base da IA!
Durante um Microsoft Hackathon de 27 a 29 de julho de 2020, várias pessoas completaram 30 quebra-cabeças de estudo de usuário. Também nos divertimos muito fazendo os quebra -cabeças em hackathon_puzzles.ipynb. Estes são de um sabor um pouco diferente, pois são mais frequentemente hacks como
def sat ( x ):
return x > x onde o tipo de x é claramente fora do padrão. 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 e Varsha Srinivasan. Você pode experimentar o notebook em (link a ser adicionado).
O arquivo split.json contém uma divisão sugerida no teste de trem. Essa divisão foi selecionada à mão pelos autores do quebra-cabeça, familiarizados com todos os quebra-cabeças, de modo que: existe uma sobreposição mínima entre quebra-cabeças relacionados nas duas divisões. Em particular, para pares de quebra -cabeças relacionados, ambos foram colocados no conjunto de treinamento ou no conjunto de testes.
Este projeto recebe contribuições e sugestões. Use sua criatividade para ajudar a ensinar as IA para programar! Veja nosso wiki sobre como adicionar um quebra -cabeça.
A maioria das contribuições exige que você concorde com um Contrato de Licença de Colaborador (CLA) declarando que você tem o direito e, na verdade, concede -nos os direitos de usar sua contribuição. Para detalhes, visite https://cla.opensource.microsoft.com.
Quando você envia uma solicitação de tração, um BOT do CLA determina automaticamente se você precisa fornecer um CLA e decorar o PR adequadamente (por exemplo, verificação de status, comentar). Simplesmente siga as instruções fornecidas pelo bot. Você só precisará fazer isso uma vez em todos os repositórios usando nosso CLA.
Este projeto adotou o Código de Conduta Open Microsoft. Para obter mais informações, consulte o Código de Conduta Perguntas frequentes ou entre em contato com [email protected] com quaisquer perguntas ou comentários adicionais.
Consulte a folha de dados do nosso conjunto de dados.
Este projeto pode conter marcas comerciais ou logotipos para projetos, produtos ou serviços. O uso autorizado de marcas comerciais ou logotipos da Microsoft está sujeito e deve seguir as diretrizes de marca registrada e marca da Microsoft. O uso de marcas comerciais da Microsoft ou logotipos em versões modificadas deste projeto não deve causar confusão ou implicar o patrocínio da Microsoft. Qualquer uso de marcas comerciais ou logotipos de terceiros estão sujeitas às políticas de terceiros.
