HHC 2016 RPN contest is now live

09172016, 01:36 PM
Post: #1




HHC 2016 RPN contest is now live  
09172016, 03:57 PM
Post: #2




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 

09172016, 04:03 PM
Post: #3




RE: HHC 2016 RPN contest is now live
You can assume inputs between 1 <= n <= 9 and 1 <= k <= 100 (81 of course).
:) 

09182016, 12:44 AM
Post: #4




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. 

09182016, 01:06 AM
Post: #5




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

09182016, 04:42 AM
(This post was last modified: 09192016 12:26 PM by Paul Dale.)
Post: #6




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 

09182016, 05:30 AM
Post: #7




RE: HHC 2016 RPN contest is now live
(09182016 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. 

09192016, 05:20 AM
Post: #8




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

09192016, 11:09 AM
Post: #9




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 

09192016, 11:42 AM
Post: #10




RE: HHC 2016 RPN contest is now live  
09192016, 11:44 AM
Post: #11




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

09192016, 12:09 PM
(This post was last modified: 09192016 12:27 PM by Paul Dale.)
Post: #12




RE: HHC 2016 RPN contest is now live
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+k1}{k1} \) possibilities (see e.g. here). To enforce the must be a digit restriction use the inclusionexclusion 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+k10i1}{k1} \) However, this allows leading zeros, so we do the summation a second time for k1 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+k10i1}{k1}  \sum_{i=0}^{min(k1, \lfloor{\frac{n}{10}}\rfloor)} (1)^i \binom{k1}{i} \binom{n+k10i2}{k2} \) 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 

09192016, 12:16 PM
Post: #13




RE: HHC 2016 RPN contest is now live
(09192016 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 

09192016, 01:47 PM
(This post was last modified: 09192016 01:52 PM by Gerson W. Barbosa.)
Post: #14




RE: HHC 2016 RPN contest is now live
(09192016 12:09 PM)Paul Dale Wrote: \( \sum_{i=0}^{min(k, \lfloor{\frac{n}{10}}\rfloor)} (1)^i \binom{k}{i} \binom{n+k10i1}{k1}  \sum_{i=0}^{min(k1, \lfloor{\frac{n}{10}}\rfloor)} (1)^i \binom{k1}{i} \binom{n+k10i2}{k2} \) 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 7step would do the job: Code:
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:
No further improvement from here, though. (09192016 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. 

09192016, 09:19 PM
Post: #15




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 

09202016, 06:41 AM
Post: #16




RE: HHC 2016 RPN contest is now live  
09202016, 09:03 AM
(This post was last modified: 09202016 09:04 AM by Maximilian Hohmann.)
Post: #17




RE: HHC 2016 RPN contest is now live
Hello!
So now that we have seen that feeding values to a builtin 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 

09202016, 09:17 AM
Post: #18




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 

09202016, 12:21 PM
(This post was last modified: 09202016 04:16 PM by Gene.)
Post: #19




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


09202016, 04:00 PM
Post: #20




RE: HHC 2016 RPN contest is now live
(09192016 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 

« Next Oldest  Next Newest »

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