HHC 2019 will be in Reno, Nevada, Sept 21-22

[Eric Rechlin]

(09-24-2019 06:41 PM)Brian Walsh Wrote:  It's simply that timeliness of posting the challenge is what matters to those who want to submit contest entries.

But you can only submit entries if you are present, and you weren't present, so I don't understand why it matters to you.

[Jake Schwartz]

Hi,

For what it is worth, Roger Hill's RPL solution ran in less than 5 seconds, if I remember correctly. Hopefully, the winning ones in each machine category can be posted in the near future.

Thanks,
Jake

[Brian Walsh]

(09-24-2019 07:06 PM)Eric Rechlin Wrote:  But you can only submit entries if you are present, and you weren't present, so I don't understand why it matters to you.

I'm embarrassed to say I wasn't aware of that rule. I apologize for all the fuss.

[Gerson W. Barbosa]

(09-23-2019 03:08 AM)Wes Loewer Wrote:  Here are my smallest and my fastest 50g entries:

smallest:
95 bytes
128 sec

Code:










«
100 DUP 999 START
 DUPDUP 
 10 MOD 
 LASTARG / 10 MOD 
 LASTARG /  
 3. ->LIST IP 3. ^ sigmaLIST
 == OVER IFT 1. +
NEXT
DROP
»

and fastest
154 bytes
21.4 sec

Code:













«
1. 9. FOR h
0. 9. FOR t
0. 9. FOR o
h 100. * t 10. * + o +
h DUPDUP * * t DUPDUP * * + o DUPDUP * * +
IF  OVER not= THEN
 DROP
END
NEXT NEXT NEXT
»

Based on Claudio’s idea:

Code:


« 2. ALOG 964.
  FOR k k DUP 2. ALOG IDIV2 10. IDIV2 3. →LIST DUP SQ * ∑LIST == k IFT
  NEXT
»

96 bytes, 214.7 seconds.

Your smallest one can get even smaller by simply replacing 100 with 2 ALOG (down to 89.5 bytes).

My very first program would take one minute to run, probably because of cubes being computed as 3 y^3, instead of DUP SQ. Now 21.7 seconds and incidentally 154 bytes long:

Code:


« 1. 9.
  FOR h 0. 9.
    FOR t 0. 9.
      FOR u h 10. * t + 10. * u + h DUP SQ * t DUP SQ * + u DUP SQ * + OVER ≠ { DROP } IFT
      NEXT
    NEXT
  NEXT
»

[Jeff O.]

(09-24-2019 02:22 AM)dramsey Wrote:  Regarding this year's programming contest:

2. Also, I'd give less information on the solution. Several people "optimized" their programs by having them stop after four results were found, since I'd specifically said there were four numbers that satisfied the "three digit numbers equal to the sum of the cubes of their digits." This wasn't really what I was looking for but it was within the rules...

You also required that the four results be on the stack at the end, so after four were found it would be natural to stop. Pretending that I did not know there would be only four results, and therefore not knowing that they would fit on the stack so I had to come up with my own way to present the results, I came up with the program below, for 42S/DM42/Free42. It simply seqentially checks all 3 digit numbers, then stops and shows each successful result as it is found. The user must press R/S to continue, with "999" in the X register indicating all numbers have been checked and all successful results displayed.

Code:


