HHC 2017 RPL Programming contest information and results thread

[Gene]

Hello all. The PDF of the programming contest is attached below.

Please work on this problem and do not post RESULTS of your work until after 6pm Nashville CDT on Sunday.

Questions here are fine, but please try not to give away how you are approaching the problem with your question. Ask carefully.

I hope you enjoy the problem. Happy programming!

[Paul Dale]

Does this entry break the contest:

Code:

<< { } >>

Pauli

[Jim Horn]

Sorry but I've got to ask - who thought up these two problems? I have strong suspicions due to their subject matter and descriptions...

Best to all at HHC2017!

[brouhaha]

My entry is currently 83.5 bytes, but even after hours of hacking away at it, I have little confidence that it's going to do really well in the scoring on the actual test data.

IMO, the tradeoff between the maximum magnitude of denominator and the error makes this problem really interesting.

[Claudio L.]

I have a question on the scoring. When it talks about using the examples to compute the score, will the score be calculated based solely on the numbers 0.6,0.99 and 0.71828 mentioned? or will there be other numbers?
I'm asking because I have my algorithm working fine, but I want to compute my own score in order to optimize it.

[Gene]

Here at the conference, I will be using some sample problems that will not be revealed until after the contest is over.

In the "real world" (tm) you do your best and then face the unknown. Same with the programming contest. Big :-)

[3298]

Is SysRPL allowed? If so, I'm currently at 75.5 bytes.
The rules are a bit vague on this point ... the relevant one would be: "The program must be keyable on a clear machine." SysRPL without Extable is quite possible (attach L256 and L257), it's just not very pretty. ( :: PTR 071A2 PTR 03E0E PTR 35B96 ; instead of :: BEGIN #1- #0=UNTIL ; )
Also, can we actually submit programs somehow without being in Nashville?

[Gene]

Hello all! Conference is going great! Wish you were here. :-)

No System RPL please. I know it **could** be done, but let's stay with user code.

[Claudio L.]

(09-16-2017 01:56 PM)Gene Wrote:  Here at the conference, I will be using some sample problems that will not be revealed until after the contest is over.

In the "real world" (tm) you do your best and then face the unknown. Same with the programming contest. Big :-)

Fair enough. For now I used those 3 values only, and was able to reduce the score by a factor of 10. I'll just have to wait for your sample data to compute an official score tomorrow.

[pdo]

(09-16-2017 06:51 PM)Claudio L. Wrote:  

(09-16-2017 01:56 PM)Gene Wrote:  Here at the conference, I will be using some sample problems that will not be revealed until after the contest is over.

In the "real world" (tm) you do your best and then face the unknown. Same with the programming contest. Big :-)

Fair enough. For now I used those 3 values only, and was able to reduce the score by a factor of 10. I'll just have to wait for your sample data to compute an official score tomorrow.

I expect Gene has some sneaky numbers ready for the final scoring. My own effort is currently at a whopping 207 bytes on a 48GX, but hopefully that can be reduced...

Paul

[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...

[Arno K]

My first attempt was some kind of brute force, way too slow. So I took a thought on the Problem and the result was an algorithm basing on X-(CEIL(X)) which produces reliable results, not directly the ones provided in the examples but we will see.
Arno

[pdo]

My approach is also quite simple, computing the smallest possible denominator at each step and truncating the sequence when the denominators would contribute more to the score than the resulting error. One thing I did find though, was that I could reduce the size of the last denominator in the last two supplied examples without incurring any error penalty, so I incorporated that into my program.

I'll post the program if anyone is interested and it's deemed okay to do that now.

Paul

[David Hayden]

I didn't enter the contest but started looking at it last night. The scores of the entries received differed enormously which led me to ask "when should you stop adding denominators?"

Suppose you have a program of b bytes that generates a score of S. Will adding new denominator d to one of the answers increase or decrease your score. If my math is right, the new denominator will decrease your score if d^2 < 10^9/b. For an 80 byte program that's 3535.

So although the directions say that you should match the input decimal as closely as you can, the scoring favors fewer terms over higher accuracy.

[Gene]

The difference in the scores and the questions that David raises are sadly due to the scoring scheme I put into place.

I would revise that scoring scheme now if I could.

My goals were:

1) Get a "correct" answer - preferably within 1 digit in the least significant location entered.

2) Get as low a series of denominators as possible - no one wants to do 1/123509813459807 if possible.

