PythonProgrammingPuzzles
1.0.0
이 repo에는 AI의 프로그래밍 능력을 가르치고 평가하는 데 사용할 수있는 Python 프로그래밍 퍼즐 데이터 세트가 포함되어 있습니다. OpenAi에 의해 생성 된 코드를 제시합니다
코덱스 신경망
이 퍼즐을 많이 해결합니다. 우리는이 데이터 세트가 빠르게 성장하기를 희망하며 문제를 해결하는 데 필요한 문제 난이도, 도메인 및 알고리즘 도구 측면에서 이미 다양합니다. 새로운 퍼즐을 제안하거나 새로 제안 된 퍼즐을 찾아 보거나 풀 요청을 통해 기여하십시오.
GPT-3과 같은 AI 시스템이 이러한 문제를 얼마나 잘 해결할 수 있는지에 대한 자세한 내용은 두 논문을 읽으십시오.
프로그래밍 퍼즐. Tal Schuster, Ashwin Kalyan, Oleksandr Polozov, Adam Tauman Kalai. 2021 년 신경 정보 처리 시스템 데이터 세트 및 벤치 마크 트랙 (Neurips)에 관한 35 번째 회의의 절차 에서.
@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. 2023 년 제 11 차 국제 학습 컨퍼런스 (ICLR)의 절차 .
@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 폴더를 참조하십시오.
몇 가지 퍼즐을 풀기 위해 바로 다이빙을 원한다면 바인더의 인트로 노트북을 사용하여 AI 기준선을 해결하고 그렇지 않은 퍼즐을 보여 주므로 프로그래밍이 어떻게 비교되는지 알 수 있습니다.
각 퍼즐은 인수로 답을 취하는 파이썬 함수의 형태를 취합니다. 대답은 함수가 True 를 반환하게하는 입력입니다. 이것을 퍼즐을 만족시키기 때문에 퍼즐의 이름이 모두 sat 라고합니다.
def sat ( s : str ):
return "Hello " + s == "Hello world" 위의 퍼즐에 대한 대답은 sat("world") True 반환하기 때문에 문자열 "world" 입니다. 퍼즐은 이와 같은 사소한 문제, 고전적인 퍼즐, 경쟁 문제, 알고리즘 및 수학의 열린 문제를 통해 모든 경쟁 문제에 이르기까지 다양합니다.
하노이 퍼즐의 클래식 타워는 다음과 같이 쓸 수 있습니다.
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,000 개의 솔루션 중 약 1 개가 만족 스러웠습니다. 분명히 Codex는 다른 입력 형식 에서이 문제를 보았습니다. 심지어 URL을 생성했습니다! (면밀히 검사를 받으면 웹 사이트가 존재하며 변수 이름을 가진 완전히 다른 형식의 파이썬 타워 코드가 포함되어 있습니다.) 특정 시작에서 끝 위치로 이동 해야하는 더 단단하고 표준이 낮은 하노이 퍼즐 변형에서 Codex는 10,000 개의 시도에서이를 해결하지 못했습니다.
다음으로 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 )다시 말하지만, 여러 가지 유효한 답변이 있으며, 다시 한 번 많은 시도에서 나왔습니다 (10k에서는 1 번의 성공 만).
역동적 인 프로그래밍이 필요한 더 어려운 퍼즐은 스트링으로 설명 할 수있는 가장 긴 후속 문제입니다.
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 ))코덱스는 이것을 해결하지 못했습니다.
데이터 세트에는 컴퓨터 과학 및 수학에서 여러 가지 열린 문제가 있습니다. 예를 들어,
Conway의 99 그래프 문제는 그래프 이론에서 해결되지 않은 문제입니다 (5 개의 $ 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 생성 코드를 디버깅 할 필요가 없습니다. 그것이 퍼즐을 해결했다면, 그것은 정의에 의해 성공했습니다.
동기 부여 및 프로그래밍 퍼즐이 AI를 프로그램하는 데 도움이되는 방법에 대한 자세한 내용은 다음을 참조하십시오.
Tal Schuster, Ashwin Kalyan, Alex Polozov 및 Adam Tauman Kalai의 프로그래밍 퍼즐 . 2021 (곧 추가 할 링크)
이 저장소의 문제는 다음을 기반으로합니다.
노트북 서브 디렉토리에는 몇 가지 관련 노트북이 있습니다. intro.ipynb는 AI가 어떤 것을 해결했는지를 나타내는 12 개의 퍼즐을 가지고 있으며 바인더에서 노트북을 시도하지 않고 프로그래밍이 AI 기준선과 어떻게 비교되는지 확인했습니다!
Demo.ipynb에는 사용자 연구에서 사용자가 완료 한 30 가지 문제가 있습니다. 데모 노트북을 시도하고 프로그래밍이 AI 기준선과 어떻게 비교되는지 확인하십시오!
2020 년 7 월 27 일부터 29 일까지 Microsoft Hackathon 동안 몇몇 사람들이 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, Monil Mehta, Philip Rosenfield, Qida Ma, Raj Bhargava, Rishisnifile, Qida Ma. Saikiran Mullaguri, Tal Schuster 및 Varsha Srinivasan. (추가 할 링크)에서 노트북을 시험해 볼 수 있습니다.
split.json 파일에는 제안 된 열차 테스트 분할이 포함되어 있습니다. 이 분할은 모든 퍼즐에 익숙한 퍼즐 저자들에 의해 손으로 선택되었으므로 두 분할의 관련 퍼즐 사이에 최소한의 중첩이 있습니다. 특히, 관련 퍼즐 쌍의 경우 둘 다 훈련 세트 또는 테스트 세트에 배치되었습니다.
이 프로젝트는 기여와 제안을 환영합니다. 창의성을 사용하여 AI의 프로그램을 가르치는 데 도움이됩니다! 퍼즐을 추가하는 방법에 대한 Wiki를 참조하십시오.
대부분의 기부금은 귀하가 귀하가 귀하의 기부금을 사용할 권리를 부여 할 권리가 있다고 선언하는 기고자 라이센스 계약 (CLA)에 동의해야합니다. 자세한 내용은 https://cla.opensource.microsoft.com을 방문하십시오.
풀 요청을 제출할 때 CLA 봇은 CLA를 제공하고 PR을 적절하게 장식 해야하는지 자동으로 결정합니다 (예 : 상태 점검, 댓글). 봇이 제공 한 지침을 따르십시오. CLA를 사용하여 모든 저장소에서 한 번만이 작업을 수행하면됩니다.
이 프로젝트는 Microsoft 오픈 소스 행동 강령을 채택했습니다. 자세한 내용은 추가 질문이나 의견이 있으면 행동 강령 FAQ 또는 [email protected]에 문의하십시오.
데이터 세트의 데이터 시트를 참조하십시오.
이 프로젝트에는 프로젝트, 제품 또는 서비스에 대한 상표 또는 로고가 포함될 수 있습니다. Microsoft 상표 또는 로고의 승인 된 사용에는 Microsoft의 상표 및 브랜드 지침이 적용되며 따라야합니다. 이 프로젝트의 수정 된 버전에서 Microsoft 상표 또는 로고를 사용한다고해서 혼란을 일으키거나 Microsoft 후원을 암시해서는 안됩니다. 타사 상표 또는 로고를 사용하면 타사 정책이 적용됩니다.