001    LBL "HC19"    program label        
002    CF 29         suppress trailing decimal point In FIX 0        
003    FIX 0         fix for single digit display        
004    99.999        enter 99.999 for number generation and loop        
005    STO 00        store 99.999        
006    LBL 01        label for overall loop        
007    ISG 00        increment counter for 3-digit number to check        
008    GTO 04        not done, sum digits cubed and check        
009    STOP          done checking 100 to 999, X register shows 999 to indicate completion.        
010    LBL 04                
011    RCL 00        recall counter        
012    IP            take integer part to eliminate 999 after decimal        
013    CLA           clear alpha register        
014    ARCL ST X     store number whose digits to be cubed-summed in Alpha reg        
015    0             enter 0 to initialize sum of digits cubed        
016    LBL 03        label for branch to shift digits and Σ d^2        
017    ATOX          shift leftmost byte from ALPHA        
018    X=0?                  
019    GTO 00        if zero, done cubing and summing, go check if equal to original number        
020    48            not zero, so not done.  sum digit cubed.  first enter 48...
021    -            ...then subtract from extracted byte to convert to digit                
022    3             enter 3        
023    Y^X           cube digit        
024     +            add to running sum of cubed digits        
025    GTO 03        go back for next digit        
026    LBL 00        label to check if original number equal to sum of cubes        
027    X<>y          swap to get Σ d^3 in x register        
028    RCL 00        Recall orignal number        
029    IP            take integer part to eliminate 999 after decimal        
030    X!=Y?        check if not equal        
031    GTO 01        if not equal, go back for next number        
032    VIEW ST X     if equal, show X register         
033    STOP          stop to show result, user to press R/S to...
034    GTO 01        ...go back for next number        
035    END

(This program used the core of my program for Gene's "Happy Number" challenge of a few years ago which summed digits squared - so I had the code handy and it was easy to modify that to sum digits cubed. Also, yes, it could stop at 963, but that's not much of an optimization so I just go all the way to 999.)

[David Hayden]

Here is my entry, which won the "Modern RPN" prize.

