mlsanityData to 7 Oct 2026

Programming Puzzles

arXiv 2106.05784 ↗First posted 10 Jun 2021cs.LG cs.AI cs.CLcited by 25

Not on the map. Why?

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.

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

Builds on

29 of 85 references.

References · 29

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,266
  5. 2014ImageNet Large Scale Visual Recognition Challengecited by 8,441
  6. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  7. 2018GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understandingcited by 4,854
  8. 2016SQuAD: 100,000+ Questions for Machine Comprehension of Textcited by 4,115
  9. 2016Gaussian Error Linear Units (GELUs)cited by 3,431
  10. 2019Language Models as Knowledge Bases?cited by 1,922
  11. 2018CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledgecited by 1,793
  12. 2020CodeBERT: A Pre-Trained Model for Programming and Natural Languagescited by 1,286
17 more
  1. 2021Measuring Coding Challenge Competence With APPScited by 879
  2. 2021CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generationcited by 732
  3. 2019CodeSearchNet Challenge: Evaluating the State of Semantic Code Searchcited by 638
  4. 2018From Recognition to Cognition: Visual Commonsense Reasoningcited by 553
  5. 2020CodeBLEU: a Method for Automatic Evaluation of Code Synthesiscited by 468
  6. 2021Dynabench: Rethinking Benchmarking in NLPcited by 447
  7. 2020Generative Language Modeling for Automated Theorem Provingcited by 379
  8. 2018SWAG: A Large-Scale Adversarial Dataset for Grounded Commonsense Inferencecited by 333
  9. 2020IntelliCode Compose: Code Generation Using Transformercited by 225
  10. 2021Get Your Vitamin C! Robust Fact Verification with Contrastive Evidencecited by 222
  11. 2019SPoC: Search-based Pseudocode to Codecited by 176
  12. 2016DeepCoder: Learning to Write Programscited by 145
  13. 2020Task-Oriented Dialogue as Dataflow Synthesiscited by 122
  14. 2020You Autocomplete Me: Poisoning Vulnerabilities in Neural Code Completioncited by 112
  15. 2021UNICORN on RAINBOW: A Universal Commonsense Reasoning Model on a New Multitask Benchmarkcited by 98
  16. 2018NAPS: Natural Program Synthesis Datasetcited by 14
  17. 2017Glass-Box Program Synthesis: A Machine Learning Approachcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 9; 2023: 3; 2024: 6; 2025: 5; 2026: 1.

25 papers.

Sort:

By area:

  1. 2021Program Synthesis with Large Language Modelscited by 3,509
  2. 2022Confident Adaptive Language Modelingcited by 297
  3. 2022UL2: Unifying Language Learning Paradigmscited by 292
  4. 2024Quiet-STaR: Language Models Can Teach Themselves to Think Before Speakingcited by 292
  5. 2022Transformers Learn Shortcuts to Automatacited by 260
  6. 2022A Survey of Deep Learning for Mathematical Reasoningcited by 124
  7. 2024Meta-Prompting: Enhancing Language Models with Task-Agnostic Scaffoldingcited by 115
  8. 2024Buffer of Thoughts: Thought-Augmented Reasoning with Large Language Modelscited by 91
  9. 2022Language Models Can Teach Themselves to Program Bettercited by 75
  10. 2022When Language Model Meets Private Librarycited by 54
  11. 2024Attribute First, then Generate: Locally-attributable Grounded Text Generationcited by 54
  12. 2022Learning Math Reasoning from Self-Sampled Correct and Partially-Correct Solutionscited by 38
13 more
  1. 2022Fault-Aware Neural Code Rankerscited by 33
  2. 2023Measuring The Impact Of Programming Language Distributioncited by 32
  3. 2025Division-of-Thoughts: Harnessing Hybrid Language Model Synergy for Efficient On-Device Agentscited by 24
  4. 2024Step-by-Step Reasoning to Solve Grid Puzzles: Where do LLMs Falter?cited by 18
  5. 2025Route-and-Reason: Scaling Large Language Model Reasoning with Reinforced Model Routercited by 13
  6. 2025VisualSphinx: Large-Scale Synthetic Vision Logic Puzzles for RLcited by 11
  7. 2024Reversal of Thought: Enhancing Large Language Models with Preference-Guided Reverse Reasoning Warm-upcited by 10
  8. 2023ACES: Generating Diverse Programming Puzzles with with Autotelic Generative Modelscited by 6
  9. 2025PuzzlePlex: Benchmarking Foundation Models on Reasoning and Planning with Puzzlescited by 5
  10. 2022A Survey on Artificial Intelligence for Source Code: A Dialogue Systems Perspectivecited by 3
  11. 2023Synthesizing a Progression of Subtasks for Block-Based Visual Programming Taskscited by 1
  12. 2025Dr. Boot: Bootstrapping Program Synthesis Language Models to Perform Repairingcited by 0
  13. 2026The Token Games: Evaluating Language Model Reasoning with Puzzle Duelscited by 0