# Programming Puzzles

arXiv: https://arxiv.org/abs/2106.05784 · HTML: https://mlsanity.com/paper/2106.05784/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 85 references that are in the map.
- First posted on arXiv 10 Jun 2021.

## Builds on (most cited first, 29 of 29)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Language Models as Knowledge Bases?](https://mlsanity.com/paper/1909.01066/) (2019)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [CodeBERT: A Pre-Trained Model for Programming and Natural Languages](https://mlsanity.com/paper/2002.08155/) (2020)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation](https://mlsanity.com/paper/2102.04664/) (2021)
- [CodeSearchNet Challenge: Evaluating the State of Semantic Code Search](https://mlsanity.com/paper/1909.09436/) (2019)
- [From Recognition to Cognition: Visual Commonsense Reasoning](https://mlsanity.com/paper/1811.10830/) (2018)
- [CodeBLEU: a Method for Automatic Evaluation of Code Synthesis](https://mlsanity.com/paper/2009.10297/) (2020)
- [Dynabench: Rethinking Benchmarking in NLP](https://mlsanity.com/paper/2104.14337/) (2021)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [SWAG: A Large-Scale Adversarial Dataset for Grounded Commonsense Inference](https://mlsanity.com/paper/1808.05326/) (2018)
- [IntelliCode Compose: Code Generation Using Transformer](https://mlsanity.com/paper/2005.08025/) (2020)
- [Get Your Vitamin C! Robust Fact Verification with Contrastive Evidence](https://mlsanity.com/paper/2103.08541/) (2021)
- [SPoC: Search-based Pseudocode to Code](https://mlsanity.com/paper/1906.04908/) (2019)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [You Autocomplete Me: Poisoning Vulnerabilities in Neural Code Completion](https://mlsanity.com/paper/2007.02220/) (2020)
- [Task-Oriented Dialogue as Dataflow Synthesis](https://mlsanity.com/paper/2009.11423/) (2020)
- [UNICORN on RAINBOW: A Universal Commonsense Reasoning Model on a New Multitask Benchmark](https://mlsanity.com/paper/2103.13009/) (2021)
- [NAPS: Natural Program Synthesis Dataset](https://mlsanity.com/paper/1807.03168/) (2018)
- [Glass-Box Program Synthesis: A Machine Learning Approach](https://mlsanity.com/paper/1709.08669/) (2017)

## Built on by (most cited first, 25 of 25)

- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Confident Adaptive Language Modeling](https://mlsanity.com/paper/2207.07061/) (2022)
- [Quiet-STaR: Language Models Can Teach Themselves to Think Before Speaking](https://mlsanity.com/paper/2403.09629/) (2024)
- [UL2: Unifying Language Learning Paradigms](https://mlsanity.com/paper/2205.05131/) (2022)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [A Survey of Deep Learning for Mathematical Reasoning](https://mlsanity.com/paper/2212.10535/) (2022)
- [Meta-Prompting: Enhancing Language Models with Task-Agnostic Scaffolding](https://mlsanity.com/paper/2401.12954/) (2024)
- [Buffer of Thoughts: Thought-Augmented Reasoning with Large Language Models](https://mlsanity.com/paper/2406.04271/) (2024)
- [Language Models Can Teach Themselves to Program Better](https://mlsanity.com/paper/2207.14502/) (2022)
- [When Language Model Meets Private Library](https://mlsanity.com/paper/2210.17236/) (2022)
- [Attribute First, then Generate: Locally-attributable Grounded Text Generation](https://mlsanity.com/paper/2403.17104/) (2024)
- [Learning Math Reasoning from Self-Sampled Correct and Partially-Correct Solutions](https://mlsanity.com/paper/2205.14318/) (2022)
- [Fault-Aware Neural Code Rankers](https://mlsanity.com/paper/2206.03865/) (2022)
- [Measuring The Impact Of Programming Language Distribution](https://mlsanity.com/paper/2302.01973/) (2023)
- [Division-of-Thoughts: Harnessing Hybrid Language Model Synergy for Efficient On-Device Agents](https://mlsanity.com/paper/2502.04392/) (2025)
- [Step-by-Step Reasoning to Solve Grid Puzzles: Where do LLMs Falter?](https://mlsanity.com/paper/2407.14790/) (2024)
- [Route-and-Reason: Scaling Large Language Model Reasoning with Reinforced Model Router](https://mlsanity.com/paper/2506.05901/) (2025)
- [VisualSphinx: Large-Scale Synthetic Vision Logic Puzzles for RL](https://mlsanity.com/paper/2505.23977/) (2025)
- [Reversal of Thought: Enhancing Large Language Models with Preference-Guided Reverse Reasoning Warm-up](https://mlsanity.com/paper/2410.12323/) (2024)
- [ACES: Generating Diverse Programming Puzzles with with Autotelic Generative Models](https://mlsanity.com/paper/2310.10692/) (2023)
- [PuzzlePlex: Benchmarking Foundation Models on Reasoning and Planning with Puzzles](https://mlsanity.com/paper/2510.06475/) (2025)
- [A Survey on Artificial Intelligence for Source Code: A Dialogue Systems Perspective](https://mlsanity.com/paper/2202.04847/) (2022)
- [Synthesizing a Progression of Subtasks for Block-Based Visual Programming Tasks](https://mlsanity.com/paper/2305.17518/) (2023)
- [Dr. Boot: Bootstrapping Program Synthesis Language Models to Perform Repairing](https://mlsanity.com/paper/2507.15889/) (2025)
- [The Token Games: Evaluating Language Model Reasoning with Puzzle Duels](https://mlsanity.com/paper/2602.17831/) (2026)

## Abstract (arXiv)

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.