+- 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 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL (/thread-18792.html)
HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Gene - 09-11-2022 01:30 AM
Palindromic numbers read the same forwards and backwards. For example, 66, 121, 79497, etc.
Problem Description: If you add any positive integer to the integer formed by reversing its digits, then repeat the process with the resulting sum, and keep repeating this loop... will you eventually reach a sum that is palindromic?
Input: a non-decimal number between 1 and a 10-digit number on the RPN machine or between 1 and a 12-digit number on the RPL machine.
Output: Two items: The resulting palindromic number and the number of additions / cycles required to reach it. Place the number in stack level 1 (or X) and number of cycles in level 2 (or Y). If the input number does not reach a palindromic sum within 50 cycles or if an intermediate sum exceeds the digit capacity of the machine being used (10 digits on the HP-41 or 12 digits on the RPL class machines), return a 0 in level 1 (X) and 0 in level 2 (Y). If it is going to overflow the non-scientific notation capacity of the machine, return a 0 in both stack levels.
Winning routine:
Smallest BYTE routine that solves the input cases. If something takes forever in the judge’s mind to run, it can be eliminated at the judge’s sole discretion.
Sample Cases:
(A) 51. This turns into 66 in one step. 51+15 which is palindromic. Output is 66 in X and 1 in Y.
(B)59. This turns into 1111 in 3 steps. 59+95=154. 154+451=605. 605+506=1111. Output is 1111 in X and 3 in Y.
(C) 99. This reaches the palindromic value of 79497 in six steps. Output is 79497 in X and 6 in Y.
Machines Eligible:
RPN: Any machine running vanilla HP-41CX functionality. If a function isn’t in the HP-41CX it is not eligible.
RPL: The HP-50G built-in functionality, no libraries attached, nothing extra. Vanilla.
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - John Keith - 09-11-2022 01:17 PM
(09-11-2022 01:30 AM)Gene Wrote: RPL: The HP-50G built-in functionality, no libraries attached, nothing extra. Vanilla.
Point of clarification: is it permissible to use the built-in Library 256?
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Gerson W. Barbosa - 09-11-2022 03:32 PM
Perhaps the hp 50g should not be limited to only 12 digits.
20341615628 →
30
4679302882662882039764
Nice late night entertainment. Thank you!
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Roland57 - 09-11-2022 06:28 PM
Hi Gene,
my quick solution for the hp67 takes 65 steps. I hope it fullfils all requirements.
regards
Roland
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Gene - 09-11-2022 06:54 PM
(09-11-2022 01:17 PM)John Keith Wrote:(09-11-2022 01:30 AM)Gene Wrote: RPL: The HP-50G built-in functionality, no libraries attached, nothing extra. Vanilla.
Point of clarification: is it permissible to use the built-in Library 256?
Gene: No libraries of any kind. Built in or not. :-)
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Gene - 09-11-2022 06:55 PM
(09-11-2022 06:28 PM)Roland57 Wrote: Hi Gene,
my quick solution for the hp67 takes 65 steps. I hope it fullfils all requirements.
regards
Roland
Gene: I had specifically asked that no responses / solutions be posted until tomorrow.
?
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Roland57 - 09-11-2022 07:20 PM
(09-11-2022 06:55 PM)Gene Wrote:sorry, I have to apologize, I missed that ! I removed the picture.(09-11-2022 06:28 PM)Roland57 Wrote: Hi Gene,
my quick solution for the hp67 takes 65 steps. I hope it fullfils all requirements.
regards
Roland
Gene: I had specifically asked that no responses / solutions be posted until tomorrow.
?
Roland
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - 3298 - 09-11-2022 09:11 PM
No libraries at all sounds hard ... because quite a few built-in commands are from libraries!
For instance, HEAD and TAIL are commands 81 and 82 in library 171. Such builtin library commands make an unnecessary (in my opinion, anyway) minefield out of this challenge.
Conversely, flash pointers are no problem, right? :-) E.g. instead of CRLIB from L256 (deliberately showing a useless-for-this-purpose command to avoid giving hints) I could do #AD002h FLASHEVAL (which is called by CRLIB and implements its core functionality), it's just harder to understand, slightly slower, and significantly bigger (13 bytes for the binary integer + 2.5 bytes for the FLASHEVAL command; same size calculation applies to SYSEVAL and LIBEVAL, though the latter obviously calls libraries). I believe especially the latter should be enough of a penalty, considering the scoring criteria. For reference: a ROMPTR (i.e. library call) generated by the compiler takes 5.5 bytes, a FPTR 6 bytes, and a normal PTR takes the 2.5 bytes we all know about.
---
Unrelated to the above: when I asked via PM, Gene confirmed that sample (C) showcases how you're supposed to start adding even if the input is already a palindrome. That is, the number of iterations shall only be 0. in the explicitly specified error conditions. I assumed that to be a mistake, but it is intentional.
That's actually nice, because DO ... UNTIL ... END is 2.5 bytes smaller than WHILE ... REPEAT ... END (assuming that flipping the condition is free, which it is in my program).
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Gerson W. Barbosa - 09-11-2022 10:18 PM
(09-11-2022 09:11 PM)3298 Wrote: No libraries at all sounds hard ... because quite a few built-in commands are from libraries!
For instance, HEAD and TAIL are commands 81 and 82 in library 171. Such builtin library commands make an unnecessary (in my opinion, anyway) minefield out of this challenge.
On the other hand Gene says "RPL: The HP-50G built-in functionality, no libraries attached, nothing extra. Vanilla."
To my knowledge, HEAD and TAIL are available since the HP-28S (C?). I think the restriction refers to third-party libraries and pure RPL (no SysRPL, no Assembly).
Mine doesn’t comply to Gene’s final requirements, except for the 50 cycle limitation. Despite this simplification, the byte count is around 200. I’d tried to replace the initial DO UNTIL END structure with WHILE REPEAT END, but that only made it slower and longer. The 30-step example takes 22 seconds, which doesn’t appear too long for me, though. The 6-step sample cases takes about 1.7 seconds.
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Gene - 09-12-2022 02:43 AM
If you have to ATTACH a library, then it is not allowed.
Winning RPL entry at the conference did not use anything like that.
Remember, the purpose is to enjoy and learn ! :-)
Not trying to create any stress.
Gene
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Gerson W. Barbosa - 09-12-2022 03:18 AM
(09-12-2022 03:02 AM)C.Ret Wrote:(09-11-2022 01:30 AM)Gene Wrote: Output: Two items: The resulting palindromic number and the number of additions / cycles required to reach it. Place the number in stack level 1 (or X) and number of cycles in level 2 (or Y). If the input number does not reach a palindromic sum ...
What is the expected results for 323: (a) Y:0 X:323 or (b) Y:4 X:7337 ?
Y: 1
X: 646
323 + 323 = 646 (a palindrome, so stop)
Notice you have to make at least one addition, no matter the input is a palindrome or not. See test case number 3 which is a palindrome (99).
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - C.Ret - 09-12-2022 04:18 AM
(09-12-2022 03:18 AM)Gerson W. Barbosa Wrote:(09-12-2022 03:02 AM)C.Ret Wrote: What is the expected results for 323: (a) Y:0 X:323 or (b) Y:4 X:7337 ?
Y: 1
X: 646
323 + 323 = 646 (a palindrome, so stop)
Notice you have to make at least one addition, no matter the input is a palindrome or not. See test case number 3 which is a palindrome (99).
Thank you for your help.
In the meantime, I delete my previous post, the example was wrong, I mix with input of 646 that lead to 7337. As you point me out, the third example given by gene with 99 answer my question!
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - 3298 - 09-12-2022 09:58 AM
(09-11-2022 10:18 PM)Gerson W. Barbosa Wrote: To my knowledge, HEAD and TAIL are available since the HP-28S (C?). I think the restriction refers to third-party libraries and pure RPL (no SysRPL, no Assembly).Well, that's the sticking point, L256 is a built-in library since the 49g, as built-in as L171 with HEAD and TAIL. You can't uninstall it, unlike EQLIB and PRTBL (which on a new 50g are preinstalled in the user-owned section of flash).
I presume it's not attached by default to "make things easier for the novice user", i.e. basically the same reasoning that got us the stupid algebraic mode as default. At this point, running 256. ATTACH at startup should be as automatic for a power-user as doing -62. SF (if you don't recognize the flag number, that's USR keyboard mode) or, well, the key sequence [MODE] [+/-] [ENTER] after a reset with memory loss (the quick path to RPN mode).
Granted, a number of L256 commands are an acquired taste, but SREV is genuinely useful for a variety of programs. This particular command is likely why we keep making so much noise about L256. (Actually, I am looking at a different command which is squarely in the "acquired taste" category ... you'll see which when I'm allowed to post the program.)
Also, HEAD and TAIL came in the 48G/GX. The 28C, 28S, and 48S/SX didn't have covered ROM, so there was no need to use ROMPTRs for builtin commands yet. That changed in the 48G/GX.
(Oh, and I'd like to dispute your notion that SysRPL isn't pure RPL. Nobody said "UserRPL only".)
---
Aaanyway, staking my claim: 171. bytes, #DA9Dh with a L256 command in it, or 184. bytes, #919Ah with the FLASHEVAL workaround instead. Execution time is basically instant for all inputs I've tried, and that includes one that overflows the 12 digit limit in the 10th iteration. (The number is 14327287. if you want the same stress-test. No significance to it, I got it by randomly punching digits.)
Another tidbit I stumbled into along the way: LIBEVAL and FLASHEVAL are themselves ROMPTRs, so the size penalty for them is another 3.5 bytes bigger than the calculation in my previous post says (though it was correct for SYSEVAL). The library they are from is also L171 - I already posted HEAD and TAIL as examples from it, but have a few more: DOLIST, DOSUBS, STREAM, REVLIST, SEQ, RREF, INFORM, CHOOSE, MSOLVR. Lots of 48G/GX commands in there. This is the minefield I alluded to.
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Gerson W. Barbosa - 09-12-2022 11:52 AM
(09-12-2022 09:58 AM)3298 Wrote: (Oh, and I'd like to dispute your notion that SysRPL isn't pure RPL. Nobody said "UserRPL only".)
---
Aaanyway, staking my claim: 171. bytes, #DA9Dh with a L256 command in it, or 184. bytes, #919Ah with the FLASHEVAL workaround instead. Execution time is basically instant for all inputs I've tried, and that includes one that overflows the 12 digit limit in the 10th iteration. (The number is 14327287. if you want the same stress-test. No significance to it, I got it by randomly punching digits.)
You are right about SysRPL, indeed “UserRPL only” isn’t anywhere in the rules. Sorry for my misinterpretation.
Here 201.5 bytes in two parts:
# D4FBh, 120 bytes and # 7CCBh, 81.5 bytes.
These include HEAD and TAIL, which prior to your first post I had no idea they were from a built-in library (thanks for the enlightenment!). Anyway, mine wouldn’t be a valid submission, since it doesn’t fully stick to rules.
Definitely, much easier with RPL and the HP 50g, when compared to RPN.
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - John Keith - 09-12-2022 11:52 AM
(09-12-2022 09:58 AM)3298 Wrote: Well, that's the sticking point, L256 is a built-in library since the 49g, as built-in as L171 with HEAD and TAIL. You can't uninstall it, unlike EQLIB and PRTBL (which on a new 50g are preinstalled in the user-owned section of flash).
I presume it's not attached by default to "make things easier for the novice user", i.e. basically the same reasoning that got us the stupid algebraic mode as default. At this point, running 256. ATTACH at startup should be as automatic for a power-user as doing -62. SF
I agree with 3298's reasoning and in fact, you don't even have to formally "attach" Library 256, just set flag -86 and do a warm start.
In the spirit of rebellion, I am posting my program for the 50g which uses one Library 256 command, even though it does not qualify. 124.5 bytes, it assumes exact mode and flag -86 set.
Code:
Spoiler alert!
\<< 0. SWAP R\->I @ Insure that n is exact and zero counter
DO DUP \->STR SREV OBJ\-> + @ Reverse and add
SWAP 1. + SWAP @ Increment counter
UNTIL DUP2 SIZE 12. > SWAP 50. > OR @ Greater than 12 digits or 50 steps?
{ DROP2 0. DUP 1. } @ Then replace with two zeros
{ DUP \->STR DUP SREV SAME } @ Else test if palindrome
IFTE
END
\>>RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Gerson W. Barbosa - 09-12-2022 12:01 PM
Code:
DIR
HHC
« R→I -105 CF 0 SWAP
DO H ∑LIST OBJ→ SWAP ∑LIST OBJ→ + SWAP 1 + SWAP DUP H
UNTIL == PICK3 50 ≥ OR
END OVER 50 == { DROP2 0 DUP } IFT
»
H
« →STR { "0" } 1 PICK3 SIZE
START OVER HEAD + SWAP TAIL SWAP
NEXT NIP "0" OVER TAIL REVLIST +
»
ENDRE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Bernd Grubert - 09-12-2022 12:27 PM
Hi Gene,
Thanks for the interesting contest.
Here's my solution for the HP-41CX. It uses 78 bytes without the alpha label at the beginning.
No registers used.
I have added a new version "P2" which is 8 bytes (length is now 70 bytes) shorter and should be nearly two times faster. I replaced some of the x=0 with x=y tests, which allowed me to remove some stack clean-up code and eliminated one of the palindrom generations.
Regards
Bernd
Edit: added register usage.
Edit: added new version
Code:
01◆LBL "P"
02 FIX 0
03 CF 29
04 .05
05 X<>Y
06◆LBL 03
07 XEQ 02
08 +
09 ENTER↑
10 ENTER↑
11 DSE X
12 -
13 X=0?
14 GTO 04
15 RDN
16 XEQ 02
17 X<>Y
18 -
19 LASTX
20 X<>Y
21 ISG Z
22 X=Y?
23 GTO 04
24 X≠0?
25 RDN
26 X≠0?
27 GTO 03
28 RDN
29 X<>Y
30 INT
31 X<>Y
32 RTN
33◆LBL 04
34 CLX
35 ENTER↑
36 RTN
37◆LBL 02
38 ENTER↑
39 CLA
40◆LBL 00
41 10
42 /
43 FRC
44 10
45 ST* Y
46 RDN
47 ARCL X
48 RDN
49 LASTX
50 INT
51 X=0?
52 GTO 01
53 GTO 00
54◆LBL 01
55 RDN
56 ANUM
57 ENDVersion P2:
Code:
01◆LBL "P2"
02 FIX 0
03 CF 29
04 ,05
05 X<>Y
06 XEQ 02
07◆LBL 03
08 +
09 ENTER↑
10 DSE X
11 X=Y?
12 GTO 04
13 RDN
14 ISG Y
15 X=0?
16 GTO 04
17 XEQ 02
18 X≠Y?
19 GTO 03
20 RDN
21 X<>Y
22 INT
23 X<>Y
24 RTN
25◆LBL 04
26 CLX
27 ENTER↑
28 RTN
29◆LBL 02
30 ENTER↑
31 CLA
32◆LBL 00
33 10
34 /
35 FRC
36 10
37 ST* Y
38 RDN
39 ARCL X
40 RDN
41 LASTX
42 INT
43 X=0?
44 GTO 01
45 GTO 00
46◆LBL 01
47 RDN
48 ANUM
49 ENDRE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - ThomasF - 09-12-2022 12:41 PM
Hi,
An RPN solution for the 41 system (C/CV/CX/X).
The code assumes nothing except that the statistical registers are at the default location.
With only local labels I get the count to 58 bytes (47 without overflow check ...).
193 XEQ A -> X: 233332 Y: 8
4884 XEQ A -> X: 8836886388 Y: 13
Cheers,
Thomas
(Edit: Added line numbers )
(Edit again: Missed the small detail about overflow!)
Code:
Code below ...
01◆LBL A Entry point to the routine
02 CLΣ x . . . Clear registers used
03 STO 11 x . . . Save (as sum in reg 11)
04◆LBL 00 x . . .
05 XEQ 01 x' . . . Reverse the register 11
06 Σ+ n . . . Add to sum (reg 11)
07 XEQ 01 x' . . . Reverse the sum
08 RCL 11 x x' . . Recall the original number
09 1 E10 OV x x' . Check for overflow ...
10 X<=Y?
11 GTO 03 Bail out ...
12 RDN x x' . .
13 X!=Y? x x' . . If different it is not a palindrom
14 GTO 00 x x' . . ... then loop again
15 RCL 16 n x x' . Recall the number of loops (N)
16 X<>Y x n x' . Fix stack
17 RTN Done!
18◆LBL 03
19 CLST
20 RTN 0 0 0 0 Overflow!
21◆LBL 01 . . . . Subroutine to return the reverse of register 11
22 CLST 0 0 0 0 Init stack
23 10 10 0 0 0
24 X<>Y 0 10 0 0
25 RCL 11 x 0 10 0
26◆LBL 02
27 ENTER x x r 10
28 RUP 10 x x r
29 MOD t x r r Get least significant digit
30 LASTx 10 t x r
31 ST* T 10 t x r' Shift the result
32 ST/ Z 10 t x' r' Shift the original number
33 X<> T r' t x' 10
34 + r" x' 10 10 Add LSD to the result
35 X<>Y x' r" 10 10
36 INT x" r" 10 10 Remove LSD from original number
37 X!=0? x" r" 10 10 Anything left to shift?
38 GTO 02 x" r" 10 10 ... yes, then loop again
39 RDN r" 10 10 x" Return the reversed result
40 ENDRE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - 3298 - 09-12-2022 12:49 PM
(09-12-2022 11:52 AM)John Keith Wrote: I agree with 3298's reasoning and in fact, you don't even have to formally "attach" Library 256, just set flag -86 and do a warm start.Ohh right, I keep forgetting about that flag because it's one of those omitted from the built-in flag browser. Thanks!
---
Well, all "central" times (Australian, European, North American) have progressed past 6:00, and other programs have shown up, time for my program:
Code:
\<<
0. SWAP
\<<
DUP # A5002h FLASHEVAL
9. 20. SUB
"." + OBJ\->
\>>
\-> r \<<
DO
r EVAL +
SWAP 1. + SWAP
UNTIL
IF
DUPDUP 1. + ==
PICK3 50. >
OR
THEN
DROP2 0. 0.
1.
ELSE
r EVAL OVER ==
END
END
\>>
\>>The subprogram containing this workaround is responsible for reversing the digits of a number. \->H is handy here: a real number has its digits (for both mantissa and exponent) stored in BCD, little endian (= backwards, just like we need). I merely need to lop off the prolog, exponent, and mantissa sign. The digit sequence may contain formerly-trailing now-leading zeroes, but OBJ\-> happily ignores them. I only need to tell it to make a real number by appending ".", otherwise an exact integer will pop out if the user has exact mode on.
This part is a subprogram because it's used in two places: adding the reversed onto the original, and checking for a palindrome (the latter is implemented as an equality check between reversed and original).
The only other remotely noteworthy piece is how I implemented the error conditions:
- an overflow is tested for by checking if adding 1. changes the number at all or if it gets swallowed by rounding to 12 significant digits;
- testing for 50 iterations takes place after the addition, so in the unlikely case it gets triggered there will be a 51st addition, and its result will be discarded. This is merely a performance concern, it doesn't affect the correctness of the results.
A variant with exact integers could be made from this as well. The obvious changes are tossing the overflow check, skipping the piece appending "." to the string given to OBJ\->, and doing R\->I at startup. The non-obvious one is that the arguments to the SUB command extracting the reversed digits from the output of \->H will have to be adjusted to the in-memory format of an exact integer: 11. OVER SIZE 1. - SUB should do the trick.
PS: come to think of it, appending "." is not necessary at all, because adding an exact integer onto a real produces a real anyway. Omitting "." + saves 8.5 bytes, bringing my program down to 175.5 bytes, #C11Ah with the L256 workaround or 162.5 bytes, #1EBAh without.
RE: HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL - Werner - 09-12-2022 01:51 PM
My first try, 41-compatible, needs 1 register (00 here)
41: 42 bytes without LBL and END.
42-Style listing:
Code:
00 { 54-Byte Prgm }
01▸LBL "HHC2022"
02 STO 00
03 STO- 00
04 XEQ 10
05▸LBL 03 @ main loop
06 +
07 XEQ 10
08 ISG 00
09 X<>Y
10 X≠Y?
11 GTO 03
12 RCL 00 @ end
13 X<>Y
14 RTN
15▸LBL 10 @ reverse number X -> revX X
16 ENTER
17 ENTER
18 -
19 10
20 LASTX
21▸LBL 02
22 %
23 FP
24 STO+ ST Z
25 R↓
26 STO× ST Y
27 LASTX
28 IP
29 X≠0?
30 GTO 02
31 R↓
32 R↓
33 ENDCheers, Werner