+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: HHC 2019 will be in Reno, Nevada, Sept 21-22 (/thread-12772.html)
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Eric Rechlin - 09-24-2019 07:06 PM
(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.
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Jake Schwartz - 09-24-2019 07:54 PM
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
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Brian Walsh - 09-25-2019 01:04 AM
(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.
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Gerson W. Barbosa - 09-25-2019 01:53 AM
(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
»RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Jeff O. - 09-25-2019 07:26 PM
(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.)
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - David Hayden - 09-26-2019 05:33 PM
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 ENDRE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - jjohnson873 - 09-27-2019 04:48 PM
(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!
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - David Hayden - 09-27-2019 09:31 PM
(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.
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - jjohnson873 - 09-27-2019 09:59 PM
(09-27-2019 09:31 PM)David Hayden 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!(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.
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Claudio L. - 09-27-2019 11:07 PM
(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
»RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - jjohnson873 - 09-28-2019 12:44 AM
(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.
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Albert Chan - 09-28-2019 01:26 AM
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 XNote: 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
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Jeff O. - 09-28-2019 04:37 PM
(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.
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - David Hayden - 09-28-2019 04:38 PM
(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
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - David Hayden - 09-28-2019 04:45 PM
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.
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Claudio L. - 09-29-2019 04:08 PM
(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.
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Craig Bladow - 09-30-2019 03:15 AM
(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 ENDRE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - RMollov - 09-30-2019 03:56 AM
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 ENDCheers all
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - RMollov - 09-30-2019 05:13 AM
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,
RE: HHC 2019 will be in Reno, Nevada, Sept 21-22 - Claudio L. - 09-30-2019 04:15 PM
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.