A couple of days ago I wondered how many authors (except for me) write problems about programming languages. I was hoping to be not alone in my passion to this topic; but the reality exceeded all expectations. Of course, problems which feature programming languages are much scarcer than ones about computers, processors, microchips, parallel computing, databases and other IT things, but still much more frequent than ones about, say, dragons :-)
1. TopCoder
The early years of TopCoder presented the participants with several programming-languages-featuring problems. Most of them (7/9) are pretty similar: given the source code written in C- or Pascal-like language, analyze it and report the result.
Problem | Task |
---|---|
QuiningTopCoder | Write an interpreter for Unefunge |
ScriptLanguage | Given source code in Visual Basic-like language with conditional jumps, find unreachable lines and uninitialized variables |
VariableDeclaration | Find all variables with invalid declarations (from C# point of view, i.e., with duplicate declaration of a variable in a block and its sub-block). The original program is given as a set of blocks and variables declared in them, so the usage of the language itself is minimized |
Loopy | Find the shortest loop in an imperative program written as a set of conditional jumps |
DeadCode | Detect unreachable commands in a program written as a set of conditional jumps |
CommentNest | Clear the given program of nested comments /* ... */ |
Comment | Clear the given program in Java-like language of nested comments // и /* ... */ , without nesting but with strings and escaped characters |
Execution | Count basic commands executed by a program with loops |
TurtleGraphics | Turtle graphics in 3D |
It's hard to say why the flow of such problems trickled away in the last years. I can suggest several versions:
- the change of Algorithms coordinator (or his aesthetic preferences).
- the lack of interest among authors. It's much easier to invent a problem about something abstract instead of following a certain topic, especially this one.
- the tasks focus on algorithmic aspects of the problem instead of a lengthy and unexciting implementation.
- the platform limits expressive means of the problems; for example, if the problem asks to generate a piece of code instead of analyzing the given one, it becomes harder immediately. TopCoder testing system disallows to process the return value (interpret the returned program and compare its behavior with the requirements), so the answer must be unique to be compared with a reference one. And this means that the problem requires additional limitations — the return must be the shortest possible, lexicographically earliest if several of the same length are possible etc. Finding an algorithm which minimizes the length of the generated code and proving its correctness is hardly a suitable task for a single SRM :-)
- if the problem asks to generate a program which does something, this something must be described with input parameters in a proper way (that is, there should be a lot of input datasets differing in a non-trivial way). Off the top of my head I can think of "output the given message" and "calculates the given arithmetic expression" — both not exactly thrilling.
2. Codeforces
On Codeforces the things are pretty good, especially given that the site is much younger than the other ones mentioned in this article. Besides my (round #96)[http://codeforces.me/blog/entry/3302], there are problems 93C - Azembler (generate a program in Assembler-like language) and 39A - C*++ Calculations (about increment operators a++ and ++a). Generally this will come with time — the system allows to make the problems diverse enough, so new themed problems are a matter of authors' ingenuity.
P.S. And this point gets immediate support from today's round: 195C - Try and Catch is based on exceptions handling in Vasya Programming Language :-)
3. Challenge24
I've already mentioned that I love this competition, haven't I? Well, I'm going to repeat this again: I really like Challenge24, not least because of the topics and problems diversity. In the last four years either the finals or the electronic contest include a problem which asks the teams to write programs in some weird language or at least interpret the given ones.
Problem | Task |
---|---|
2012, EC, D. If | Optimize the size of the given program in a language with random memory access. This problem allowed plenty of approaches: the easiest was to remove unused and excessive code and to optimize calculation of constants (well, the easiest was to submit the original programs without any modification, which yielded some points, but that's trivial). Advanced approaches required coding an interpreter or a translator and analyzing its high-level purpose. |
2011, Finals, K. Punchcards | Write a program performing the given task in an Assembly-like language. A bonus dwim was the submission format — the code had to be copied onto "punch cards" which had commands written in binary codes, with 1s represented by fat black circles in certain boxes. Filled punch cards were to be submitted to admins, and after some time one of them arrived with the news. A dreary job (even the shortest program couldn't fit on one card), and imagine the joy of editing and debugging them :-) |
2010, EC, G. Compiler | Translate the described language into Assembly |
2009, Finals, 3 Cheap labor | Write a program performing the given task in Piet (an inspiring language indeed :-)). The tasks were never harder than calculating factorial, but this was compensated by language complexity. By the way, I wonder whether any finalist had a Piet programs generator (or rather a translator from pseudocode) lying around — my estimate is that it would give a leg up to the lucky one. Just checked — my computer has it; I wish this problem was around in the years I was at the finals :-) |
2003, Finals, Chapter 7 Automated testing | That year the finals features one huge task split in several smaller ones; one of the subtasks involved writing an interpreter for a fictional scripting language AUCH |
Note that this format suits Challenge24 nearly perfectly. First, it differs a lot from the typical contest tasks, so Algorithm reds have smaller advantage on it (I can't really imagine a format which would give them no advantage at all). Second, it implements two principles of Challenge24: first (small) test cases can be solved by hand while the larger ones require some automation, and different submissions can be compared by "quality" (the length of generated code), thus enabling relative scoring. Finally, the timing and the teaming of the contest allows to set problems which require writing an interpreter before starting the actual programs.
4. IPSC
Another contest which doesn't limit the authors' creativity by the format: each problem needs only two tests (subtasks), and they may differ a lot (unlike Challenge24 in which the tests for the problem vary in size and complexity but not meaning). Therefore each year of the competition (alas, except for the last one) has a fancy problem featuring a programming language of some kind, either in the main contest or in practice one.
Problem | Task |
---|---|
2011, H. HQ0-9+-INCOMPUTABLE?! | Write a program in described esoteric language which outputs the given string of digits |
2010, practice, R. Round and round it goes | Select the constants to send the given program into an infinite loop |
2009, С. Cryptic punchcards | Decode punch cards. The punch cards of the second subtask contain a Fortran program with inevident output (comments in several styles and multiline commands) |
2009, I. Instructions | Write a program in an Assembly-like language |
2008, C. Comparison Mysteries | Tricks with Java data types |
2007, practice, Q. QuackQuack | Write a program in an esoteric queue-based language Quack. Quack was featured in several earlier practice contests, and debuted in 2004 main contest |
2006. J. Jamcode 2006 | Given a wrong C++ program, find an input for which it will produce correct output |
2005, B. Bottom Coder | Modify the given program in one character so that it performs the given task |
2005, practice, Q. Quack Strikes Back | Write a program in Quack |
2004, G. Gets and Puts | Quack debut :-) |
2003, B. begin 4 7 add | Figure out what a PostScript program does |
2002, A. Andrews's Exams III | Given a program in C and Pascal, find input which makes it work fast (easy) or figure out its output (hard) |
2001. A. Andrews's Exams II | Figure out the output of the given program in C and Pascal |
2000. A. Andrews's Exams | Calculate the asterisks printed by the given program in C and Pascal |
5. Other sources
There is good reason to believe that various ACM-contests use programming-languages-based problems as well, and some digging through archives will reveal a lot of interesting cases.
- The first glance at acm.timus.ru shows us tag "unusual problems" and a problem Introspective Program which asks to write a quine in a mysterious language PIBAS...
- ...and Language Ocean from eastern subregional of NEERC 2011 which requires to implement types inference and check of types validity...
- ...and Time Limit Exceeded which makes you interpret the given program and terminate it mercilessly after only ten million commands...
- ...and Brainfuck which asks to generate the shortest program in a version of Brainfuck without loops.
- A series of problems from Ural State University introduces the participant with D++ language (nothing in common with Meta D++, or DigiSystems D++, or D++ for distributed calculations).
- More examples given in post comments in Russian interface.
And what problems about programming languages do you know?