Nickolas's blog

By Nickolas, 12 years ago, translation, In English

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?

  • Vote: I like it
  • +28
  • Vote: I do not like it

| Write comment?