Programming Puzzles
By Tal Schuster, Ashwin Kalyan, Oleksandr Polozov, Adam Tauman Kalai. 2021
40 citations recorded by the source corpus.
We introduce a new type of programming challenge called programming puzzles, as an objective and comprehensive evaluation of program synthesis, and release an open-source dataset of Python Programming Puzzles (P3). Each puzzle is defined by a short Python program $f$, and the goal is to find an input which makes $f$ return True. The puzzles are objective in that each one is specified entirely by the source code of its verifier $f$, so evaluating $f$ is all that is needed to test a candidate solution. They do not require an answer key or input/output examples, nor do they depend on natural language understanding. The dataset is comprehensive in that it spans problems of a range of difficulties and domains, ranging from trivial string manipulation problems, to classic programming puzzles (e.g., Tower of Hanoi), to interview/competitive-programming problems (e.g., dynamic programming), to longstanding open problems in algorithms and mathematics (e.g., factoring). We develop baseline enumerative program synthesis, GPT-3 and Codex solvers that are capable of solving puzzles -- even without access to any reference solutions -- by learning from their own past solutions. Codex performs best, solving up to 18% of 397 test problems with a single try and 80% of the problems with 1,000 tries per problem. In a small user study, we find a positive correlation between puzzle-solving performance and coding experience, and between the puzzle difficulty for humans and AI solvers. Therefore, further improvements on P3 could have a significant impact on many program synthesis areas.
Subfields: Evaluation & Benchmarks, Code Generation & Program Synthesis
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Evaluation & Benchmarks
In Code Generation & Program Synthesis
Citations in the corpus
- Language Models Can Teach Themselves to Program Better (2022, methodology): “The experiments on fine-tuning LMs to improve their performance on solving programming puzzles were done with the GPT-Neo model [4], as described in the introduction.”
- Quiet-STaR: Language Models Can Teach Themselves to Think Before Speaking (2024, background): “Zelikman et al. (2023b) shows how a bootstrapping loop can be implemented where a model repeatedly improves a code-improver using the same code-improver and Haluptzok et al. (2023) shows how language models can bootstrap their programming ability with programming puzzles Schuster et al. (2021).”
- Measuring The Impact Of Programming Language Distribution (2023, methodology): “We demonstrate this functionality by creating a new dataset called Translating Python Programming Puzzles (TP3) from the Python Programming Puzzles (Schuster et al., 2021) benchmark, where the objective is to translate expert-level python programs to other languages.”
- Unifying Language Learning Paradigms (2022, background): “Examples of these include UNICORN (Lourie et al., 2021) for commonsense reasoning, UnifiedQA (Khashabi et al., 2020, 2022) for question answering, Programming Puzzles (Schuster et al., 2021b) for problem solving, and UnifiedSKG (Xie et al., 2022) for Structured Knowledge Grounding.”
- Confident Adaptive Language Modeling (2022, methodology): “Autoregressive language modeling provides a flexible framework for solving complex tasks with a unified natural language input and output format, while also relaxing the need for large-scale task-specific data collection and training [67; 15; 17; 58; 80].”
- A Survey of Deep Learning for Mathematical Reasoning (2022, unknown): “Sci-enceQA (Lu et al., 2022a) involves numerical reasoning in scientific domains, while P3 (Schuster et al., 2021) studies the function inference ability of deep learning models to find a valid input which makes the given program return True .”