HHC 2016 RPN contest is now live
|
09-20-2016, 08:48 PM
Post: #21
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
One more trick, two steps less :
Code: 01: [cplx]STO J |
|||
09-21-2016, 01:09 PM
(This post was last modified: 09-21-2016 01:10 PM by Gene.)
Post: #22
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
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 |
|||
09-21-2016, 05:21 PM
Post: #23
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
(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: Thanks for the improvement! I'm glad I didn't post the previous 11-step version :-) Code:
|
|||
10-05-2016, 05:00 PM
(This post was last modified: 02-06-2024 06:31 PM by Jeff O..)
Post: #24
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
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" 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 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 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. Dave - My mind is going - I can feel it. |
|||
10-05-2016, 06:56 PM
Post: #25
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
Excellent Jeff! That's great!
|
|||
10-06-2016, 11:42 AM
Post: #26
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
(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! Dave - My mind is going - I can feel it. |
|||
10-06-2016, 11:47 AM
Post: #27
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
Jeff,
An very interesting approach to the problem. Kind of halfway between brute force and my analytic solution. Pauli |
|||
10-06-2016, 04:26 PM
Post: #28
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
(10-06-2016 11:47 AM)Paul Dale Wrote: Jeff, 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 Dave - My mind is going - I can feel it. |
|||
10-07-2016, 06:49 AM
Post: #29
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
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 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE |
|||
10-07-2016, 02:03 PM
Post: #30
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
(10-07-2016 06:49 AM)Werner Wrote: ....But I never thought of that, either ;-) Well, I did not think of it, just managed to stumble across it. Once found, the fun part was implementing on the 34s. Jeff Dave - My mind is going - I can feel it. |
|||
10-14-2016, 07:48 PM
(This post was last modified: 02-13-2024 01:50 PM by Jeff O..)
Post: #31
|
|||
|
|||
RE: HHC 2016 RPN contest is now live
(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" New version 8 steps shorter: Code: 001 LBL"HHC" Dave - My mind is going - I can feel it. |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 6 Guest(s)