(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
- 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
99is 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. 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
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 (
-) 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
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".