HHC 2016 RPN contest is now live
09-17-2016, 01:36 PM
Post: #1
 Gene Senior Member Posts: 528 Joined: Dec 2013
HHC 2016 RPN contest is now live
HHC 2016 RPN contest PDF

09-17-2016, 03:57 PM
Post: #2
 Werner Member Posts: 180 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
Gene,
while the description explicitly states that we may assume 1 <= k <= 9 and 1 <= n <= 100, 2 of the 5 test cases use degenerate input (k=12 and n=0). So, do we have to test for these or not?

Cheers, Werner
09-17-2016, 04:03 PM
Post: #3
 Gene Senior Member Posts: 528 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
You can assume inputs between 1 <= n <= 9 and 1 <= k <= 100 (81 of course).

:-)
09-18-2016, 12:44 AM
Post: #4
 Paul Dale Senior Member Posts: 1,003 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
Some clarifications please: The contest says minimum bytes or steps with registers counting for 8 bytes. On the 34S a step occupies two bytes and register is equivalent to 4 steps. Is the intention to count registers as eight steps (i.e. double their worth)?

Do the lettered registers count as used registers? They cannot be converted into program steps.
Likewise, does the stack count towards register use?

What about the statistical accumulations? These do eat into program space and occupy 140 bytes on the first sigma+.

Pauli

There are exceptions to the two byte instruction length but these won't be used here. Also, double precision registers are twice the size but again won't be used.
09-18-2016, 01:06 AM
Post: #5
 Gene Senior Member Posts: 528 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
My intent was simply to penalize using "memories" of any kind of register usage.

Solution A is 80 bytes and uses no registers.

Solution B is 80 bytes but uses 30 memories.

Solution A wins.

Using the statistics registers is a good example. It should require a +140 to the byte count.

Here on the museum, the community will ultimately decide (as it should) the best solution. :-)

Here at HHC, I will do the best I can in the hour I'll have to judge every solution to this and the RPL contest. I don't ever have much time for lunch on Sundays at the conferences. :-)
09-18-2016, 04:42 AM (This post was last modified: 09-19-2016 12:26 PM by Paul Dale.)
Post: #6
 Paul Dale Senior Member Posts: 1,003 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
I've got a solution in 32 steps and four registers that runs essentially instantly for any inputs.

I'm sure it can be significantly improved -- it is taking a fairly naïve approach to the problem.

Pauli
09-18-2016, 05:30 AM
Post: #7
 Gerson W. Barbosa Senior Member Posts: 690 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
(09-18-2016 04:42 AM)Paul Dale Wrote:  I've got a solution in 32 steps and four registers that runs essentially instantly for any inputs.

{ { 2, 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 } { 3, 1 3 6 10 15 21 28 36 45 54 61 66 69 70 69 66 61 54 } { 4, 1 4 10 20 35 56 84 120 165 219 279 342 405 465 519 564 597 615 } { 5, 1 5 15 35 70 126 210 330 495 714 992 1330 1725 2170 2654 3162 3675 4170 } { 6, 1 6 21 56 126 252 462 792 1287 2001 2992 4317 6027 8162 10746 13782 17247 21087 } { 7, 1 7 28 84 210 462 924 1716 3003 5004 7995 12306 18312 26418 37038 50568 67353 87648 } { 8, 1 8 36 120 330 792 1716 3432 6435 11439 19433 31732 50016 76350 113178 163284 229713 315645 } { 9, 1 9 45 165 495 1287 3003 6435 12870 24309 43741 75465 125445 201675 314523 477015 705012 1017225 } }

Lists format:

{k, f(k,1) f(k,2) f(k,3) ... f(k,18)}

0,62 seconds on m48+ running on iPhone SE (all lists)

f(9,19) = 1435005 (0.3695 s on the real HP 50g)

If only my formula worked for n >= 20... the conversion to wp34s would be fairly easy.

Looking forward to your solutions... and formulas :-)

Gerson.
09-19-2016, 05:20 AM
Post: #8
 Paul Dale Senior Member Posts: 1,003 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
My algorithm calculates the number of numbers of the required length or shorter that digit sum to the correct amount and then subtracts the number of numbers of one less than the required length -- this was the quick way to handle leading zeros and still get a direct combinatorial solution.

I didn't figure out a combinatorial solution that dealt with leading zeros properly and I suspect I'm missing something really obvious. It wasn't a great weekend for me

Code:
    LBL B 01:        [cplx]STO J 02:        DEC Y 03:        XEQ a 04:        [cplx]x[<>] J 05:        XEQ a 06:        RCL- J 07:        RTN 08:    a::    [cplx]STO 00 09:        # 010 10:        / 11:        IP 12:        MIN 13:        0 14:        x[<>] Y 15:        [Sigma] 00 16:        RTN 17:        LBL 00 18:        (-1)[^x] 19:        RCL 01 20:        RCL Z 21:        COMB 22:        * 23:        RCL 00 24:        RCL+ 01 25:        # 010 26:        RCL* T 27:        - 28:        DEC X 29:        RCL 01 30:        DEC X 31:        COMB 32:        *     END

