HHC 2016 RPN contest is now live

[Gene]

HHC 2016 RPN contest PDF

Please post your results after 6pm USA Central time Sunday.

[Werner]

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

[Gene]

You can assume inputs between 1 <= n <= 9 and 1 <= k <= 100 (81 of course).

:-)

[Paul Dale]

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.

[Gene]

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. :-)

[Paul Dale]

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

[Gerson W. Barbosa]

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

[Paul Dale]

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

[Werner]

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

[Paul Dale]

(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

[Didier Lachieze]

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.

[Paul Dale]

Some explanation about my approach.

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

[Paul Dale]

(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

[Gerson W. Barbosa]

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

[Paul Dale]

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

[Werner]

(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

[Maximilian Hohmann]

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!

Regrads
Max

(*) yes I know, the smart thing is to see this solution in the first place

[Paul Dale]

The shortest implementation thus far is a brute force approach. My combinatorial approach is several more steps.


Pauli

[Gene]

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

[Didier Lachieze]

(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