RE: HHC 2016 RPN contest is now live - Didier Lachieze - 09-20-2016 08:48 PM
One more trick, two steps less :
Code:
01: [cplx]STO J
02: XEQ a
03: DEC K
04: a:: [cplx]RCL J
05: SDR 001
06: IP
07: MIN
08: [Sigma] 00
09: x<> I
10: RCL- I
11: RTN
12: LBL 00
13: (-1)[^x]
14: RCL K
15: RCL Z
16: COMB
17: *
18: RCL J
19: # 010
20: RCL* T
21: -
22: RCL K
23: DEC X
24: STO+ Y
25: COMB
26: *
27: END
RE: HHC 2016 RPN contest is now live - Gene - 09-21-2016 01:09 PM
Here's a link to a fast solution generator on the web.
Change N and SUM in the code here:
// Driver program
int main()
{
int n = 3, sum = 5;
cout << finalCount(n, sum);
return 0;
}
and click RUN.
http://code.geeksforgeeks.org/index.php
RE: HHC 2016 RPN contest is now live - Gerson W. Barbosa - 09-21-2016 05:21 PM
(09-20-2016 06:41 AM)Werner Wrote: (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
Thanks for the improvement! I'm glad I didn't post the previous 11-step version :-)
Code:
001- LBL A
002- cENTER
003- +
004- DEC X
005- Γ
006- x<>y
007- Γ
008- /
009- Rv
010- Γ
011- /
012- END
RE: HHC 2016 RPN contest is now live - Jeff O. - 10-05-2016 05:00 PM
This is a little late to the party, but better late than never, I guess.
As is my usual practice, I did not look at the discussion of solutions to the HHC 2016 RPN Programming Contest until I decided that I was satisfied with my own efforts or reached a dead end. I did look at the thread before the embargo was lifted, and saw Pauli's post that he had a 32 step solution that ran instantaneously. Upon seeing that, I figured there must be some simple(?) technique to solve the challenge of which I was not aware. But since it is fun to attack Gene's challenges, I went ahead and pursued my first thought, which was of course, brute force: form the lowest k-digit number, find the sum of its digits, see if it equals the target sum, if so, increment a counter, if not, don't increment the counter, then increment the k-digit number and repeat up to the highest k-digit number. I suspected that it might take a long time to run on a 34s for some inputs, but I went ahead anyway, and was able to get a program up and running fairly quickly. It took about 75 seconds to return 35 as the answer to f(4,5), Gene's explanatory example. Based on that timing, figuring about a factor of 10 in execution time for each additional digit, I did not want to run it on even a 5 digit number. The next day, I entered the program into the wp34s emulator on my PC. It of course gave much quicker results, so I was able to check Gene's (valid) sample cases. Feeling brave, I turned the emulator loose on f(9,56) and let it run overnight. I was not at the PC when it finished, but my best guess is that it took 10 to 12 hours to return 9,286,233. In case anyone is interested, here is the code for that brute force program:
Code:
001 LBL"HHC"
002 STO 00 store target sum n in 00
003 x<> Y swap
004 10^x Form maximum k-digit number +1
005 ROUNDI make sure it is an integer
006 STO A store max k-digit+1 number in A
007 SDR 001 Form minimum k-digit number
008 STO B store in B
009 CLx clear x
010 STO C store zero in C, count of digit sums n in k-digit number
011 CLx clear x (target of BACK in step 030)
012 STO D store zero in D, sum of digits in current number
013 RCL B recall current number whose digits are being summed
014 SDR 001 divide by 10
015 ENTER enter
016 FP fractional part
017 STO- Y subtract fractional part from current number divided by 10
018 SDL 001 multiply fractional part by 10
019 STO+ D add to D, sum of digits of current number
020 Rdn roll down
021 x=/=0? is number being summed not equal 0?
022 BACK 008 if not, loop back to sum next digit
023 RCL D when done, recall sum of digits
024 x=/=? 00 sum of digits not equal to target sum?
025 SKIP 001 if not, skip
026 INC C if equal, increment count of digit sums equal to n
027 RCL A recall maximum k-digit number + 1
028 INC B increment current number whose digits to be summed
029 x=/=? B next number not equal maximum k-digit+1?
030 BACK 019 if not, go back to sum digits of next no. and check sum
031 RCL C if equal, recall count of digits sums equal to n
032 END done
At this point, my suspicions were of course confirmed that this was not the optimal approach to this problem, so I did not attempt to refine the program to reduce the number of steps, registers used, etc. To move forward, I decided to see if I could discern some sort of pattern. I started building a table which presented the counts of digit sums for number of digits vs. desired sum of the digits, like this:
Code:
sum of Number of Digits
Digits 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7 8 9
3 1 3 6 10 15 21 28 36 45
4 ...
I was able to figure out the answers for the simple values by hand, used my above program on the emulator for up to 6-digit values, and eventually used Gene's calculation source which he kindly provided directly to me to extend the above table in excel. In an effort to make a long story short, I was eventually able to deduce that:
f(k,n) = f(k-1,n) + f(k,n-1) - f(k-1,n-10)
Below is a screenshot of part of part of an excel table implementing the above formula. As an example, the value highlighted in blue, f(7,12), can be seen to be equal to the value highlighted in red, f(6,12) plus the value highlighted in yellow, f(7,11) minus the value highlighted in green, f(6, 2). The two cells with the little red triangles in the corners must be initialized to 1. The cells highlighted in orange must be forced to be zero. Beyond those forced values, the formula produces all of the other correct values in the table.
With the above as an aid, I was eventually able to implement the method in a wp34s program. I have a working 63-step program on a physical wp34s that returns correct values for 9-digit numbers in about 3 seconds maximum. It could be extended to handle at least up to 11-digit arguments* within the memory confines of a wp34s, it would just run a little slower. In case it is not obvious, the method requires the current sum plus the previous 101 values to be retained in memory. I used local registers with rolling pointers to do that. (There is probably a more effective way of updating the pointers for each iteration, but I quit with what worked.) I forced the zeros required in the left-most column every 10th sum instead of calculating that sum by the formula using an inner loop. Here is the listing:
Code:
001 LBL"HHC" Comments
002 DEC X subtract 1 from target sum n
003 SDL 001 ten times (target sum -1)
004 + add number of digits to form count of iterations, C
005 STO 02 store count of iterations in 02
006 REGS 010 set number of regs to low value to free space for 102 local regs
007 #112 constant 112
008 STO A store initial r000 pointer value
009 #113 constant 113
010 STO B store initial r001 pointer value
011 #122 constant 122
012 STO C store initial r010 pointer value
013 #213 constant 213
014 STO D store initial r101 pointer value
015 #002 constant 002
016 STO 03 store initial 10 loop counter in 03
017 LocR 102 create 102 local registers
018 #001 constant 001
019 STO-> A store initial 1 in R01
020 STO .11 store initial 1 in R11
021 LBL 01
022 DSE 02 decrement iteration count, skip when zero
023 SKIP 002
024 RCL-> A Recall final sum
025 RTN finished
026 DEC A decrement r000 pointer
027 DEC B decrement r001 pointer
028 DEC C decrement r010 pointer
029 DEC D decrement r101 pointer
030 #111 constant 111
031 x=/=? A is r000 pointer not equal to 111?
032 SKIP 003 if not, skip to check r001 pointer
033 #213 if r000 pointer is equal to 111, set pointer to max local reg
034 STO A store new r000 pointer
035 SKIP 014 done updating, skip to calculate next count
036 x=/=? B is r001 pointer not equal to 111?
037 SKIP 003 if not, skip to check r011 pointer
038 #213 if r001 pointer is equal to 111, set pointer to max local reg
039 STO B store new r001 pointer
040 SKIP 009 done updating, skip to calculate next count
041 x=/=? C is r010 pointer not equal to 111?
042 SKIP 003 if not, skip to check r010 pointer
043 #213 if r010 pointer is equal to 111, set pointer to max local reg
044 STO C store new r010 pointer
045 SKIP 004 done updating, skip to calculate next count
046 x=/=D? is r101 pointer not equal to 111?
047 SKIP 002 if not, done updating, skip to calculate next count
048 #213 if r101 pointer is equal to 111, set pointer to max local reg
049 STO D store new r101 pointer
050 #010 constant 010
051 x=/=? 03 check if loop count equal 10
052 SKIP 004 if no, proceed to calculate sum
053 CLx if count is multiple of 10…
054 STO->A ...force current sum to be zero
055 STO 03 reset loop count to zero
056 SKIP 004
057 RCL->B recall r001
058 RCL+->C add r010
059 RCL- ->D subtract r101
060 STO->A store in r000
061 INC 03 increment 10 loop counter
062 GTO 01
063 END
Disclaimer - I do not claim that the above method is anything special, certainly still brute force compared to the insightful methods presented in the posts above. But since it is a different approach that produces correct results, I thought I'd go ahead and present it.
* - 10 digits would require 112 local registers, 11 digits would require 122, 12 digits would require 132, and 13 digits would require 142 local registers. The manual states that there can be up to 144 local registers created, but when I tried to extend past 11 digits, i.e., tried to enter LocR 132 or LocR 142, the instruction defaulted to LocR 013 or LocR 014. I've tried to read all instructions regarding creation and use of local registers in the manual, but have still not figured out what I am doing wrong.
Edit - saw a simple improvement to the brute force program, could not stop myself from revising it.
Edit 2 - ditto for the 2nd program, also implemented a slightly optimized routine to update the pointers. Same number of steps but should run slightly faster.
[attachment=3999]
RE: HHC 2016 RPN contest is now live - Gene - 10-05-2016 06:56 PM
Excellent Jeff! That's great!
RE: HHC 2016 RPN contest is now live - Jeff O. - 10-06-2016 11:42 AM
(10-05-2016 06:56 PM)Gene Wrote: Excellent Jeff! That's great!
Thanks Gene, another fun and exciting challenge! Can't wait until next year!
RE: HHC 2016 RPN contest is now live - Paul Dale - 10-06-2016 11:47 AM
Jeff,
An very interesting approach to the problem. Kind of halfway between brute force and my analytic solution.
Pauli
RE: HHC 2016 RPN contest is now live - Jeff O. - 10-06-2016 04:26 PM
(10-06-2016 11:47 AM)Paul Dale Wrote: Jeff,
An very interesting approach to the problem. Kind of halfway between brute force and my analytic solution.
Pauli
Pauli,
Any analysis on your part as to why it works? I was fairly shocked that it did, even producing the proper results when the counts are decreasing for sums over half of the maximum for a given number of digits, even producing the zeros for the counts of sums over the maximum. I thought I'd have to force those cases.
Also, any idea why I cannot create more than 127 local registers?
Jeff
RE: HHC 2016 RPN contest is now live - Werner - 10-07-2016 06:49 AM
Well, it is easy to see that
f(k,n) = sum(i=0..9,f(k-1,n-i))
(which is what I used in a quick RPL program to verify the results)
so
f(k,n-1) = sum(i=0..9,f(k-1,n-1-i))
Naturally the two sums coincide except for the first and last elements, so
f(k,n) = f(k,n-1) - f(k-1,n-10) + f(k-1,n)
But I never thought of that, either ;-)
Cheers, Werner
RE: HHC 2016 RPN contest is now live - Jeff O. - 10-07-2016 02:03 PM
(10-07-2016 06:49 AM)Werner Wrote: ....But I never thought of that, either ;-)
Cheers, Werner
Well, I did not think of it, just managed to stumble across it. Once found, the fun part was implementing on the 34s.
Jeff
RE: HHC 2016 RPN contest is now live - Jeff O. - 10-14-2016 07:48 PM
(10-06-2016 04:26 PM)Jeff O. Wrote: Also, any idea why I cannot create more than 127 local registers?
Just to close the loop on this, I consulted with Marcus and found that creation of more than 127 local registers must be done via indirection. So, to set 144 local registers one must do as follows:
...
#144
LocR->X
...
I do not believe that the above is specifically stated anywhere in the manual, if so, I was unable to find it. It does follow from footnote no. 112 on page 271 of the manual: "Only arguments up to 127 are storable in an op-code, hence the limit." This was in reference to accessing local registers, but of course would logically apply to keying in something like "LocR 142".
With that mystery (to me) solved, I modified my program to calculate the number of sums n in a k-digit number for k equal up to 13, presented below. It does run a little more slowly than the version limited to 9 digits; there appears to be about a 1.5 second penalty for large sums in 9-digit numbers. It calculates f(13, 117) in about 7.5 seconds. As warned in the manual (p.270), creating so many local registers requires you to be aware of how many steps are in use in program memory. If you have too many program steps used, you'll get a "RAM is FuLL" message when you try to run the program. I had to move some programs to the library so that there were no more than 351 program steps in RAM before it would run. I also added a couple of steps to release the local registers and reset the number of regular numbered registers to 100. Otherwise it stops with no such registers allocated, which would likely affect running other programs.
Code:
001 LBL"HHC"
002 DEC X subtract 1
003 #014 constant 14 (10 for k=9, 11 for k=10, 12 for k=11, 13 for k=12, 14 for k=13)
004 x 14 times (target sum -1)
005 + add number of digits to form count of iterations
006 STO J store count of iterations in J
007 REGS 000 set number of numbered registers to low value to free space for local regs.
Can be set to 0 since only lettered regs are used
008 #112 constant 112
009 STO A store initial R000 pointer value
010 #113 constant 113
011 STO B store initial R001 pointer value
012 #126 constant 126 (122 for k=9, 123 for k=10, 124 for k=11, 125 for k=12, 126 for k=13)
013 STO C store initial pointer to R014
014 #253 constant 253 (213 for k=9, 223 for k=10, 233 for k=11, 243 for k=12, 253 for k=13)
015 STO D store initial R141 pointer value
016 #002 constant 002
017 STO K store initial forced zero sum loop counter in K
018 #142 constant 142 to indirectly set 142 local registers (indirection not required for less than 127)
019 LocR ->X create 142 local registers (102 for k=9, 112 for k=10,
122 for k=11, 132 for k=12, 142 for k=13)
020 #001 constant 001
021 STO-> A store initial 1 in LocR001
022 STO .15 store initial 1 in LocR015 (.11 for k=9, .12 for k=10,
.13 for k=11, .14 for k=12, .15 for k=13)
023 LBL 01 Label for overall count loop iteration, easier to keep track of than BACK
024 DSE J decrement iteration count, skip when zero
025 SKIP 004 skip to update pointers and calculate next sum if not done
026 RCL-> A done, Recall final sum
027 LocR 000 release local registers (optional)
028 REGS 100 restore 100 standard registers (optional)
029 RTN finished
030 DEC A decrement R000 pointer
031 DEC B decrement R001 pointer
032 DEC C decrement R014 pointer
033 DEC D decrement R141 pointer
034 #111 constant 111
035 x=/=A? is R000 pointer not equal to 111?
036 SKIP 003 if not, skip to check r001 pointer
037 #253 if R000 pointer is equal to 111, set pointer to max local reg
038 STO A store new R000 pointer
039 SKIP 014 done updating pointers, go calculate next sum
040 x=/=B? is R001 pointer not equal to 111?
041 SKIP 003 if not, skip to check R011 pointer
042 #253 if R001 pointer is equal to 111, set pointer to max local reg
043 STO B store new R001 pointer
044 SKIP 009 done updating pointers, go calculate next sum
045 x=/=C? is R014 pointer not equal to 111?
046 SKIP 003 if not, skip to check R141 pointer
047 #253 if R014 pointer is equal to 111, set pointer to max local reg
048 STO C store new R014 pointer
049 SKIP 004 done updating pointers, go calculate next sum
050 x=/=D? is R141 pointer not equal to 111?
051 SKIP 002 if not, done checking/updating pointers, go calculate next sum
052 #253 if R141 pointer is equal to 111, set pointer to max local reg
053 STO D store new R141 pointer
054 #014 constant 014 (10 for k=9, 11 for k=10, 12 for k=11, 13 for k=12, 14 for k=13)
055 x=/=? K check if forced zero sum loop count equal 14
(10 for k=9, 11 for k=10, 12 for k=11, 13 for k=12, 14 for k=13)
056 SKIP 004 if no, proceed to calculate sum
057 CLx if count is multiple of 14…
058 STO->A ...force current sum to be zero
059 STO K reset forced zero sum loop counter to zero
060 SKIP 004 skip sum calculation if sum forced to zero
061 RCL->B recall previous sum
062 RCL+->C add sum from 14 sums ago (10 for k=9, 11 for k=10, 12 for k=11, 13 for k=12, 14 for k=13)
063 RCL- ->D subtract sum from 141 sums ago (101 for k=9, 111 for k=10, 121 for k=11, 131 for k=12, 141 for k=13)
064 STO->A store new sum in current register pointed to by A
065 INC K increment forced zero sum loop counter
066 GTO 01 loop back to decrement count, update pointers, calculate next sum
067 END
New version 8 steps shorter:
Code:
001 LBL"HHC"
002 DEC X subtract 1
003 #014 constant (10 for k=9, 11 for k=10, 12 for k=11, 13 for k=12, 14 for k=13)
004 x constant times (target sum -1)
005 + add number of digits to form count of iterations + 1
006 DEC X decrement to get the number of iterations required to calculate the target sum
007 STO J store count of iterations in J
008 REGS 000 set number of regs to low value to free space for 102 to 142 local regs
009 #111 constant 111
010 SDR 003 shift digits right 3 places to create .111
011 #112 constant 112, points to lowest local register
012 + add .111 to set DSE skip index
013 STO A Set pointer A to initial value of 112
014 INC X increment by 1 for initial B value
015 STO B Set pointer B to initial value of 113
016 #13 constant 13
017 + add to initial B pointer to obtain initial C pointer value of 126
018 STO C Set pointer C to initial value of 126 (122 for k=9, 123 for k=10, 124 for k=11, 125 for k=12, 126 for k=13)
019 #127 constant 127
020 + add to initial C pointer to obtain initial D pointer value of 253
021 STO D Set initial D pointer D value to 253 (213 for k=9, 223 for k=10, 233 for k=11, 243 for k=12, 253 for k=13)
022 #013 constant 13
023 STO K store initial loop counter to set every (k+1)th sum to zero in K
024 #142 constant 142 to indirectly set 142 local registers (indirection not required for less than 127)
025 LocR ->X create 142 local registers (102 for k=9, 112 for k=10, 122 for k=11, 132 for k=12, 142 for k=13)
026 #001 constant 001
027 STO-> A store initlal 1 in registere 112
028 STO .15 store initial 1 in register 127 (.11 for k=9, .12 for k=10, .13 for k=11, .14 for k=12, .15 for k=13)
029 DSE A Begin loop to calculate sums, decrement A pointer…
030 SKIP 002 skip when equal to 111
031 #142 constant 142
032 STO+ A if A pointer is equal to 111, set pointer to max local reg by adding 142
033 DSE B decrement B pointer…
034 SKIP 002 skip when equal to 111
035 #142 constant 142
036 STO+ B if B pointer is equal to 111, set pointer to max local reg by adding 142
037 DSE C decrement C pointer…
038 SKIP 002 skip when equal to 111
039 #142 constant 142
040 STO+ C if C pointer is equal to 111, set pointer to max local reg by adding 142
041 DSE D decrement D pointer…
042 SKIP 002 skip when equal to 111
043 #142 constant 142
044 STO+ D if D pointer is equal to 111, set pointer to max local reg by adding 142
045 DSE K decrement loop counter setting every (k+1)th sum to zero
046 SKIP 004 skip when equal zero
047 #014 constant 14
048 STO K reset loop counter to 14
049 CLx clear x for zero,
050 SKIP 003 if count is multiple of 14, skip to force current sum to be zero
051 RCL->B recall register pointed to by B, sum(k-1,n)
052 RCL+->C recall and add register pointed to by C, sum(k,n-1)
053 RCL- ->D recall and subtract register pointed to by D, sum(k-1,n-10), forms sum(k,n)
054 STO->A store new sum(k,n) in register pointed to by A
055 DSE J decrement loop counting iterations required for input k,n
056 BACK 027 if not zero, loop back to update pointers, calculate next sum
057 LocR 000 if zero, final sum complete, release local registers…
058 REGS 100 restore 100 standard registers (optional)
059 END stop, final sum displayed
Over 7 years after writing the above code, for some reason I felt like entering it into the WP 34S emulator app on my phone. When it did not work, I had to remember how to program the WP 34S, then troubleshoot the program, and found a typo in the above original listing which I have corrected for posterity. Then of course I had to see if I could improve it, and developed the new version above, which is 8 steps shorter (really only 7 since I saved a step by eliminating the single label) and just better overall, I think. A real WP 34S returns results in about 9 seconds for the worst case input of 13, 117. By way of comparison, the same algorithm on a 35s takes about 9 minutes for that input.
|