HHC 2017 RPL Programming contest information and results thread

[Arno K]

mine is a little bit longer, I forgot about that alog trick, the loop is nearly the same.
Arno
P.S I have not forgotten everything in that about 10 years of absense from RPL.
Still refreshing.

[pdo]

(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

[Gene]

First, here's a website about Egyptian Fractions that I think is great! Link

--------------------------------------------------------------------------------------------
The way the contests work at a real HHC gathering goes something like this.

1) We announce that program submissions (a physical machine with the program in it already AND a printed/hand written listing of the program AND the author's name on the machine and listing) are due to the judge at say Noon.

2) Noon happens to be when we break for lunch.

3) So as we break for lunch, those entering the contest are fighting their way to the judge who has to be careful to keep the machines safe (I dropped a 41C two years ago and broke it - ugh - didn't enjoy getting that fixed).

4) The judge tries to go get some lunch and then runs the inputs to the RPL and RPN contests on the machines and tries to record results / score them.

5) This is often a slow process since people want to be friendly and are curious. Personally, I don't like to hide, but I probably should.

6) The contest results are usually determined in an hour or so and then announced around 3pm. The results are kept secret until then.

7) Winner of each contest gets to pick a prize from the prize table AFTER the Best Speaker picks one but before all the other attendees will pick one.

8) The judge then starts trying to think of a contest for next year!

--------------------------------------------------------------------------------------------
Well, I hope everyone is not too disappointed, but here are the five numbers I used as test inputs. None of them are aimed at "boundary" conditions, but were trying to be a fairly reasonable input.


As to what scoring adjustment I would consider changing? I would have put more penalty on error. As it is, shortcuts to leave errors are not as penalizing as I would probably think they should have been. Oh well.


Number 1: 0.4488 (this is a 48 inside another 48)
Factors returned by the five submissions: 3+9+230+129375

Number 2: 0.422618262 (this is the sine of 25 degrees - a number I use in displays for photographs.
Factors returned: (1) 3+12+169+29040+3236245955 (2) 3+12+169+20940 (3) 3+12+169+29040+3239579892

Number 3: 0.41421356 (this is the square root of 2 minus 1)
Factors returned: (1) 3+13+253+218314+62500000000 (2) 3+13+253+218314+63850599813

Number 4: 0.853 (why not?)
Factors Returned: (1) 2+3+51+17000+1000000000000 (2) 2+3+51+17000

Number 5: 0.5 (this is to see if program works with one term!)
Factors returned: (1) 2 and (2) One program failed

[pier4r]

Gene thanks for sharing the link. I still have to attempt this problem 8regardelss of the score, the problem itself is interesting).

Just to add some info. Years ago (I was 16 I think. Man I am old), I read "history of mathematics" of C. B. Boyer, that had a nice chapter about Egyptian fractions. Only, I did not see the problem posed in those terms, it is pretty interesting!

edit: randomly browsing hpcalc.org http://www.hpcalc.org/details/3163

what nice site! And nice that the community contributed to it!

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

[Claudio L.]

And here are the scores for my more basic code:

0.4488:
{3 9 230 129375 } error=0

0.422618262:
{ 3 12 169 29040 3243470446 } error*1e12=7.8e-8

0.41421356:
{ 3 13 253 218314 65143073093 } error*1e12=1.9e-10

0.853:
{ 2 3 51 17000 } error=0

0.5:
{ 2 } error=0

Size in bytes (newRPL): 176 bytes.

First term= 68386938021/1e7*176 =1203610

Error term *100 = 0

Notice the errors are smaller because of the 32-digit default precision in newRPL, which makes it pick the last number much more accurately, the classicRPL version should return numbers more in line with what Gene reported.

Final score: 1203610, this is more than the score from my other algorithm squared!

All in all, I liked the challenge, this was fun.

Here's my code for this one (not optimized, as I moved on to the other algorithm):

Code:


(original newRPL code)
«
  0 'K' LSTO DUP WHILE
  DUP 1E-12
  ≥ REPEAT
    DUP INV DUP IP DUP
    UNROT ≠ + DUP UNROT
    INV - 'K' INCR DROP
  END
  DROP K →LIST DUP INV
  ΣLIST ROT - 1E12
  * SWAP 
»

Code:


(userRPL code)
«
  0 → K « DUP WHILE
  DUP 1E-12
  ≥ REPEAT
    DUP INV DUP IP DUP
    UNROT ≠ + DUP UNROT
    INV - 'K' INCR DROP
  END
  DROP K →LIST DUP INV
  ΣLIST ROT - 1E12
  * SWAP 
  »
»

[pdo]

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

Nice! That's a really clever idea. I'll have to play around with that myself too.

Paul

[DavidM]

(09-18-2017 07:58 PM)Gene Wrote:  As to what scoring adjustment I would consider changing? I would have put more penalty on error. As it is, shortcuts to leave errors are not as penalizing as I would probably think they should have been. Oh well.

That makes sense, given your stated objectives. I was afraid you were thinking that the scoring should have been simplified to only code size, which I believe would have made this contest a lot less interesting.

Thanks for putting the extra effort into coming up with great contests, Gene! And I hope the changes in format this year were welcomed by all -- it seems like giving folks more time to work on them made it better for the attendees.

[Claudio L.]

(09-18-2017 09:34 PM)pdo Wrote:  Nice! That's a really clever idea. I'll have to play around with that myself too.

Paul

Actually, the idea came from Gene himself. On page 2 of the PDF, he shows different fractions for 8/11, and I saw the huge difference in terms of score between the one that ends in 1/37+1/4070 and the last one that has 1/70+1/77.
Both sums of fractions give 3/110, so they are numerically equivalent, but the sum of the denominators isn't (and it kills the score!).
So I set to code an algorithm to search for these better pairs of numbers, as I thought that was the true nature of the problem.
I didn't quite achieve it, as my algorithm soon degenerated in the abomination I posted, but the resulting code can drastically reduce the score (even if the resulting lists are not exactly desirable).

[Edwin]

I have four different versions:
code 1

Code:


Bytes: 68
Checksum: # 3988h
<< { } SWAP
  DO DUP INV CEIL ROT OVER + UNROT INV -
  UNTIL DUP NOT
  END 1.E12 * SWAP
>>

results:
a) 0.4488
2: 0.
1: { 3. 9. 230. 129375. 2.26772796335E12 -1.E24 }

b) 0.422618262
2: 0.
1: { 3. 12. 169. 29040. 3239579892. 1.44927536232E19 1.E31 }

c) 0.41421356
2: 0.
1: { 3. 13. 253. 218314. 63850599813. 1.E22 }

d) 0.853
2: 0.
1: { 2. 3. 51. 17000. 3.46981263012E12 }

e) 0.5
2: 0.
1: { 2. }

code 2

Code:


Bytes: 78.5
Checksum: # A77Bh
<< { } SWAP
  DO DUP INV CEIL ROT OVER + UNROT INV -
  UNTIL DUP .000000000001 <
  END 1.E12 * SWAP
>>

results:
a) 0.4488
2: 0.44097
1: { 3. 9. 230. 129375. }

b) 0.422618262
2: 0.000000069
1: { 3. 12. 169. 29040. 3239579892. }

c) 0.41421356
2: 0.0000000001
1: { 3. 13. 253. 218314. 63850599813. }

d) 0.853
2: 0.2882
1: { 2. 3. 51. 17000. }

e) 0.5
2: 0.
1: { 2. }

code 3

Code:


Bytes: 83
Checksum: # 33D1h
<< { } 0
  DO PICK3 OVER - INV CEIL ROT OVER + UNROT INV +
  UNTIL PICK3 OVER - NOT
  END ROT - 1.E12 * SWAP
>>

results:
a) 0.4488
2: 0.
1: { 3. 9. 230. 129375. }

b) 0.422618262
2: 0.
1: { 3. 12. 169. 29040. 3236245955. }

c) 0.41421356
2: 0.
1: { 3. 13. 253. 218314. 62500000000. }

