HHC 2017 RPL Programming contest information and results thread

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