[2106.05784] Programming Puzzles

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 $x$ which makes $f$ output "True". The puzzles are objective in that each one is specified entirely by the source code of its verifier $f$, so evaluating $f(x)$ is all that is needed to test a candidate solution $x$. 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 that are immediately obvious to human programmers (but not necessarily to AI), to classic programming puzzles (e.g., Towers of Hanoi), to interview/competitive-programming problems (e.g., dynamic programming), to longstanding open problems in algorithms and mathematics (e.g., factoring). The objective nature of P3 readily supports self-supervised bootstrapping. We develop baseline enumerative program synthesis and GPT-3 solvers that are capable of solving easy puzzles -- even without access to any reference solutions -- by learning from their own past solutions. Based on a small user study, we find puzzle difficulty to correlate between human programmers and the baseline AI solvers.

Programming Puzzles Tal Schuster Ashwin Kalyan Oleksandr Polozov Adam Tauman Kalai MIT Allen Inst. for AI Microsoft Research Microsoft Research Abstract arXiv:2106.05784v3 [cs.LG] 6 Nov 2021 We introduce a new type of programming challenge called programming puzzles,…

related reading

• [2203.07814] Competition-Level Code Generation with AlphaCodearxiv.org
• [2112.02969] Jigsaw: Large Language Models meet Program Synthesisarxiv.org
• Program Synthesis with Large Language Modelsarxiv.org
• the-illusion-of-thinking.pdfml-site.cdn-apple.com
• [2201.11903] Chain of Thought Prompting Elicits Reasoning in Large Language Modelsarxiv.org
• [2501.01257] CodeElo: Benchmarking Competition-level Code Generation of LLMs with Human-comparable Elo Ratingsarxiv.org
• [2108.07732] Program Synthesis with Large Language Modelsarxiv.org
• From Rosetta to Match-Up: A Paired Corpus of Linguistic Puzzles with Human and LLM Benchmarksarxiv.org
• GitHub - srush/Tensor-Puzzles: Solve puzzles. Improve your pytorch.github.com
• Competitive programming with AlphaCode — Google DeepMinddeepmind.com
• [2510.09714] All Code, No Thought: Current Language Models Struggle to Reason in Ciphered Languagearxiv.org
• 2308.03958arxiv.org