HHC 2017 RPL Programming contest information and results thread

[Claudio L.]

(09-18-2017 07:44 PM)pdo Wrote:  

(09-18-2017 06:34 PM)Claudio L. Wrote:  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.

Now this sounds really interesting! I'd love to hear more details.

Paul

Nothing fancy, really.
The basic algorithm takes each denominator as A=CEIL(1/x) as others mentioned. This is the closest 1/A fraction to x, which leaves the smallest residual x'=x-1/A for the next step. The next step does the same on this small number B=CEIL(1/x') , therefore giving you a large denominator, but optimal convergence.
My algorithm tries to work with 2 steps at once:
x=1/A+1/B

The idea is to choose a pair of A and B that minimizes A+B.

A=CEIL(1/x) is the smallest number for A.
B=CEIL(1/x') is the largest possible B.

So the algorithm loops from A to (A+B)/2, computing a B' for each A', and chooses the A that minimizes A+B. Doesn't choose B, as that's for the next iteration.

Of course, for large numbers this became ridiculously slow, so I decided to skip values, so it doesn't find the best A and B combination, just something better.

It does stop early if:
x<1e-12, if A-1/x is <1e-12.

I'll post the code later, as I need my desktop to get it from the calc, also it's newRPL so uses LSTO, I need to modify it for classic userRPL but no big deal.

On Gene's list it produced the following results:

0.4488:
{ 4 9 21 55 88 186 399 687 1592 1793 3249804 } with error*1e12 = 0.025
Sum = 3254638, it clearly messed up in that case, as it did worse than the basic algo.

0.422618262:
{ 4 10 26 54 140 216 472 1108 1185 1503201 } with error*1e12=0.28
Sum = 1506416, now it starts to shine! compare with the last term of the classic algorithm

0.41421356:
{ 5 9 19 38 81 177 327 681 1161 1296 4549516 } with error*1e12=0.033
Sum = 4553310

0.853:
{ 2 5 12 28 58 129 211 3384 633 825 1797 1737 7658074 } with error*1e12=0.011
Sum = 7666895

0.5:
{ 2} with error 0

Total code size is 604 bytes on newRPL (should be around 450 bytes on classicRPL but let's ignore that for now and use 604 bytes).
The total sum of the denominators for all 5 numbers is 16981261

16981261/1e7*604 = 1025.7, so that's the first term of the score.

the sum of error*1e12 multiplied by 100 only adds 35 points to the score.

Final score: 1061

I'll try to post the code tonight if possible.

Here's the code:

Code:


(newRPL original version)
«
  { } 0 → 
    X DEN BSTA « X WHILE
    X 1E-11
    ≥ REPEAT
      X INV CEIL DUP INV
      NEG X + IF DUP 1E-11
      < THEN
        DROP 'DEN' SWAP
        SADD 0 'X' STO
      ELSE
        IF OVER 1000
        ≥ THEN
          SWAP 'DEN' SWAP
          SADD 'X' STO
        ELSE
          INV FLOOR DUP2
          + 'MN' LSTO
          MN 1000 /
          CEIL 'STP' LSTO
          OVER 'BSTA'
          STO OVER + 2
          / IP FOR 'A'
            X A INV -
            DUP IF ABS
            1E-11
            ≤ THEN
              A 'BSTA' STO
              0 'MN' STO
              DROP 
            ELSE
              INV CEIL
              IF A + DUP
              MN < THEN
                'MN' STO
                A 'BSTA' STO
              ELSE
                DROP 
              END
            END
            STP 
          STEP
          'DEN' BSTA SADD
          'X' BSTA INV
          STO- 
        END
      END
    END
    DEN INV ΣLIST - 1E12
    * ABS DEN 
  »
»

Code:


(userRPL compatible version -- UNTESTED -- I hope it works)
«
  { } 0 0 1 → 
    X DEN BSTA MN STP « X WHILE
    X 1E-11
    ≥ REPEAT
      X INV CEIL DUP INV
      NEG X + IF DUP 1E-11
      < THEN
        DROP 'DEN' SWAP
        STO+ 0 'X' STO
      ELSE
        IF OVER 1000
        ≥ THEN
          SWAP 'DEN' SWAP
          STO+ 'X' STO
        ELSE
          INV FLOOR DUP2
          + 'MN' STO
          MN 1000 /
          CEIL 'STP' STO
          OVER 'BSTA'
          STO OVER + 2
          / IP FOR A
            X A INV -
            DUP IF ABS
            1E-11
            ≤ THEN
              A 'BSTA' STO
              0 'MN' STO
              DROP 
            ELSE
              INV CEIL
              IF A + DUP MN < THEN
                'MN' STO
                A 'BSTA' STO
              ELSE
                DROP 
              END
            END
            STP 
          STEP
          'DEN' BSTA STO+
          'X' BSTA INV
          STO- 
        END
      END
    END
    DEN INV 0. + ΣLIST - 1E12
    * ABS DEN 
  »
»