Python Programming Puzzles (P3)
This repo contains a dataset of python programming puzzles which can be used to teach and evaluate an AI's programming proficiency. We hope this dataset with grow rapidly, and it is already diverse in terms of problem difficult, domain, and algorithmic tools needed to solve the problems. Please propose a new puzzle or browse newly proposed puzzles or contribute through pull requests.
To learn more about how well AI systems such as GPT-3 can solve these problems, read our paper:
Programming Puzzles. Tal Schuster, Ashwin Kalyan, Oleksandr Polozov, Adam Tauman Kalai.
Adam Tauman Kalai.
@misc{schuster2021programming,
title={Programming Puzzles},
author={Tal Schuster and Ashwin Kalyan and Oleksandr Polozov and Adam Tauman Kalai},
year={2021},
eprint={2106.05784},
archivePrefix={arXiv},
}
To reproduce the results in the paper, see the solvers folder.
If you just want to dive right into solving a few puzzles, try the intro notebook at Binder
that shows which puzzles the AI baselines solved and which they did not, so you can see how
your programming compares.
What is a python programming puzzle?
Each puzzle takes the form of a python function that takes an answer as an argument.
The goal is to find an answer which makes the function return True.
This is called satisfying the puzzle, and that is why the puzzles are all named sat.
def sat(s: str):
return "Hello " + s == "Hello world"
The answer to the above puzzle is the string "world" because sat("world") returns True. The puzzles range from trivial problems like this, to classic puzzles,
to programming competition problems, all the way through open problems in algorithms and mathematics.
A slightly harder example is:
def sat(s: str):
"""find a string with 1000 o's but no consecutive o's."""
return s.count("o") == 1000 and s.count("oo") == 0
A more challenging puzzle that requires dynamic programming is the
longest increasing subsequence problem
which we can also describe with strings:
from typing import List
def sat(x: List[int], s="Dynamic programming solves this classic job-interview puzzle!!!"):
"""Find the indexes (possibly negative!) of the longest monotonic subsequence"""
return all(s[x[i]] <= s[x[i+1]] and x[i+1] > x[i] for i in range(25))
The classic Towers of Hanoi puzzle can be written as follows:
def sat(moves: List[List[int]]):
"""moves is list of [from, to] pairs"""
t = ([8, 7, 6, 5, 4, 3, 2, 1], [], []) # towers state
return all(t[j].append(t[i].pop()) or t[j][-1] == min(t[j]) for i, j in moves) and t[0] == t[1]
For more information on the motivation and how programming puzzles can help AI learn to program, see
the paper:
Programming Puzzles, by Tal Schuster, Ashwin Kalyan, Alex Polozov, and Adam Tauman Kalai. 2021 (Link to be added shortly)