Rather than going through the numbers 100-999 and extracting digits, this goes through the digits and constructs the number. I figured that this would be faster (unverified), but I see from other posts that it results in much larger code (63 steps with the label and END vs. mid-high 30's).

Let's call the digits in the number X,Y,Z. So when considering the number 123, X=1, Y=2 and Z=3.

The program loops through possible values of X, then Y, then Z. Along the way it computes the partial sums of cubes:
S1 = X^3
S2 = X^3+Y^3
S3 = X^3+Y^3+Z^3
and also stores the partial values of the number:
N1 = X00
N2 = XY0
N3 = XYZ

all of this is to minimize the computation needed in the innermost loop.

The program breaks out of the "Z" loop if it determines that the partial sum-of-cubes is larger than any possible value that would be considered in the loop. This cuts the number of iterations in the Z loop to 440. A similar test in the Y loop could avoid some iterations of Z completely but I decided that one pass through the Z loops was worth saving the space and time of the duplicate check.

In pseudocode-Prime code, the program is:

Code:

// Pre-compute 0^3..9^3
for X from 1 to 9 do          // No leading zeros
  S1 := X^3;
  N1 := 100*X;
  for Y from 0 to 9 do
    S2 := S1 + Y^3;
    N2 := N1 + 10*Y
    for Z from 0 to 9 do
      S3 := S2 + Z^3;
      N3 := N2+Z;
      if (S3 = N3) then
        print N3;  // Got it!
      END;
      if S3 > N2+9 then break; end;    // No future value of Z will work
    END;
  END;
END;

Registers (in the end I didn't need some of these)
R0..R9 0^3 - 9^3
R10..R11 Partial sums S1..S3
R13..R15 Partial numbers N1..N3
R16..R18 Digits X, Y, and Z
R19 Index to store results
R20..R23 Results

Labels:
L02..L04 Top of X, Y, and Z loops
L05 Bottom of Y loop
L06 Bottom of Z loop

Code:

01 LBL "CUBES"
02 9            ; pre-compute 0^3 .. 9^3 into R00..R09
03 LBL 01
04 RCL ST X
05 3
06 Y^X
07 STO IND ST Y
08 X<>Y
09 DSE ST X
10 GTO 01
11 STO 00        ; X=0 when you get here

12 23          ; R19 is index register for storing results
13 STO 19

14 1.009        ; for X digit = 1 to 9
15 STO 16
16 LBL 02
17 RCL IND 16    ; X^3
18 STO 10      ; S1 = X^3
19 RCL 16
20 IP
21 100
22 *
23 STO 13        ; N1 = X*100

24 .009        ; for Y digit = 0 to 9
25 STO 17
26 LBL 03
27 RCL IND 17    ; Y^3
28 RCL+ 10
29 STO 11        ; S2 = X^3 + Y^3
30 RCL 17
31 IP
32 10
33 *            ; Y*10
34 RCL+ 13        ; X*100 + Y*10
35 STO 14        ; N2 = X*100 + Y*10

36 .009        ; For Z digit = 0 to 9
37 STO 18
38 LBL 04
39 RCL IND 18    ; Z^3
40 RCL +11     ; X^3 + Y^3 + Z^3 (S3)
41 RCL 18
42 IP
43 RCL+ 14        ; X*100 + Y*10 + Z (N3)
44 X=Y?        ; if X^3+Y^3+Z^3 = N3
45 STO IND 19    ; then store it
46 X=Y?           ; and increment the
47 DSE 19        ; result index register
48 9            ; DSE never faills
49 +
50 X<Y?        ; if S3 > N3+9 then no value for Z will work.
51 GTO 05        ; go to bottom of Y loop
52 ISG 18        ; Next Z
53 GTO 04

54 LBL 05        ; Next Y
55 ISG 17
56 GTO 03

57 ISG 16        ; Next X
58 GTO 02

59 RCL 23        ; Recall the 4 results to the stack
60 RCL 22
61 RCL 21
62 RCL 20
63 END

[jjohnson873]

(09-26-2019 05:33 PM)David Hayden Wrote:  Here is my entry, which won the "Modern RPN" prize.

[/code]

I keyed in David's HHC programming solution into my DM42. OMG! It's blazing fast! Not even using USB power. It takes about +1 second to find all four (4) solutions. I wondered if David somehow hid the four solutions in the code somewhere. LOL. (just kidding). So I put in loop counters into each of his three loops X, Y & Z. The X-loop took 9 iterations. The Y-loop took 90 iterations and the Z-loop took 538 iterations. All totaled, the program looped 435,780 times in about one second. Viva DM42!
I'm certain someone could figure out a more accurate execution time by counting bytes and estimating the execution time based on processor speed. But don't blink....it's fast.
Nice solution, Dave! And zippy too!

[David Hayden]

(09-27-2019 04:48 PM)jjohnson873 Wrote:  I keyed in David's HHC programming solution into my DM42. OMG! It's blazing fast!

Thanks Jim!

(09-27-2019 04:48 PM)jjohnson873 Wrote:  So I put in loop counters into each of his three loops X, Y & Z. The X-loop took 9 iterations. The Y-loop took 90 iterations and the Z-loop took 538 iterations. All totaled, the program looped 435,780 times in about one second. Viva DM42!

My Prime version indicated 440 iterations in the Z loop, but maybe that was an earlier version.

I think you've computed the total number of loops incorrectly. Since you measured the actual number of times in each loop, you should add them, not multiply.

I'm sure that someone will post a faster/smaller RPN solution, if they haven't already.

[jjohnson873]

(09-27-2019 09:31 PM)David Hayden Wrote:  

(09-27-2019 04:48 PM)jjohnson873 Wrote:  I keyed in David's HHC programming solution into my DM42. OMG! It's blazing fast!

Thanks Jim!

(09-27-2019 04:48 PM)jjohnson873 Wrote:  So I put in loop counters into each of his three loops X, Y & Z. The X-loop took 9 iterations. The Y-loop took 90 iterations and the Z-loop took 538 iterations. All totaled, the program looped 435,780 times in about one second. Viva DM42!

My Prime version indicated 440 iterations in the Z loop, but maybe that was an earlier version.

I think you've computed the total number of loops incorrectly. Since you measured the actual number of times in each loop, you should add them, not multiply.

I'm sure that someone will post a faster/smaller RPN solution, if they haven't already.

So these loops aren't nested inside of each other? I made an assumption they were nested, but should have checked the algorithm. It's still FAST! Thanks, Dave!

[Claudio L.]

(09-23-2019 01:54 PM)Claudio L. Wrote:  My take, nothing clever here, just plain brute force.

OK, now it's time to get a bit clever.
Below is a version of Wes's brute force, but this time it precomputes all multiplications and powers and stores them in lists.
This brings down execution time down to 49 ms (from 68 ms), 27% faster at the expense of some memory.

Code:


«
  { 0 1 2 3 4 5 6 7 8 9 } 'U' LSTO     @ Save the units
   U 10 * 'T' LSTO                           @ Save the tens
   T 10 * 'H' LSTO                           @ Save the hundreds
   U 3 ^ 'C' LSTO                            @ Save the cubes
   2 10 FOR 'X'
     1 10 FOR 'Y'
         1 10 FOR 'Z'
             U Z GET
             T Y GET
             H X GET
             + +                    @ Compute the number from its digits
             C Z GET
             C Y GET
             C X GET
            + +                     @ Compute the sum of cubes
            IF OVER ≠ THEN DROP END
      NEXT
    NEXT
  NEXT
»

And talking about clever... here comes David. The code below is identical except it does David's early exit trick, bringing down total execution time now to 35 ms.

Code:


«
  { 0 1 2 3 4 5 6 7 8 9 } 'U' LSTO     @ Save the units
   U 10 * 'T' LSTO                           @ Save the tens
   T 10 * 'H' LSTO                           @ Save the hundreds
   U 3 ^ 'C' LSTO                            @ Save the cubes
   2 10 FOR 'X'
     1 10 FOR 'Y'
         1 10 FOR 'Z'
             U Z GET
             T Y GET
             H X GET
             + +                    @ Compute the number from its digits
             C Z GET
             C Y GET
             C X GET
            + +                                    @ Compute the sum of cubes
            IF OVER - DUP THEN                     @ Keep the difference of the Sum(cubes)-Number
                  NIP IF 9 > THEN EXIT END         @ If the difference is more than 9, do early exit
            ELSE
                 DROP 
            END
      NEXT
    NEXT
  NEXT
»

[jjohnson873]

(09-23-2019 01:54 PM)Claudio L. Wrote:  My take, nothing clever here, just plain brute force. I had solved this previously, I found this code already in my calc I guess from some old challenge?.
Anyway, the trivial code was also in my calc already and Wes already posted it, so I won't repeat it. I do want to post this other version which splits the digits from a single loop.
Is quite straightforward, uses the newRPL-only DIGITS command to extract digits off a number ( <number> <start_digit> <end_digit> DIGITS):

Code:



«
  100 999 FOR 'K'
    K 0 0 DIGITS 3 ^
    K 1 1 DIGITS 3 ^ +
    K 2 2 DIGITS 3 ^ +
    IF K == THEN  K  END
  NEXT
»

This version runs in 0.097 seconds, while Wes fastest runs in 0.068 seconds. That's when run from within a program, if executed from the keyboard it's 0.556 seconds and 0.531 seconds respectively due to power-saving clock management.

Hello Claudio....was this written and run on an HP Prime or a different calculator? I was curious about how you arrived at the very accurate msec. timing.

[Albert Chan]

HP71B version, with a running sum of number less cube of its digits.

If the total is zero, we found an Armstrong number.
Slight optimization on the inner loop. Instead of running from 0 to 9, do 2 to 9

If Armstrong number N last digit is 0, N+1 must also be an Armstrong number.

Code:

10 DESTROY ALL @ DIM C(10) @ FOR I=1 TO 9 @ C(I)=I^3-I @ NEXT I
20 FOR X=1 TO 9 @ M=99*X-C(X)
30 FOR Y=MOD(X,2) TO 9 STEP 2 @ N=M+9*Y-C(Y) @ IF N<=0 THEN EXIT Y
40 FOR Z=2 TO 9 @ IF N<=C(Z) THEN EXIT Z
50 NEXT Z
60 IF N=C(Z) THEN DISP X;Y;Z
70 NEXT Y
80 IF N=0 THEN DISP X;Y;0 @ DISP X;Y;1
90 NEXT X

Note: discovered a BASIC quirk

FOR NEXT loops variable ends with first value that failed the loop.
>FOR K=1 TO 100 STEP 7 @ NEXT K
>K
106

So, above code Z loop can also do 2 to 8, and still run correctly.

Update: Y loop optimized with parity test, cutting search space in half.
see https://www.hpmuseum.org/forum/thread-13791.html

[Jeff O.]

(09-26-2019 05:33 PM)David Hayden Wrote:  ... I figured that this would be faster (unverified), but I see from other posts that it results in much larger code (63 steps with the label and END vs. mid-high 30's).

My version may have been “only” 35 steps, but did not put the results on the stack as per the rules. If I add steps to do so brought, it is now 42 steps, and it takes approximately 3.5 to 4 seconds to run on my DM42. The extra steps for your more elegant and (verified) much faster program are well worth it.

[David Hayden]

(09-27-2019 09:59 PM)jjohnson873 Wrote:  So these loops aren't nested inside of each other? I made an assumption they were nested, but should have checked the algorithm. It's still FAST! Thanks, Dave!

Yes they are nested, but if you added a counter inside the Z loop then you counted the total number of loops in X, Y, and Z. The Z loop definitely doesn't run half a million times to check just 900 numbers

[David Hayden]

I think this can be used to time the program:
LBL 01
TIME
STO 24
XEQ "CUBES" ; or whatever program you're timing
TIME
RCL 24
HMS-
END

On my DM42, my program takes 1.02s. On a 41C w/ quad memory module, 5 minutes, 7 seconds.

[Claudio L.]

(09-28-2019 12:44 AM)jjohnson873 Wrote:  Hello Claudio....was this written and run on an HP Prime or a different calculator? I was curious about how you arrived at the very accurate msec. timing.

NewRPL has 10 microsecond resolution on the TEVAL command.

[Craig Bladow]

(09-28-2019 04:45 PM)David Hayden Wrote:  I think this can be used to time the program:
LBL 01
TIME
STO 24
XEQ "CUBES" ; or whatever program you're timing
TIME
RCL 24
HMS-
END

On my DM42, my program takes 1.02s. On a 41C w/ quad memory module, 5 minutes, 7 seconds.

I used Dave's timing program to time my entry to the programming contest at HHC 2019.

It runs in 1.4 seconds on a DM42 running on battery.

The program reduces the search space to 8*8*8 by not evaluating some combinations that would sum to greater than 999.

Code:


00 { 134-Byte Prgm }
01▸LBL "cbsum"
02 9ᴇ-3
03▸LBL 01
04 ENTER
05 IP
06 3
07 Y↑X
08 STO IND ST Y
09 R↓
10 ISG ST X
11 GTO 01
12 1.009
13 STO 10
14 7ᴇ-3
15 STO 11
16 7ᴇ-3
17 STO 12
18 14
19 STO 13
20▸LBL 02
21 RCL IND 10
22 RCL IND 11
23 +
24 RCL IND 12
25 +
26 CF 01
27 RCL 10
28 IP
29 100
30 ×
31 RCL 11
32 IP
33 10
34 ×
35 +
36 RCL 12
37 IP
38 +
39 X≠Y?
40 GTO 05
41 STO IND 13
42 1
43 STO+ 13
44▸LBL 05
45 ISG 12
46 GTO 02
47 7ᴇ-3
48 STO 12
49 ISG 11
50 GTO 02
51 7ᴇ-3
52 STO 11
53 ISG 10
54 GTO 02
55 14
56 RCL 13
57 1
58 -
59 1ᴇ3
60 ÷
61 +
62 STO 13
63▸LBL 03
64 RCL IND 13
65 ISG 13
66 GTO 03
67 STOP
68 END

[RMollov]

Code:


00 { 82-Byte Prgm }
01▶LBL "AN"
02 2.002
03 STO 02
04 99.999
05 STO 00
06▶LBL 00
07 ISG 00
08 GTO 01
09 GTO 02
10▶LBL 01
11 RCL 00
12 IP
13 STO 01
14 100
15 ÷
16 XEQ 03
17 XEQ 03
18 3
19 Y^X
20 +
21 +
22 RCL 01
23 X≠Y?
24 GTO 00
25 ISG 02
26 X<>Y
27 STO IND 02
28 GTO 00
29▶LBL 03
30 FP
31 LASTX
32 IP
33 RCL× ST X
34 RCL× ST L
35 X<>Y
36 10
37 ×
38 RTN
39▶LBL 02
40 RCL IND 02
41 DSE 02
42 GTO 02
43 END

00 { 21-Byte Prgm }
01▶LBL "VV"
02 TIME
03 LSTO "t"
04 XEQ "AN"
05 TIME
06 RCL "t"
07 HMS-
08 END

DM42 version ~same as some of the above 1:38" plugged, 3:37" on batts with a chance to see the flying goose (a few more labels) Dave's goes for 0:34 plugged 0:82 on batts

Cheers all

[RMollov]

Just by looking at your code I noticed some questionable steps

(09-30-2019 03:15 AM)Craig Bladow Wrote:  I used Dave's timing program to time my entry to the programming contest at HHC 2019.

It runs in 1.4 seconds on a DM42 running on battery.

The program reduces the search space to 8*8*8 by not evaluating some combinations that would sum to greater than 999.

Code:


00 { 134-Byte Prgm }
01▸LBL "cbsum"
02 9ᴇ-3
03▸LBL 01
04 ENTER
05 IP
06 3
07 Y↑X
08 STO IND ST Y
09 R↓
10 ISG ST X
11 GTO 01
12 1.009
13 STO 10
14 7ᴇ-3
15 STO 11
16 7ᴇ-3    @ <not needed, value already in X>
17 STO 12
18 14
19 STO 13
20▸LBL 02
21 RCL IND 10
22 RCL IND 11
23 +
24 RCL IND 12
25 +
26 CF 01
27 RCL 10
28 IP
29 100
30 ×
31 RCL 11
32 IP
33 10
34 ×
35 +
36 RCL 12
37 IP
38 +
39 X≠Y?
40 GTO 05
41 STO IND 13
42 1
43 STO+ 13
44▸LBL 05
45 ISG 12
46 GTO 02
47 7ᴇ-3
48 STO 12
49 ISG 11
50 GTO 02
51 7ᴇ-3
52 STO 11
53 ISG 10
54 GTO 02
55 14
56 RCL 13
57 1
58 -
59 1ᴇ3
60 ÷
61 +
62 STO 13
63▸LBL 03
64 RCL IND 13
65 ISG 13
66 GTO 03
67 STOP   @ <not needed, program stops at END anyway>
68 END

Cheers,

[Claudio L.]

One final RPL version: no loops!

This one is also newRPL specific (sorry, it's what I use, I don't mean to leave anybody out):

Code:


«
  0 9 1 RANGE      @ Make a case-list of numbers 0-9
 3 ^ DUPDUP + +    @ Sum of the cubes of the digits of ALL numbers from 0 to 999
 1 «
    IF DUP NSUB 1 - ≠ NSUB 100 < OR THEN
      DROP 
    END
  »
  DOSUBS           @ And some list processing (remove if Sum()≠ index on the list)
»

Loopless is not faster, mainly because of the overhead of creating the lists, but worth a look as a curiosity. This one runs in 113ms.