d) 0.853
2: 0.
1: { 2. 3. 51. 17000. 1.E12 }

e) 0.5
2: 0.
1: { 2. }

code 4

Code:


Bytes: 83
Checksum: # 2C2Eh
<< { } SWAP 0
  DO DUP2 - INV CEIL 4 ROLL OVER + 4 ROLLD INV +
  UNTIL DUP2 - NOT
  END - 1.E12 * SWAP
>>

results:
a) 0.4488
2: 0.
1: { 3. 9. 230. 129375. }

b) 0.422618262
2: 0.
1: { 3. 12. 169. 29040. 3236245955. }

c) 0.41421356
2: 0.
1: { 3. 13. 253. 218314. 62500000000. }

d) 0.853
2: 0.
1: { 2. 3. 51. 17000. 1.E12 }

e) 0.5
2: 0.
1: { 2. }

[Claudio L.]

(09-18-2017 07:58 PM)Gene Wrote:  Well, I hope everyone is not too disappointed...

Not at all, I think the scoring idea was brilliant. Based only on speed or only on code size makes everybody focus on the same thing, while mixing several variables like you did really made the problem so much more interesting to work on.
Low denominators is only the first step to get a decent score, that's done and from now on your error penalty becomes huge. Code size is also a much bigger factor now that denominators/1e7 is a small number.
I personally think you did a great job on this contest. I predict that during this week, several other people will come up with new and much better algorithms than mine, there's a lot of room for improvement yet, all thanks to your scoring system.
Perhaps during the conference people didn't have time to dig deep enough into the problem, but in this forum this is not over...

[Paul Dale]

(09-18-2017 07:58 PM)Gene Wrote:  As to what scoring adjustment I would consider changing? I would have put more penalty on error. As it is, shortcuts to leave errors are not as penalizing as I would probably think they should have been. Oh well.

This is what prompted my tongue in cheek null program suggestion. At 100 points maximum for each error, returning no denominators and making the size * denominator component zero seemed ideal.

That program would have scored 263.86.

The equivalent that does return a result << 1 SWAP - { 1 } >> would add about 25 per example to the score. It still wouldn't have passed the judges discretion clause


Pauli

[Gene]

(09-18-2017 11:21 PM)Paul Dale Wrote:  It still wouldn't have passed the judges discretion clause

Pauli

Gene: You are quite correct! :-) However, please continue to be creative.

[3298]

Oookay, I posted my code, now I have the official numbers to test on.
UserRPL score: 26748.8744054
SysRPL score: 21888.9128444
What they returned:
- Number 1: 3+9+230+129375, like all Nashville contestants.
- Number 2: 3+12+169+29040+3239579892, result (3) in Gene's list.
- Number 3: 3+13+253+218314, the point where my exit condition trickery avoided a big denominator compared to both Nashville results.
- Number 4: 2+3+51+17000, result (2).
- Number 5: 2, no failure.
It was obvious that the SysRPL version would be better than the UserRPL one, because it produces the exact same results in a smaller program. Though I don't know the size of the Nashville submissions, I doubt they were small enough to make up for what I won at number 3 by dropping their last denominator.

But I'll look further and test whether the "evil judge protections" () were really needed...
- The version I presented used an exit condition of <=1.E10. If I used <1.E9 instead to save 2.5 bytes (applies to both languages), I would have lost some points on number 2 by hitting result (2) instead (assuming 20940 is a typo for 29040). It substitutes 323.9579892*bytes (25106.744163 for UserRPL, 20247.374325 for SysRPL) in score for 30868.1999931 points (according to my 50G) for the increased error. That hurts, so this has to stay.
- The other protection was designed to handle tiny inputs below the exit threshold by not entering the loop at all. There were no inputs like that, so this can go, saving 2.5 bytes on the UserRPL version and 5 bytes on the SysRPL version by exchanging the WHILE loop for an UNTIL loop, which removes the :: ; (= 5 bytes) around the part of the loop that actually adds the denominators to the list. Unfortunately the UserRPL has a SWAP at the start of the exit condition checking code that has to be run on entry, so that needs to be added between the empty list and the start of the loop, so the savings are only 2.5 bytes in that case. The scores would be 25938.8808119 and 19458.9320639.

