PythonProgrammingPuzzles
1.0.0
Этот репо содержит набор данных программирования Python, который можно использовать для обучения и оценки мастерства программирования ИИ. Мы представляем код, сгенерированный Openai
Кодекс Нейронная сеть
Решение многих из этих головоломок. Мы надеемся, что этот набор данных будет быстро расти , и он уже разнообразен с точки зрения сложности проблемы, домена и алгоритмических инструментов, необходимых для решения проблем. Пожалуйста, предложите новую загадку или просмотрите вновь предложенные головоломки или внесите вклад в результаты запросов на притяжение.
Чтобы узнать больше о том, насколько хорошо системы ИИ, такие как GPT-3, могут решить эти проблемы, прочитайте две наши статьи:
Программирование головоломок. Тал Шустер, Эшвин Калян, Олександр Полозов, Адам Тауман Калай. В материалах Тридцати пятой конференции по наборам данных и контрольно-пропускной основе нейронной обработки и критериями (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}
}
Чтобы воспроизвести результаты в этой статье, см. Папку решателей.
Новое самообладание: во второй статье у нас есть языковые модели (LMS) , генерирующие свои собственные головоломки , и, вместе с интерпретатором Python, улучшают свои собственные возможности для решения головоломки. После нашей статьи (Arxiv, 2022) было несколько документов, где LM улучшается, проверяя свои собственные решения. Тем не менее, наш подход потенциально более мощный, потому что у нас LM генерирует свои собственные проблемы, а не только свои собственные решения.
Языковые модели могут научить себя лучше программировать. Патрик Халупццок, Мэтью Бауэрс, Адам Тауман Калай. В материалах Одиннадцатой Международной конференции по обучению представлений (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}
}
Чтобы воспроизвести результаты в этой статье, см. Папку ICLR2023.
Если вы просто хотите погрузиться в решение нескольких головоломок, попробуйте вступительный ноутбук в Binder, который показывает, какие головоломки решались базовые показатели ИИ, а что нет, чтобы вы могли видеть, как сравнивается ваше программирование.
Каждая головоломка принимает форму функции Python, которая принимает ответ в качестве аргумента. Ответ - это вход, который заставляет функцию возвращать True . Это называется удовлетворительной головоломкой, и именно поэтому все головоломки называются sat .
def sat ( s : str ):
return "Hello " + s == "Hello world" Ответ на вышеупомянутую головоломку - это струна "world" потому что sat("world") возвращается True . Головоломки варьируются от тривиальных проблем, подобных этой, до классических головоломок, до программирования проблем соревнований, вплоть до открытых проблем в алгоритмах и математике.
Классические башни головоломки Ханоя можно написать следующим образом:
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 движений, поэтому вместо этого мы просим, чтобы ИИ сгенерировал код , который выводит ответ. В этом случае API Codex сгенерировал следующий код:
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 из 1000 решений были удовлетворительными. Очевидно, что Кодекс видел эту проблему ранее в других форматах ввода-он даже сгенерировал URL! (При более внимательном рассмотрении веб-сайт существует и содержит код Python Tower-of-Hanoi в совершенно другом формате с различными именами переменных.) На более жестком, менее стандартном варианте головоломки Hanoi, который требует перемещения от определенных начальных позиций, 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" Кодекс сгенерировал приведенный ниже код, который при запуске дает действительный ответ [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 )Опять же, есть несколько действительных ответов, и опять же, это было из многих попыток (только 1 успех в 10K).
Более сложная головоломка, которая требует динамического программирования, - это самая продолжительная проблема последующей последовательности, которую мы также можем описать с помощью строк:
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 ))Кодекс не решил это.
Набор данных также имеет ряд открытых проблем в области компьютерных наук и математики. Например,
Проблема 99-графического графа Конвея является нерешенной проблемой в теории графиков (см. Также пять проблем в 1000 долларов (обновление 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-код или опасения, что он не делает то, что вы хотите. Если это решило головоломку, то она преуспела по определению.
Для получения дополнительной информации о мотивации и о том, как головоломки программирования могут помочь ИИ научиться программировать, см. Документ:
Программирование головоломок , Тал Шустер, Эшвин Калян, Алекс Полозов и Адам Тауман Калай. 2021 (ссылка на добавление в ближайшее время)
Проблемы в этом репо основаны на:
В подкаталорике ноутбуков есть несколько соответствующих записей. Intro.ipynb имеет дюжину головоломок, указывающих, какие из них решал ИИ, и не пробовал ноутбук в Binder и посмотрите, как ваше программирование сравнивается с базовыми показателями ИИ!
Demo.ipynb имеет 30 проблем, выполненных нашими пользователями в исследовании пользователя. Попробуйте демо -ноутбук и посмотрите, как ваше программирование сравнивается с базовыми показателями ИИ!
Во время Microsoft Hackathon 27-29 июля 2020 года несколько человек завершили 30 головоломок. У нас также было множество веселья, делая головоломки в Hackathon_puzzles.ipynb. Это несколько иного вкуса, так как они чаще всего hacks
def sat ( x ):
return x > x где тип x явно нестандартный. 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 Маллагури, Тал Шустер и Варша Шринивасан. Вы можете попробовать ноутбук по адресу (ссылка для добавления).
Файл split.json содержит предлагаемое разделение тестирования поезда. Этот раскол был отобран вручную авторами головоломки, которые знакомы со всеми головоломками, так что: существует минимальное перекрытие между родственными головоломками в двух расщеплениях. В частности, для пар связанных головоломок либо были размещены в учебном наборе, либо в тестовом наборе.
Этот проект приветствует вклады и предложения. Используйте свое творчество, чтобы помочь научить ИИ программировать! Посмотрите на нашу вики о том, как добавить головоломку.
Большинство взносов требуют, чтобы вы согласились с лицензионным соглашением о участнике (CLA), заявив, что вы имеете право и фактически предоставить нам права на использование вашего вклада. Для получения подробной информации посетите https://cla.opensource.microsoft.com.
Когда вы отправляете запрос на привлечение, бот CLA автоматически определит, нужно ли вам предоставить CLA и правильно украсить PR (например, проверка состояния, комментарий). Просто следуйте инструкциям, предоставленным ботом. Вам нужно будет сделать это только один раз во всех репо, используя наш CLA.
Этот проект принял код поведения с открытым исходным кодом Microsoft. Для получения дополнительной информации см. Кодекс поведения FAQ или свяжитесь с [email protected] с любыми дополнительными вопросами или комментариями.
Смотрите таблицу данных для нашего набора данных.
Этот проект может содержать товарные знаки или логотипы для проектов, продуктов или услуг. Уполномоченное использование товарных знаков или логотипов Microsoft подлежит и должно следовать указаниям Microsoft по товарной марке и брендам. Использование товарных знаков Microsoft или логотипов в модифицированных версиях этого проекта не должно вызывать путаницу или подразумевать спонсорство Microsoft. Любое использование сторонних товарных знаков или логотипов подвержена политике сторонних сторон.
