HHC 2016 RPN contest is now live

[Jeff O.]

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.