3) Have a program that is as small as possible.


Those are hard to do without being in conflict, so that's why I tried the scheme in the contest... it was the third I had typed up. Not sure how to reward the programs given those criteria...

[DavidM]

(09-18-2017 04:52 PM)Gene Wrote:  My goals were:

1) Get a "correct" answer - preferably within 1 digit in the least significant location entered.

2) Get as low a series of denominators as possible - no one wants to do 1/123509813459807 if possible.

3) Have a program that is as small as possible.

Those are hard to do without being in conflict, so that's why I tried the scheme in the contest... it was the third I had typed up. Not sure how to reward the programs given those criteria...

How would you have amended the scoring? While the specific weighting of factors may be debatable, I think you did a good job of modeling your goals. I was quite pleased to see a contest that didn't focus solely on program size as The Most Important Thing. You came up with a suitable problem that has multiple "correct" approaches, with some having a higher quality result than others. That, by itself, must have required some effort on your part.

I got as far as the simple version that I assume most participants got to initially, but hit a brick wall when trying to find the "secret sauce" for how to manipulate the terms to minimize the list (#2 in your list above, which for me was the most interesting part of the challenge).

That there is a wide range of scores for the participants is a good thing in my mind, as it implies that there isn't a single clever approach to the problem that was found by some subset of the participants. I would find that kind of outcome far less satisfying.

[pdo]

(09-18-2017 01:54 PM)David Hayden Wrote:  If my math is right, the new denominator will decrease your score if d^2 < 10^9/b.

I fear I may have misread something then as my break-even point was d^2 < 10^21/b, a factor of 10^12 difference allowing another 6 digits in the denominators.

Confused,
Paul

[Claudio L.]

(09-18-2017 05:31 PM)DavidM Wrote:  How would you have amended the scoring? While the specific weighting of factors may be debatable, I think you did a good job of modeling your goals. I was quite pleased to see a contest that didn't focus solely on program size as The Most Important Thing. You came up with a suitable problem that has multiple "correct" approaches, with some having a higher quality result than others. That, by itself, must have required some effort on your part.

I agree 100%. How the score is weighted doesn't matter, the fact it made us think about a different approach to try to minimize those denominators without increasing error made it a more open contest. As a matter of fact, through all these years I never attempted to solve any of the HHC contests, but this one caught my attention *because* of the weird scoring and the balance of error vs size of denominators vs size of code that was needed to make it work well.

[Claudio L.]

(09-18-2017 01:54 PM)David Hayden Wrote:  So although the directions say that you should match the input decimal as closely as you can, the scoring favors fewer terms over higher accuracy.

Yes and no. I actually came up with an algorithm that minimizes the denominators but still guarantees 1e-12 accuracy to avoid all penalty from error. Once I got to that point, my "pseudo-score" (using 0.6,0.99 and 0.71828 only) dropped from 6900 to 519. With that score, even a small 1e-11 error added 100 points, ruining my efforts.
I'd like to see how it all plays out with Gene's pool of numbers, but I found the weights to be quite balanced once you reach a certain level of optimization.

[3298]

My approach was mostly based on program size, I pulled out all tricks I could to cut the size down. Fortunately the score says nothing about speed, so I was free to do some questionable stunts with numbers that are smaller than just writing out the number itself. The actual algorithm was pretty simple, just pick the smallest number whose reciprocal is smaller than the given number (that's two commands: INV CEIL), add it to the list, and repeat with the input number minus the reciprocal mentioned.
I start by pushing an empty list onto the stack (oh, how much I wish the UserRPL compiler would detect this and compile it to the SysRPL command NULL{} which only takes 2.5 bytes instead of 5 ... oh well), then there's the loop which shuffles the list, the input number, and its temporary data on the stack as needed, and if the exit condition is satisfied (the input number has shrunk below a threshold) a small number of cleanup commands prepare the stack in the way the challenge tells us to. I've lined up the loop's commands such that what remains of the input number is on level 1, ready to be scaled up by 1.E12 (because what's left is by definition the error). After that, SWAP and done. Not a lot left to optimize, so the loop is the main target for optimization.

First discovery: due to my SysRPL attempts, I had the SysRPL stack display on, even during the UserRPL attempts. Knowing that some numbers are stored in ROM which can make code smaller (referencing them takes just the 2.5 bytes of a command instead of the length of the actual object, i.e. 2.5 bytes prolog + several bytes of data: 8 bytes for a real number), I was disappointed by UserRPL's lack of control on how my numbers are stored. However, the SysRPL stack display causes everything to be decompiled to SysRPL code which does have this level of control, so I see what the UserRPL compiler has done. For example, there is %12 which is a pointer to the real number 12 in ROM, and there's % 12 (pay attention to the space) which is the real number 12 embedded in the program. Long story short, this showed me that the UserRPL compiler compiles whole numbers from -9 to +9 (inclusive) as pointers into ROM.
That's not a whole lot of numbers, but in those cases, a lot of space is saved. What's more, with the right commands we can generate other numbers from these, and as long as we use four or less commands (including the pointer to the number in ROM) there's still some space saved. (Four commands = 10 bytes, a real = 10.5 bytes.)
In my program I focused on ALOG and SQ to get other numbers from these single-digit whole numbers. For example, the number we are supposed to return on level 2 can be up-scaled this way:

Code:

1.E12 * (13 bytes)

or this way:

Code:

6. ALOG SQ * (10 bytes)

Do I need to tell you which one I ultimately used?
(The ALOG command turns the 6 into 1.E6, the SQ doubles the exponent to 12.)

Second discovery: as others have already noted, very big denominators affect the score greatly. Because the score for a single number is mostly affected by the largest denominator or the error, I tried to find a balance between these. The other denominators can be mostly ignored.
My loop has a very simple knob to tune this balance: the threshold at which I leave a number on the stack as error. For example, the number 1.E-10 would correspond to an error of 100 (i.e. score increased by 10000), or to a denominator of 1.E10 (i.e. score increased by 1000*bytes; assuming a program size of about 80 bytes that's roughly 80000). These calculations show that 1.E10 is clearly on the "leave as error" side of the threshold. 1.E-9 is on the other side (counts for 100000 as error, or 100*bytes=~8000 as denominator), so the ideal threshold is somewhere between those. (It's somewhere between 2.E10 and 3.E10, actually.) However, 1.E-9 and 1.E-10 take less bytes to generate (see above) than any number inbetween (5 bytes for 1.E-9: -9. ALOG, 7.5 bytes for 1.E-10: -5. ALOG SQ), so I put one of those in for size reasons. I chose 1.E-10, because it's closer to the ideal threshold, and because it has a better worst-case score, despite the 2.5 additional bytes it takes over 1.E-9. Using < vs <= or > vs >= there's still the possibility to include or exclude the number itself, in case an evil judge throws that number at the program. My random number tests have had trouble generating denominators in that range, so if the test numbers are nice, this is a place where a further size improvement can be made.

Early versions of my program used a DO...UNTIL loop, but the weakness of this was that it obviously couldn't exit before shoving at least one denominator into the list. This is only important when someone throws very small numbers at the program, which a random number test is extremely unlikely to do, but a judge could possibly try it.
Therefore I used WHILE...REPEAT as another "evil judge" protection, even though it's longer by 5 bytes (SysRPL knowledge tells me why: just like SysRPL's WHILE command, ending the loop makes skipping over the remaining portion of the loop necessary; this is done via the SysRPL command 2SKIP, so this remaining portion has to be wrapped in :: ; to count as one piece, with the END (UserRPL) or REPEAT (SysRPL) being the other skipped piece). Again, if the numbers are nice, this is another place where the size can be reduced (just remember to reverse the condition, because WHILE exits when the test fails, and UNTIL exits when the test succeeds).

What's that, you want the code already? Fine, here it is (77.5 bytes, #AF9F):

Code:

<< { }
  WHILE SWAP DUP -5. ALOG SQ >
  REPEAT DUP INV CEIL DUP UNROT INV - UNROT +
  END 6. ALOG SQ * SWAP
>>

As a bonus, here's a SysRPL version. I used a meta instead of a list for a change, but the list equivalent has exactly the same size and results. Subject to the same "evil judge" measures as the UserRPL version. 62.5 bytes, #4935:

Code:

::
  ZEROSWAP BEGIN
    DUP %10 %CHS %ALOG %>
  WHILE ::
    DUP %1/ %CEIL
    DUP4UNROLL ROT#1+UNROT
    %1/ %-
  ; REPEAT
  %12 %ALOG %* OVER#2+UNROL P{}N
;

I'm interested in comparing this to Claudio's sophisticated optimization on the actual test numbers...