What should I do with my fastest code challenge?

Question

So I've vastly overestimated the processing it would take to find domino tilings of a rectangle and wrote up a challenge that has gotten a little weird.

First of all, the execution times are really low. For both answers, execution takes roughly the same time as compilation. The answers (both in C) cannot even turn on compiler optimizations because the increased compilation time actually hurts their scores...

Now, both answers have to work for all rectangles up to 8 x 8 but are currently scored using 8 x 6 rectangles. 8 x 8 takes roughly a second for both answers (with optimizations turned on), so that might help. Doing so would not change the positions in the current leader board.

But there's another problem. The mandatory output is 9 MiB for 8 x 6 and 950 MiB for 8 x 8. Printing the output seems to take up roughly half the execution times for the answers in their current state, and it has been suggested that preparing the output for printing might actually require a lot more time than finding the valid tilings.

I thought requiring the output instead of just counting the tilings was it is was a good way of making sure that there was no blurry line between hardcoding the result and actually calculating it. At the same time, eliminating the output doesn't seem fair to the answerers who spent a considerable amount of time optimizing the output (which wasn't intended to be the point, but still is something that can be scored).

My gut feeling in that its too late to change the output format, but that I should score the submissions using 8 x 8 rectangles. Thoughts?

Answer 1

If you want to reduce the impact of producing the output, I don't think increasing the size to 8 x 8 would help. At least for my solution, the relative time to produce the output is actually larger at that size.

For 8 x 6, the times (as measured on my own machine) are:

• 167,089 solutions.
• 15 ms for finding solutions (counted only).
• 30 ms for finding and outputting solutions (redirected to /dev/null).
• 50% of time used for output.

For 8 x 8, the same times are:

• 12,988,816 solutions.
• 778 ms for finding solutions.
• 1,822 ms for finding and outputting solutions.
• 57% of time used for output.

The only problem you solve with the larger size is that the compile time becomes mostly insignificant. But that could also be done by not counting the compile time at all. I figure you might have wanted to include the compile time to give interpreted languages a better chance. But in reality, they're probably at a big disadvantage anyway. I suspect that it would be almost like using a non-golf language for a golf challenge.

IMHO, only requiring the solution count as output, and measuring it for 8 x 8, would be the best option if you want to measure the efficiency of the core algorithm and its implementation. It should be possible to detect blatant cheating from looking at the code.

Or maybe you could have a hybrid? Say the solutions need to produce the output by default, which would be used for correctness testing. But they can have a command line switch to disable output, and only produce a count, which is used for the performance benchmark.

BTW: You absolutely have to require some kind of output. Otherwise a good optimizing compiler might optimize away the whole code.