Programming Puzzles
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
TP3 is a new code translation dataset from the Python Programming Puzzles benchmark that involves translating expert-level python functions to any language.
“we present a new code translation dataset called Translating Python Programming Puzzles (TP3) from the Python Programming Puzzles (Schuster et al., 2021) benchmark that involves translating expert-level python functions to any language.”
From Measuring The Impact Of Programming Language Distribution (2023) · cites this paper as Schuster et al., 2021
The source programs for TP3 are the hand-crafted verification functions for each problem in P3.
“The source programs for TP3 are the hand-crafted verification functions for each problem in P3.”
From Measuring The Impact Of Programming Language Distribution (2023) · cites this paper as Schuster et al., 2021
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2017) · arXiv · doi:10.48550/arxiv.1706.03762 · Cited by 120,404 · see citing works
Scikit-learn: Machine Learning in Python
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Müller, A., Nothman, J., Louppe, G., et al. (2012) · arXiv · doi:10.48550/arxiv.1201.0490 · Cited by 71,016 · see citing works
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019) · Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers) · doi:10.18653/v1/n19-1423 · Cited by 48,293 · see citing works
ImageNet Large Scale Visual Recognition Challenge
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. (2015) · International Journal of Computer Vision · doi:10.1007/s11263-015-0816-y · Cited by 39,380 · see citing works
RoBERTa: A Robustly Optimized BERT Pretraining Approach
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., & Stoyanov, V. (2019) · arXiv · doi:10.48550/arxiv.1907.11692 · Cited by 16,515 · see citing works
Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate ShiftPreprint
Ioffe, S. (2024) · arXiv (Cornell University) · doi:10.57702/o9raffed · Cited by 15,273 · see citing works
Mastering the game of Go without human knowledge
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017) · Nature · doi:10.1038/nature24270 · Cited by 9,084 · see citing works
B., T. A. A. (1946) · The Mathematical Gazette · doi:10.2307/3609182 · Cited by 7,192 · see citing works
SQuAD: 100,000+ Questions for Machine Comprehension of Text
Rajpurkar, P., Zhang, J., Lopyrev, K., & Liang, P. (2016) · Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/d16-1264 · Cited by 6,208 · see citing works
GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding
Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., & Bowman, S. (2018) · Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP · doi:10.18653/v1/w18-5446 · Cited by 4,222 · see citing works
A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al. (2018) · Science · doi:10.1126/science.aar6404 · Cited by 3,562 · cited 2× · see citing works
“Several neighboring fields that have made substantial progress in reasoning include theorem prov357 ing [6], two-player game playing [53], and SAT-solving [7].”
BackgroundMethodCodeBERT: A Pre-Trained Model for Programming and Natural Languages
Feng, Z., Guo, D., Tang, D., Duan, N., Feng, X., Gong, M., Shou, L., Qin, B., Liu, T., Jiang, D., et al. (2020) · Findings of the Association for Computational Linguistics: EMNLP 2020 · doi:10.18653/v1/2020.findings-emnlp.139 · Cited by 2,824 · see citing works
CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge
Talmor, A., Herzig, J., Lourie, N., & Berant, J. (2019) · North American Chapter of the Association for Computational Linguistics · doi:10.18653/v1/n19-1421 · Cited by 2,805 · see citing works
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,375 · see citing works
Language Models as Knowledge Bases?
Petroni, F., Rocktäschel, T., Riedel, S., Lewis, P., Bakhtin, A., Wu, Y., & Miller, A. (2019) · Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) · doi:10.18653/v1/d19-1250 · Cited by 1,834 · see citing works
(2018) · International Conference on Learning Representations · Cited by 1,621 · see citing works
Temporal difference learning and TD-Gammon
Tesauro, G. (1995) · Communications of the ACM · doi:10.1145/203330.203343 · Cited by 1,618 · see citing works
On the inherent intractability of certain coding problems (Corresp.)
Berlekamp, E. R., McEliece, R. J., & van Tilborg, H. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055873 · Cited by 1,542 · see citing works
Castéran, P., & Bertot, Y. (2004) · HAL (Le Centre pour la Communication Scientifique Directe) · Cited by 1,084 · see citing works
Automating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · ACM-SIGACT Symposium on Principles of Programming Languages · doi:10.1145/1926385.1926423 · Cited by 1,039 · see citing works
From Recognition to Cognition: Visual Commonsense Reasoning
Zellers, R., Bisk, Y., Farhadi, A., & Choi, Y. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2019.00688 · Cited by 769 · see citing works
SWAG: A Large-Scale Adversarial Dataset for Grounded Commonsense Inference
Zellers, R., Bisk, Y., Schwartz, R., & Choi, Y. (2018) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/d18-1009 · Cited by 712 · see citing works
DeepCoder: Learning to Write ProgramsPreprint
Balog, M., Gaunt, A. L., Brockschmidt, M., Nowozin, S., & Tarlow, D. (2016) · International Conference on Learning Representations · doi:10.48550/arxiv.1611.01989 · Cited by 641 · see citing works
Noise-tolerant learning, the parity problem, and the statistical query model
Blum, A., Kalai, A., & Wasserman, H. (2003) · Journal of the ACM · doi:10.1145/792538.792543 · Cited by 598 · see citing works
Self-citationSocial IQa: Commonsense Reasoning about Social Interactions
Sap, M., Rashkin, H., Chen, D., LeBras, R., & Choi, Y. (2019) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.18653/v1/d19-1454 · Cited by 588 · see citing works
Automating string processing in spreadsheets using input-output examples
Gulwani, S. (2011) · ACM SIGPLAN Notices · doi:10.1145/1925844.1926423 · Cited by 581 · see citing works
CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation
Lu, S., Guo, D., Ren, S., Huang, J., Svyatkovskiy, A., Blanco, A., Clement, C., Drain, D., Jiang, D., Tang, D., et al. (2021) · arXiv · doi:10.48550/arxiv.2102.04664 · Cited by 536 · see citing works
IntelliCode compose: code generation using transformer
Svyatkovskiy, A., Deng, S. K., Fu, S., & Sundaresan, N. (2020) · Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering · doi:10.1145/3368089.3417058 · Cited by 474 · cited 1× · see citing works
“[54] Alexey Svyatkovskiy, Shao Kun Deng, Shengyu Fu, and Neel Sundaresan.”
BackgroundThe 3 x + 1 Problem and its Generalizations
Lagarias, J. C. (1985) · American Mathematical Monthly · doi:10.1080/00029890.1985.11971528 · Cited by 427 · see citing works
Program Synthesis with Large Language Models
Austin, J., Odena, A., Nye, M., Bosma, M., Michalewski, H., Dohan, D., Jiang, E., Cai, C., Terry, M., Le, Q., et al. (2021) · arXiv · doi:10.48550/arxiv.2108.07732 · Cited by 388 · see citing works
Dynabench: Rethinking Benchmarking in NLP
Kiela, D., Bartolo, M., Nie, Y., Kaushik, D., Geiger, A., Wu, Z., Vidgen, B., Prasad, G., Singh, A., Ringshia, P., et al. (2021) · Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies · doi:10.18653/v1/2021.naacl-main.324 · Cited by 254 · see citing works
Learning and Evaluating Contextual Embedding of Source CodePreprint
Kanade, A., Maniatis, P., Balakrishnan, G., & Shi, K. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.00059 · Cited by 238 · see citing works
FlashMeta: a framework for inductive program synthesis
Polozov, O., & Gulwani, S. (2015) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/2814270.2814310 · Cited by 229 · see citing works
Self-citationCodeBLEU: a Method for Automatic Evaluation of Code Synthesis
Ren, S., Guo, D., Lu, S., Zhou, L., Liu, S., Tang, D., Sundaresan, N., Zhou, M., Blanco, A., & Ma, S. (2020) · arXiv · doi:10.48550/arxiv.2009.10297 · Cited by 214 · see citing works
Bebras International Contest on Informatics and Computer Literacy: Criteria for Good Tasks
Dagienė, V., & Futschek, G. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-69924-8_2 · Cited by 187 · see citing works
Polozov, O., Gulwani, S., & Singh, R. K. (2017) · Cited by 167 · see citing works
Self-citationCodeSearchNet Challenge: Evaluating the State of Semantic Code Search
Husain, H., Wang, H.-H., Gazit, T., Allamanis, M., & Brockschmidt, M. (2019) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.7908467 · Cited by 144 · see citing works
Measuring Coding Challenge Competence With APPS
Hendrycks, D., Basart, S., Kadavath, S., Mazeika, M., Arora, A., Guo, E., Burns, C., Puranik, S., He, H., Song, D., et al. (2021) · arXiv · doi:10.48550/arxiv.2105.09938 · Cited by 142 · see citing works
Get Your Vitamin C! Robust Fact Verification with Contrastive Evidence
Schuster, T., Fisch, A., & Barzilay, R. (2021) · Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies · doi:10.18653/v1/2021.naacl-main.52 · Cited by 126 · see citing works
Self-citationA Machine Learning Framework for Programming by Example
Menon, A. K., Tamuz, O., Gulwani, S., Lampson, B., & Kalai, A. T. (2013) · Cited by 112 · see citing works
Self-citationSPoC: Search-based Pseudocode to Code
Kulal, S., Pasupat, P., Chandra, K., Lee, M., Padon, O., Aiken, A., & Liang, P. (2019) · arXiv · doi:10.48550/arxiv.1906.04908 · Cited by 103 · see citing works
Task-Oriented Dialogue as Dataflow Synthesis
Andreas, J., Bufe, J., Burkett, D., Chen, C., Clausman, J., Crawford, J., Crim, K., DeLoach, J., Dorner, L., Eisner, J., et al. (2020) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00333 · Cited by 98 · see citing works
You Autocomplete Me: Poisoning Vulnerabilities in Neural Code CompletionPreprint
Schuster, R., Song, C., Tromer, E., & Shmatikov, V. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.02220 · Cited by 83 · see citing works
Generative Language Modeling for Automated Theorem Proving
Polu, S., & Sutskever, I. (2020) · arXiv · doi:10.48550/arxiv.2009.03393 · Cited by 82 · see citing works
Structural Language Models of CodePreprint
Alon, U. S., Sadaka, R., Levy, O., & Yahav, E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.00577 · Cited by 60 · see citing works
Bootstrap Learning via Modular Concept Discovery
Dechter, E., Malmaud, J., Adams, R. P., & Tenenbaum, J. B. (2014) · Cited by 43 · see citing works
UNICORN on RAINBOW: A Universal Commonsense Reasoning Model on a New Multitask Benchmark
Lourie, N., Bras, R. J. L., Bhagavatula, C., & Choi, Y. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i15.17590 · Cited by 19 · see citing works
Guide to Competitive Programming: Learning and Improving Algorithms Through Contests
Laaksonen, A. (2018) · doi:10.1007/978-3-030-39357-1 · Cited by 10 · see citing works
Neural Program Search: Solving Data Processing Tasks from Description and Examples
Polosukhin, I., & Skidanov, A. (2018) · Cited by 4 · see citing works
Glass-Box Program Synthesis: A Machine Learning ApproachPreprint
Christakopoulou, K., & Kalai, A. T. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.08669 · Cited by 1 · see citing works
Self-citationBERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2018) · arXiv · doi:10.48550/arxiv.1810.04805
Flagged first, then by citations
Research works printed but not linked: 9
- [9][9] Armin Biere, Marijn Heule, and Hans van Maaren. Handbook of satisfiability , volume 185. IOS press, 2009. -
- [10][10] N. Biggs, P.M.L.S.E.N.L. Biggs, London Mathematical Society, London Mathematical Society lecture note series, and S.P.G.N.J. Hitchin. Finite Groups of Automorphisms: Course Given at the University of Southampton, October-December 1969 . Lecture note series. Cambridge University Press, 1971. ISBN 9780521082150. URL https://books.google.com/books? id=flA4AAAAIAAJ . -
- [12][12] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems , volume 33, pages 1877-1901. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/file/ 1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf . -
- [14][14] François Chollet. On the measure of intelligence. arXiv preprint arXiv:1911.01547 , 2019. - · arXiv
- [24][24] G. H. Hardy, E. M. Wright, D. R. Heath-Brown, and Joseph H. Silverman. An introduction to the theory of numbers . Oxford University Press, Oxford; New York, 2008. ISBN 9780199219858 0199219850 9780199219865 0199219869. -
- [30][30] Burt Kaliski. RSA factoring challenge , pages 531-532. Springer US, Boston, MA, 2005. ISBN 978-0-387-23483-0. doi: 10.1007/0-387-23483-7\_362. URL https://doi.org/10.1007/ 0-387-23483-7\_362 . - · DOI
- [39][39] C. Mayer. Python One-Liners: Write Concise, Eloquent Python Like a Professional . No Starch Press, Incorporated, 2020. ISBN 9781718500501. URL https://books.google. com/books?id=jVv6DwAAQBAJ . -
- [59][59] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-theart natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations , pages 38-45, Online, October 2020. Association for Computational Linguistics. URL https://www.aclweb.org/anthology/ 2020.emnlp-demos.6 . -
- [60][60] Maksym Zavershynskyi, Alexander Skidanov, and Illia Polosukhin. NAPS: natural program synthesis dataset. CoRR , abs/1807.03168, 2018. URL http://arxiv.org/abs/1807.03168 . - · arXiv
Cited by
Sorted by citations
When Language Model Meets Private Library
Zan, D., Chen, B., Lin, Z., Guan, B., Yongji, W., & Lou, J. (2022) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2022.findings-emnlp.21 · Cited by 51 · see citing works
Using the gaming chatbot to develop algorithmic and logical thinking skills
Varnavsky, A. N. (2024) · Informatics and Education · doi:10.32517/0234-0453-2024-39-2-48-58 · Cited by 2 · see citing works
Measuring The Impact Of Programming Language Distribution
Orlanski, G., Xiao, K., Garcia, X., Hui, J., Howland, J., Malmaud, J., Austin, J., Singh, R., & Catasta, M. (2023) · arXiv · doi:10.48550/arxiv.2302.01973
“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.”
MethodInfluential
- Authors
- Schuster, T., Kalyan, A., Polozov, O., & Kalai, A. T.
- Affiliations
- Microsoft (United States) (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2021
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2106.05784
- OpenAlex
- W3168035277
- Cited by
- 2
- References
- 47
- Citations by year
- 2024: 1 · 2022: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Computer Science Applications › Teaching and Learning Programming
- Physical Sciences › Computer Science › Information Systems › Software Engineering Research
- Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
- Keywords
- programming puzzles, program synthesis, GPT-3, codices, Tower of Hanoi, factoring, puzzle difficulty
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
