HHC 2017 RPL Programming contest information and results thread

[Claudio L.]

While we wait for Gene's sample data, I'd like to discuss approaches.
I did 2 different versions, one basic algorithm going for minimum code size, but I quickly realized the score is vastly affected by those big denominators (based on the examples in the PDF file), so I set out to code an algorithm that tries to minimize those denominators.

For the most part it succeeds: produces longer lists (more fractions) but with smaller magnitude denominators, always keeping the error within 1e-11 so it doesn't impact the score much.

My code size quadrupled, and for some numbers it became a lot less efficient. For example, my new algorithm produces { 3 6 10 } for 0.6 instead of { 2 10 } which is clearly a better choice. I started coding a "finishing" routine that would take the list and simplify '1/A+1/B=1/C'. In other words, to optimize the list by eliminating those additional fractions (1/3+1/6 = 1/2).

While I worked on it, I quickly realized it wasn't worth it at all because '1/A+1/B=1/C' is very rare on large denominators, and optimizing the small numbers didn't matter much to the final score, as the sum of all denominators was a large number. That line of work was abandoned.

Then I turned to another idea: truncate the lists whenever large denominators appeared. Turns out that very small errors become very large denominators (1E-10 = 1/1E10), so dropping large denominators would only produce small errors, reducing the score on one side, slightly increasing the error term in the score, but overall I expected a score decrease. But my second algorithm was already reducing the magnitude of those denominators, therefore the errors were too large and were impacting the score. The dropping technique could still be applied to the simpler algorithm, though I didn't do it as I was focusing on the better algorithm. In the end I'm going with the raw algorithm, which gives unoptimized lists of fractions, with smaller denominators but more fractions.

We'll see how it scores...