I also tried Claudio's fancy optimizing program on the stock firmware. It's definitely slow, but hey, speed is not rated. It also needed a small fix to be accepted by the compiler (remove the tick marks from FOR 'A'). These are the results:
- Number 1: 4+9+21+55+88+186+399+687+1592+1793+3249802
- Number 2: 4+10+25+61+128+231+840+722+1229+1441+6055831
- Number 3: 5+9+19+38+81+177+327+681+1161+1296+4549514
- Number 4: 2+5+12+27+58+341+161+316+655+2871+9574+3583+1218+2700367
- Number 5: fails on ΣLIST. It's an easy fix, though - just write 0. + ΣLIST, then it works and returns 2.
The score is impressive: 1300.2357774 for the original version (603 bytes on stock firmware), or 1308.5296064 for the number-5-fixed version (the errors count for 300 in both cases). I think we have a winner - though there's some optimization potential left in the program size. For instance, reducing the variable names down to one character would save quite a few bytes here and there, since the UserRPL compiler does no NULLLAM conversion.

(09-18-2017 11:21 PM)Paul Dale Wrote:  At 100 points maximum for each error

Wouldn't that be 100 * 1.E12 due to the scaling applied to the returned error? That clearly makes the simple no-denominators program the worst possible one.

[Gene]

Winning Nashville RPL routine (code will have to come later) was 71.5 bytes in size.

[Paul Dale]

(09-19-2017 12:11 AM)3298 Wrote:  Wouldn't that be 100 * 1.E12 due to the scaling applied to the returned error? That clearly makes the simple no-denominators program the worst possible one.

The input numbers are in the range zero through one. Returning a constant in this range means a maximum error of 1. This is multiplied by 100. Returning 0.5 would be better and would even have got one of the test cases correct.


Pauli

[Claudio L.]

(09-19-2017 01:50 AM)Paul Dale Wrote:  

(09-19-2017 12:11 AM)3298 Wrote:  Wouldn't that be 100 * 1.E12 due to the scaling applied to the returned error? That clearly makes the simple no-denominators program the worst possible one.

The input numbers are in the range zero through one. Returning a constant in this range means a maximum error of 1. This is multiplied by 100. Returning 0.5 would be better and would even have got one of the test cases correct.


Pauli

3298 is correct here. The rules say 100 times the error value returned to the stack. That value is the actual error * 1E12, so an error of 1 would result in a score of 1E14.

Sorry to pop your bubble. Gene rules have no easy loopholes :-)

[Claudio L.]

(09-19-2017 12:11 AM)3298 Wrote:  It also needed a small fix to be accepted by the compiler (remove the tick marks from FOR 'A'). - Number 5: fails on ΣLIST. It's an easy fix, though - just write 0. + ΣLIST, then it works and returns 2.

Sorry, when I manually "patched" the code for classic userRPL I forgot that FOR cannot use ticks (in newRPL this doesn't matter), and that ΣLIST cannot deal with single-element lists. But I'm glad you got it working! I'll edit the post so other people can use it.

[Paul Dale]

How'd I miss that factor

Pauli

[Claudio L.]

(09-19-2017 12:11 AM)3298 Wrote:  The score is impressive: 1300.2357774 for the original version (603 bytes on stock firmware), or 1308.5296064 for the number-5-fixed version (the errors count for 300 in both cases). I think we have a winner - though there's some optimization potential left in the program size. For instance, reducing the variable names down to one character would save quite a few bytes here and there, since the UserRPL compiler does no NULLLAM conversion.

No winner. Compared to your code, mine only beat it at one fraction. The magnitude of that single denominator threw you off. I think the winner would combine both routines, run both algorithms, and choose the list that minimizes the sum of denominators.
Code size would be bigger, but the magnitude of the denominators would shrink, since my code is not very good on 3 of the solutions. I think that would lower the score.