The END doesn't count (I hope), the initial LBL B can be omitted. Using the assembler, we can get relative subroutine calls which saves a step. Without this add LBL 01 between steps 7 and 8 and change the two BSR a to XEQ 01 and add one step. It uses four registers.

I suspect this can be further optimised, I really didn't spend a lot of time on this.

The program doesn't deal with out of range inputs since the clarification that they weren't allowed. It should scale up to larger input values too.

Pauli
09-19-2016, 11:09 AM
Post: #9
 Werner Member Posts: 180 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
No replies to this, so everyone is as stumped as I am? ;-)
I'm still trying to figure out your 'direct combinatorics'.
And I can see only one very small improvement, that even a WP34 beginner like me could spot: division by 10 (steps 8 and 9) is the same as SDR 001, no?

Cheers (meaning, in this case, 'bravo'),
Werner
09-19-2016, 11:42 AM
Post: #10
 Paul Dale Senior Member Posts: 1,003 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
(09-19-2016 11:09 AM)Werner Wrote:  And I can see only one very small improvement, that even a WP34 beginner like me could spot: division by 10 (steps 8 and 9) is the same as SDR 001, no?

One step saved

Pauli
09-19-2016, 11:44 AM
Post: #11
 Didier Lachieze Senior Member Posts: 679 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
I have a brute force solution in 27 steps and 2 local registers but I would like to understand the formulas used in Pauli's version as I can't compete on the execution time.

Code:
001 LocR 002 002 STO-.00  // n saved in R.00 003 x<>y 004 10^x 005 STO Y    //last value in Y 006 SDR 001  //start value in X 007 CLα 008 αIP X 009 #048 010 αLENG 011 * 012 ENTER 013 DROP 014 α->x 015 - 016 αLENG 017 x#0? 018 BACK 005 019 DROP 020 X=? .00 021 INC .01 022 DROP 023 INC X 024 x<? Y 025 BACK 018 026 RCL .01 027 RTN

After entering the program press [g] [RTN] to position the program pointer to step 001 and to clear the return stack, then enter k and n values and press R/S.
To compute new f(k,n) after the result of the previous run has been displayed, just enter the new values of k and n and press R/S again.
I don't check for k>9 or n>100.
09-19-2016, 12:09 PM (This post was last modified: 09-19-2016 12:27 PM by Paul Dale.)
Post: #12
 Paul Dale Senior Member Posts: 1,003 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live

We're looking for $$\sum_{i=1}^{k}x_i = n$$ where each $$x_i$$ is a single digit. Without the single digit restriction, there are $$\binom{n+k-1}{k-1}$$ possibilities (see e.g. here).

To enforce the must be a digit restriction use the inclusion-exclusion principle to remove the illegal cases with digits > 10 from the above result.

A bit of fiddling around gives: $$\sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k}{i} \binom{n+k-10i-1}{k-1}$$

However, this allows leading zeros, so we do the summation a second time for k-1 instead of k and subtract that from the first sum to get the result:

$$\sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k}{i} \binom{n+k-10i-1}{k-1} - \sum_{i=0}^{min(k-1, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k-1}{i} \binom{n+k-10i-2}{k-2}$$

I feel that there should be a more direct approach, but can't see it. My allergies have been dreadful for the last week and I'm not thinking even close to straight, so I could easily be completely wrong about all of this.

- Pauli
09-19-2016, 12:16 PM
Post: #13
 Paul Dale Senior Member Posts: 1,003 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
(09-19-2016 11:44 AM)Didier Lachieze Wrote:  I have a brute force solution in 27 steps and 2 local registers ...

Neat solution. I didn't even consider using the alpha register.

I did think about decomposing numbers into digits and building digits to form the number but neither worked out well. Alpha does this directly and superbly.

Pauli
09-19-2016, 01:47 PM (This post was last modified: 09-19-2016 01:52 PM by Gerson W. Barbosa.)
Post: #14
 Gerson W. Barbosa Senior Member Posts: 690 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
(09-19-2016 12:09 PM)Paul Dale Wrote:  $$\sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k}{i} \binom{n+k-10i-1}{k-1} - \sum_{i=0}^{min(k-1, \lfloor{\frac{n}{10}}\rfloor)} (-1)^i \binom{k-1}{i} \binom{n+k-10i-2}{k-2}$$

The most difficult part is deriving a working formula. Congratulations and thanks! Give me a formula and I'll move the world:-)

If n < 10, then a 7-step would do the job:

