(This is a guest post by Moritz Lenz. If you're wondering what this is all about, it's the aftermath of The 2011 Perl 6 Coding Contest. If you're not wondering, it's still about that.)

Let's consider the first task from the Perl 6 Coding Contest 2011.

Here is the description of the task once more:

What non-negative integers can you write as expressions containing exactly
four occurrences the number 9, and any of the binary operators *, /, %, +,
-, prefix negations, and any number of matching pairs of parentheses you
care to use?

The program should accept an upper limit N as a command-line argument.
It should then print all integers 0..N in increasing order, along with
an expression with four nines, if any such was found.

It was probably the easiest of all tasks, and the one we got the most submissions for. Yet there were still some things that could go wrong, and some submissions got some of them wrong:

• non-negative implies that we start at 0 = 9 + 9 - 9 - 9, not at 1
• integers means that the result must be an integer; it does not mean that intermediate results are automatically rounded or truncated
• the expressions must consist of four times the number 9, not the digit nine. Thus 99 is not a valid expression of two nines.

All contestants solved this task with the following strategy: first find all possible expressions involving four nines (and possibly filter out those out of range), then iterate the numbers from 0 to N and check for each if an expression was found.

One possible approach to generate all expresions is to hard-code all expressions with one nine, namely 9 and -9. Then apply all operators to all combinations of those, and thus generate all expressions with two nines. This is a good time for filtering out duplicates, for example 18 == 9 + 9 == 9 - (-9). Then expressions of greater length can be generated from the shorter ones in the same manner.

There are just two small pitfalls: the first is that one has to remember that not all expressions can be generated by combining expressions of length (N-1) and 1. For example 324 == (9 + 9) * (9 + 9) can only be written as the combination of two expressions with two nines each. The second small pitfall is that three of the operators (%, / and -) are not commutative, so one has to explicitly try both combinations of $a op $b and $b op $a, or take care of that in some other way.

The task description allowed the prefix minus operator, but including it into the production does not produce any new numbers; it is sufficent to seed the expressions of length one with (9, -9).

As usual, we've published each contestant's code along with a review; feel free to have a look. This year, we're also publish solutions from people who sent in solutions but didn't sign up for the contest.

Isn't it noteworthy how, even with this narrow a task, people's solutions are all over the board in terms of the constructs used, code size, and style? We think so.

Stand by for the review on t2: "Sums of cubes".