HHC 2021 Programming Contests - Surprise !

[Jeff O.]

Checking this thread for the first time after sleeping on the problem for several nights, working out an approach, starting to write code on a DM42 a few days ago, then fussing with it intermittently until I got a version that worked on all inputs. I first considered the “add 1, see if it is a palindrome, if not, add one and so on” method, but worried that that method could take a while to run on real machines, and surely there was a better way, so I tried to arrive at a direct approach. Eventually I arrived at the method described by Dave B. (Before checking this thread I assumed that I did not come up with a novel method among this group and was not surprised to see it used.) It took lots of tricks (for me at least) to handle all the cases, e.g. even number of digits vs. odd, all nines. The working version is 74 steps, 127 bytes. But I also used the ALENG instruction which I now see violated the rules* so I would have to replace all of those with LOG IP 1 + sequences. But at least it works and I think would be relatively fast on a real 42s since it is a direct approach with no looping required (except a small number of loops to build the palindromes).

Program listing is below. I may try to correct the above and optimize the code (which is quite clunky, I’m sure), if so I’ll post an updated listing.

High level comments:
Steps 1 through 20 set a flag if the input has an odd number of digits, leaving it clear for an even number, and lops off the rightmost n/2 or (n-1)/2 digits for inputs with an even or odd number of digits, respectively. This leaves an n/2 or (n+1)/2 digit number for even/odd digit inputs. Step 21 calls a subroutine which creates a palindrome by reversing the n/2 digits and tacking on the end for even digit inputs, or reversing the first (n-1)/2 digits and tacking on the end, leaving the rightmost digit (which was the middle digit of the input number) alone for odd-digit inputs. Then compare to the original, if larger, we have succeeded in finding the next largest palindromic number and stop.

If equal or smaller, we have not succeeded, so steps 26 through 49 create the next higher palindromic number by incrementing the rightmost digit of the truncated number and creating a palindrome with the subroutine. It took some fussing to enable the routine to handle the "all nines" cases using the method used for all other inputs. It would be simpler and shorter to simply detect that case and add 2 to the input number to find the next higher palindrome. That seems a little "brute-force-y", not as "elegant" as using the same method for all inputs. But is mathematically valid, and I had to handle them as special cases anyway, so it is probably better. Code for that option is provided in the second code block below.

I will admit to not having studied all entries discussed above in detail, so if I have used any techniques from those routines, I give full credit to the author and acknowledge priority. I also credit Dejan R. for much of the palindrome building subroutine. While cogitating on my approach, I knew that I would need a routine to reverse digits. Then Dejan handily posted a routine to the HHC group that was easily adapted.

I also acknowledge that I worked on it for a week-and-a half, not continuously of course, but not one night as intended for the contest, or the couple of days for other solutions posted above.

edit - slightly improved (2 steps shorter) versions developed before I saw Werner's very nice technique that allowed for a significant improvement detailed in a separate post below.

Code:

00 { 124-Byte Prgm }
01▸LBL "PAL"
02 FIX 00
03 CF 29
04 CF 01
05 CLA
06 STO 01
07 ARCL ST X
08 ALENG
09 2
10 ÷
11 FP
12 X≠0?
13 SF 01
14 X<>Y
15 LASTX
16 IP
17 10^X
18 ÷
19 IP
20 STO 03
21 XEQ 50
22 RCL 01
23 X<>Y
24 X>Y?
25 STOP
26 RCL 03
27 CLA
28 ARCL ST X
29 ALENG
30 X<>Y
31 1
32 +
33 CLA
34 ARCL ST X
35 ALENG
36 RCL ST Z
37 X=Y?
38 GTO 97
39 0.1
40 RCL ST T
41 FS? 01
42 ×
43 FS?C 01
44 GTO 95
45 SF 01
46 GTO 95
47▸LBL 97
48 RCL ST Z
49▸LBL 95
50 XEQ 50
51 STOP
52▸LBL 50
53 0.1
54 RCL× ST Y
55 ENTER
56 FC? 01
57 RCL ST Z
58 IP
59▸LBL 01
60 10
61 STO× ST Z
62 ÷
63 X=0?
64 GTO 00
65 ENTER
66 FP
67 STO+ ST Z
68 -
69 GTO 01
70▸LBL 00
71 R↓
72 END

Version that simply adds 2 for the all nines cases, "only" 67 steps, 108 bytes:

Code:

00 { 108-Byte Prgm }
01▸LBL "PAL"
02 FIX 00
03 CF 29
04 CF 01
05 CLA
06 STO 01
07 ARCL ST X
08 ALENG
09 2
10 ÷
11 FP
12 X≠0?
13 SF 01
14 X<>Y
15 LASTX
16 IP
17 10^X
18 ÷
19 IP
20 STO 03
21 XEQ 50
22 RCL 01
23 X<>Y
24 X>Y?
25 STOP
26 RCL 03
27 CLA
28 ARCL ST X
29 ALENG
30 X<>Y
31 1
32 +
33 CLA
34 ARCL ST X
35 ALENG
36 RCL ST Z
37 X=Y?
38 GTO 97
39 RCL 01
40 2
41 +
42 STOP
43▸LBL 97
44 RCL ST Z
45 XEQ 50
46 STOP
47▸LBL 50
48 0.1
49 RCL× ST Y
50 ENTER
51 FC? 01
52 RCL ST Z
53 IP
54▸LBL 01
55 10
56 STO× ST Z
57 ÷
58 X=0?
59 GTO 00
60 ENTER
61 FP
62 STO+ ST Z
63 -
64 GTO 01
65▸LBL 00
66 R↓
67 END

* - Correction, ALENG does not violate the rules, see Gene's post below.