Code:
 001- LBL A 002-    + 003- DEC X 004- DEC X 005- RCL L 006- DEC X  007- COMB         END

Results start to be different when n > 9. I tabulated the first few differences for the case k = 6 and generalized the corresponding OEIS sequence for k, but this would work only for n up to 19. At this point I switched to the HP 50g for clarity:

Code:
 « → k n   « 'COMB(n+k-2,;k-1,)' EVAL n 9, >     IF     THEN 'COMB(n+k-12,;k-2,)*(k*(n-9,)-1,)/(k-1,)' -     END   » »

No further improvement from here, though.

(09-19-2016 12:09 PM)Paul Dale Wrote:  My allergies have been dreadful for the last week and I'm not thinking even close to straight, so I could easily be completely wrong about all of this.

I woke up late on Sunday and remained in bed for the next eight or ten hours. Low blood sugar level, I think, six months after the latest episode. But I wouldn't have been able to find a solution anyway, as I can't think of anything even today, when it's gone.
Hope you are better now.

Gerson.
09-19-2016, 09:19 PM
Post: #15
 Paul Dale Senior Member Posts: 1,003 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
Steps 13 and 14 in my original program are not required -- I forgot how the Sigma function takes it arguments Combine this with the earlier one step saving and my solution is down to 29 steps.

Pauli
09-20-2016, 06:41 AM
Post: #16
 Werner Member Posts: 180 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
(09-19-2016 01:47 PM)Gerson W. Barbosa Wrote:  If n < 10, then a 7-step would do the job:

You mean, five?

Code:
001- LBL A 002- DEC X 003- DEC Y 004  STO+ Y 005- COMB 006- END

;-)
Cheers, Werner
09-20-2016, 09:03 AM (This post was last modified: 09-20-2016 09:04 AM by Maximilian Hohmann.)
Post: #17
 Maximilian Hohmann Member Posts: 163 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
Hello!

So now that we have seen that feeding values to a built-in function (*) results in the shortest program I am really curious to see the SR56 implementation!

Max

(*) yes I know, the smart thing is to see this solution in the first place
09-20-2016, 09:17 AM
Post: #18
 Paul Dale Senior Member Posts: 1,003 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
The shortest implementation thus far is a brute force approach. My combinatorial approach is several more steps.

Pauli
09-20-2016, 12:21 PM (This post was last modified: 09-20-2016 04:16 PM by Gene.)
Post: #19
 Gene Senior Member Posts: 528 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
Only one solution was presented at HHC. Namir Shammas gave a solution that works, but has a rather long run time for some inputs.

Since there was only one solution, no winner was declared.

Test inputs were:

Code:
k      n       F(k,n) 4      20     597 7      12     12,306 3      12     66 6      50    126 6      30    47,631 2      15    4 5      44    5 5      20    4,998

Code:
 01: STO 01 02: X<>Y 03: DEC X 04: 10 05: X<>Y 06: Y^X 07: STO 00 08: 10 09: * 10: STO 03 11: 0 12: STO 02 13: LBL 00 14: RCL 00 15: X=? 03 16: GTO 01 17: 0 18: RCL 00 19: LBL 02 20: ENTER 22: ENTER 23: 10 24: STO / Z 25: STO / Y 26: X<>Y 27: FP 28: * 29: STO+ Z 30: RDN (ROLL DOWN) 31: IP 32: X NOT EQUAL 0 33: GTO 02 34: RDN  35: X=? 01 36: INC 02 37: INC 00 38: GTO 00 39: LBL 01 40: RCL 02 41: END
09-20-2016, 04:00 PM
Post: #20
 Didier Lachieze Senior Member Posts: 679 Joined: Dec 2013
RE: HHC 2016 RPN contest is now live
(09-19-2016 09:19 PM)Paul Dale Wrote:  Steps 13 and 14 in my original program are not required -- I forgot how the Sigma function takes it arguments Combine this with the earlier one step saving and my solution is down to 29 steps.

Kudos for the formula! Here is a slightly modified version of your solution with one step and one register less: 29 steps including the END and using 3 registers (I,J,K) instead of 4 (J,K,00,01), still a bit longer than my brute force solution (2 steps and 1 register more) but much much more faster !

Code:
01:        [cplx]STO J 02:        XEQ a 03:        DEC K 04:        XEQ a 05:        RCL- I 06:        RTN              07:   a::  [cplx]RCL J 08:        SDR 001 09:        IP 10:        MIN 11:        [Sigma] 00 12:        x<> I 13:        RTN          14:        LBL 00 15:        (-1)[^x] 16:        RCL K 17:        RCL Z 18:        COMB 19:        * 20:        RCL J 21:        # 010 22:        RCL* T 23:        - 24:        RCL K 25:        DEC X 26:        STO+ Y 27:        COMB 28:        * 29:        END
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)