HHC 2022 - Programming Contest - no responses until after 6am Monday 6am CENTRAL

[Gene]

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.

[John Keith]

(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?

[Gerson W. Barbosa]

Perhaps the hp 50g should not be limited to only 12 digits.

20341615628 →

30
4679302882662882039764

Nice late night entertainment. Thank you!

[Roland57]

Hi Gene,

my quick solution for the hp67 takes 65 steps. I hope it fullfils all requirements.

regards
Roland

[Gene]

(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. :-)

[Gene]

(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.

?

[Roland57]

(09-11-2022 06:55 PM)Gene Wrote:  

(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.

?

sorry, I have to apologize, I missed that ! I removed the picture.

Roland

[3298]

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).

[Gerson W. Barbosa]

(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.

[Gene]

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

[Gerson W. Barbosa]

(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).

[C.Ret]

(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!

[3298]

(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.

[Gerson W. Barbosa]

(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.

[John Keith]

(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
\>>

[Gerson W. Barbosa]

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 +
  »
END

[Bernd Grubert]

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 END

Version 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 END

[ThomasF]

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 END

[3298]

(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
  \>>
\>>

184. bytes, #919Ah as shown. The FLASHEVAL with the binary number before it runs the internal part of \->H (without checking for the presence of an argument). That's the L256 workaround, and replacing it with \->H itself shrinks it to 171. bytes, #DA9Dh.
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.

[Werner]

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 END

Cheers, Werner