HHC 2021 Programming Contests - Surprise !

[Claudio L.]

(10-05-2021 06:38 PM)Gene Wrote:  newRPL would have won the day in person had it been used, for sure... as long as the statements in the procedure were standard and could have been put into a 50g, 48gII, etc. :-)

That's where it gets weird: the exact same code (for example John Keith's code above), running on different platforms would give you different scores. His code is so standard, it can run on an old 48G, the rubber keyed 49g, on a 50g and then newRPL on a 50g or even newRPL on a Prime G1. All giving you different speeds and different scores for the exact same algorithm... I'm glad I'm not the judge :-)

[Gene]

True. At the conference, the two RPL machines were 50g so no problem there.

[Dave Britten]

Just for fun, I did a 71B BASIC implementation of the RPN problem. This should work on a stock 71B with no additional LEX files or modules.

Rather than searching upward one by one, I took the approach of simply "mirroring" the input number to create a palindrome, checking to see if the result is greater than the input, and if it's not, incrementing the value of the left half by 1 and building a palindrome from that instead. Had to do a few tricks to correctly handle cases with input of all 9. It also works correctly for an input of 0, returning 1.

Roughly half of the program is a string-reverse function, and there's room to shave a few more bytes off of this by combining some lines. It's very fast, though. It may look like there's a loop at first glance, but the backward jump should only occur either 0 or 1 times. There is a FOR loop in the string reversal function, of course.

Code:

0010 INPUT X
0020 X$=STR$(X) @ L=LEN(X$) @ N=CEIL(L/2) @ M=FLOOR(L/2)
0030 A$=X$[1,N]
0035 B$=FNR$(A$[1,M])
0040 P=VAL(A$[1,N]&B$) @ IF P>X THEN GOTO 100
0050 A$=STR$(VAL(A$)+1) @ IF LEN(A$)>N THEN M=M+1
0060 GOTO 35
0100 DISP P @ END 
1000 DEF FNR$(S$)
1001 FNR$="" @ IF LEN(S$)=0 THEN END 
1005 DIM T$[LEN(S$)]
1010 T$=""
1020 FOR I=LEN(S$) TO 1 STEP -1
1030 T$=T$&S$[I,I]
1040 NEXT I @ FNR$=T$
1050 END DEF

[Werner]

Just finished my RPN program using the exact same algorithm Dave just explained ;-)
It doesn't use any synthetics or CX commands. The listing is in 42S code, the corresponding 41 code is 88 bytes without the END. Stack-only, of course ;-)
There's probably room for improvement..

Code:

00 { 95-Byte Prgm }
01▸LBL "PAL"
02 FIX 00
03 CF 29
04 CLA
05 ARCL ST X
06 XEQ 14
07 ALENG
08 2
09 MOD
10 X=0?
11 GTO 03
12 CLX
13▸LBL 02
14 +
15 10
16 ÷
17 IP
18 LASTX
19 XEQ 10
20 X>Y?
21 RTN
22 R↓
23 XEQ 14
24 1
25 GTO 02
26▸LBL 03
27 +
28 10
29 %
30 XEQ 10
31 X>Y?
32 RTN
33 R↓
34 XEQ 14
35 1
36 GTO 03
@  add reverse digits of number
37▸LBL 10
38 ENTER
39 FP
40 STO+ ST Z
41 -
42 10
43 STO× ST Z
44 ÷
45 X>0?
46 GTO 10
47 +
48 RTN
@  leading half: abcd -> ab, abcde -> abc
49▸LBL 14
50 STO ST Y
51 ALENG
52 2
53 ÷
54 IP
55 10^X
56 ÷
57 IP
58 END

Cheers, Werner

[Sylvain Cote]

(10-06-2021 05:35 PM)Werner Wrote:  It doesn't use any synthetics or CX commands. The listing is in 42S code, the corresponding 41 code is 88 bytes without the END. Stack-only, of course ;-)

Almost, ALENG is part of X-Functions module (CX built-in).

[Werner]

Ah of course! Silly me. I used to have a CV+X-Functions, perhaps that's why I assumed it to be a standard function..
Cheers, Werner

[Gene]

Delete the RTN and save a byte. :-)

[Craig Bladow]

Here is my second place entry in the HHC 2021 RPN contest. As submitted it was 72 bytes. I removed the STOP at the end so as presented here it is 71 bytes.
My strategy was to get something working, with some efficiency, and then reduce the program size. My approach compared each digit with its match until failure, so it would not spend time reversing the entire number for every candidate. Also only the first odd number of digits, greater than N/2 (N is the number of digits), would be compared.

Very late Saturday I had achieved the first two goals but ran out of time to try any new approaches.

Code:


01▸LBL "PAL"
02 STO 00
03 FIX 00
04 CF 29
05▸LBL 00
06 1
07 STO+ 00
08 RCL 00
09 CLA
10 ARCL ST X
11 ALENG
12 2
13 ÷
14 IP
15 1
16 -
17 X<0?
18 GTO 02
19 1ᴇ3
20 ÷
21 STO 01
22 X<>Y
23 STO 02
24▸LBL 01
25 RCL 02
26 10
27 ÷
28 IP
29 STO 02
30 LASTX
31 FP
32 10

But did I develop the faster solution?

I keyed in David Hayden's excellent first place solution, which is a very elegant and compact program and ran Gene's 15151 test number as input.

The above routine took 16 seconds to find the next palindrome and David's winning solution took 24 seconds, on the same DM41X, in fast mode, on battery power.

So a small consolation!

[C.Ret]

(10-07-2021 10:50 PM)Craig Bladow Wrote:  I keyed in David Hayden's excellent first place solution, which is a very elegant and compact program and ran Gene's 15151 test number as input.

The above routine took 16 seconds to find the next palindrome and David's winning solution took 24 seconds, on the same DM41X, in fast mode, on battery power.

With 15151 as test value, my 57 bytes code takes 0'11"73 to display 15251 on an original HP-41C just because I add a PSE instruction to see progress and a BEEP instruction at end to facilitate time measurement with my watch.
I am really surprise that my modest and ageless HP-41C vintage run faster that today hi-tech SwissMicro instruments !

Code:

01►LBL "PAL  1  STO 03
03►  LBL 01  +  STO 01  PSE  0  RCL 01                                                  // Increment n & show progress
09►  LBL 02  STO Z  10  ST* Z  ST/ T  MOD  +  X<>Y  INT  X>0?  GTO 02                   // Build palindrome of n
20□          RDN  RCL 01  -  STO 02                      X=0?  GTO 04                   // Exit when n is a palindrome  
27►  LBL 03  RCL 01  RCL 02  RCL 03  10^X  MOD           X=0?  ISG 03  GTO 01  GTO 03   // Compute next increment & loop    
37►  LBL 04  RCL 01  BEEP                                                               // Recall palindrome n on stack & beep  
40►.END.                                                                   (( 57 Bytes))

R 01: actual n    R 02: d=palindrome(n)-n       R 03: k=size of next increment
First increment is i=1, at each step d is the difference between n and its palindrome.
If d=0 then n is a palindrome, otherwise, the next increment is i= d MOD 10^k where k is first value so that i≠0

Removing these the instructions PSE and BEEP spare exactly two bytes in code and a bit more than two seconds of running time.

(10-06-2021 05:24 PM)Dave Britten Wrote:  Just for fun, I did a 71B BASIC implementation of the RPN problem. This should work on a stock 71B with no additional LEX files or modules.

Just for fun, I did a BASIC implementation of the RPL problem on a stock HP-71B, not using additional LEX files or JPC ROM module.

Code:

CAT   GOLOMB    S BASIC  108    10/04/21 18:54   (108 Bytes)

10 INTEGER A,B,G(2300) @ REAL S,T @ INPUT A,B @ T=TIME
12 S=1 @ G(1)=1 @ FOR K=2 TO B @ G(K)=1+G(K-G(G(K-1))) @ S=RES*RES+S*(K>A) @ NEXT K
14 DISP S;TIME-T @ BEEP

1 5 -> 27 0'00"33
2 4 -> 17 0'00"26
5 5 -> 9 0'00"33
100 101 -> 882 0'06"44
1000 1500 -> 4884182 1'38"03
2000 2300 -> 5724280 2'30"39


Incidentally, because of natural contradictive mental behavior, I also made a code for the RPL problem on a HP-41C RPN:

Code:

01►LBL "GO  x=y?  FS 02                                             // Flag 2 is a=b indicator 
04          STO 00  1  STO 01  RCL Z  x=y?  FS 01                   // Flag 1 is a=1 indicator
10          EEX -3  ST* 00  *  2  +  X<>Y  CF 00  FC?C 01  XEQ 01   // LOOP1 from k= 2  to a (skip when Flag 1 is set) 
19          X<> 00  X<>Y  INT  ST+ Y  SF 00  FC?C 02  XEQ 01        // LOOP2 from k=a+1 to b (skip when Flag 2 is set)   
26          RCL 00  RTN                                             // recall sum of Golomb's squares & end
    
28►LBL 01   XEQ 02  ISG Y  GTO 01 RTN                               // MAIN LOOP on k (k is stack register .Y)
    
33►LBL 02   RDN  STO Y  INT  STO Z  1  ST- T  X<>Y  RCL IND T       // compute G(k) = 1 + G(k-G(G(k-1))
42          RDN  RCL IND T  -  RDN  RCL IND T  +  STO IND Y         // with successive indirect indices in .T register
49          X^2  FS? 00  ST+ 00  RTN                    ((86 bytes))// Flag 0 is active square summation in R00

Registers:
R00: sum of squares
R01 to R###: G(1) to G(###) where SIZE ### is the memory limit depending of your HP-41 configuration.

Usage: a [ENTER^] b [XEQ][ALPHA]GO[ALPHA] display \( \sum_{k=a}^{b}G^2_k \)

Speed:
1 5 -> 27 0'00"33
1 5 -> 27 0'04"85
2 4 -> 17 0'03"95
5 5 -> 9 0'04"28
100 101 -> 882 1'02"29
1000 1500 -> too few registers
2000 2300 -> too few registers (my HP-41C armed with only two memory modules is limited to SIZE 130

And again, thanks for sharing this contest problems, I learn of few fact by reading all contributions here. I surely have to initiate myself into synthetic programming13 !

EDITED Wed 13-oct 2021: corrected instruction number in last HP-41 code and add bytes count.

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

[3298]

(10-12-2021 03:42 PM)Jeff O. Wrote:  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.

Hey, it's not like we, the remote contestants, are in for anything other than the fuzzy warm feeling of pride and accomplishment. Some of us (and that includes myself) try to show off that we would have beat the on-site folks, by solving the puzzle before the deadline, but other than that the deadline really only exists for those guys, not us.

On that note, I have two questions for the judge:
1. As part of this show-off, I used to write a post containing the BYTES output of my program (size and checksum) before time was up, but this time I was scared away by the unusually sharp reminder to not only refrain from posting code, but also not post questions ... Would the size be too much of a hint to what's achievable, or can I resume that practice next time?
2. What do the on-site RPL entries look like? I'd like to see what algorithm they used: generating the sequence one-by-one (like John Keith), generating it in same-value stretches (like myself), or something entirely different.

[Gene]

Note: ALENG does not violate the rules, as it is part of the extended functions present on the HP-41CX.

[Jeff O.]

(10-12-2021 05:55 PM)Gene Wrote:  Note: ALENG does not violate the rules, as it is part of the extended functions present on the HP-41CX.

Obviously I misunderstood something in the thread. That's great, I hate to be a rule-breaker!

[David Hayden]

(10-04-2021 02:26 AM)Gene Wrote:  Test cases I used for the RPL contest

1 5 -> 27
2 4 -> 17
5 5 -> 9
100 101 -> 882
1000 1500 -> 4884182
2000 2300 -> 5724200

In the last case, shouldn't that be 5724280?

[Jeff O.]

(10-06-2021 05:35 PM)Werner Wrote:  Just finished my RPN program using the exact same algorithm Dave just explained ;-)
It doesn't use any synthetics or CX commands. The listing is in 42S code, the corresponding 41 code is 88 bytes without the END. Stack-only, of course ;-)
There's probably room for improvement..

Hi Werner,
Being an RPN implementation of Dave's method, I was curious about how you did it in fewer steps and bytes than my effort. Of course doing it stack-only helps, eliminating byte- and step-wasting stores and recalls. I'm lazy and usually just store and recall things in registers. (After I get a working program, sometimes I go back and actually see where things go in the stack and try to devise ways to eliminate the use of registers, but have not (yet) done so with my program.) I have not fully dissected your program, but upon loading and running, I did notice that it seems to fail on the "all nine(s)" cases, e.g., entering 9 should yield 11, 99 should give 101, etc. Unless I mis-entered your program, it gives 101 for 9, 1001 for 99, etc. I'm in no way criticizing your effort, your code for these challenges always strike me as marvels of efficiency and cleverness. I assume you simply did not consider these cases. I found them kind of annoying, and handling them was the last thing I added to mine after getting the basic routine to work. I'd be interested in seeing your approach to handling all nine(s) if you care to spend any more time on this problem, which I will understand if you do not.
Jeff

[Werner]

No need to pussyfoot around it: My routine is plain wrong for these cases! Back to the drawing board! Well, once I get back from holiday, that is ;-)
Thanks for pointing it out, Werner

[Jeff O.]

(10-12-2021 05:55 PM)Gene Wrote:  Note: ALENG does not violate the rules, as it is part of the extended functions present on the HP-41CX.

Following up on this, even thought ALENG was "legal", I created a version using "LOG IP...". I was actually able to create a slightly shorter version using LOG IP instead of ALENG, which pleased me, but the pleasure was short-lived as I quickly found that the program failed for an input of zero, declaring "Invalid Data", due to attempting to take the log of zero. Zero was not test number, and the palindromes are defined as positive integers in the rules, so I do not know if zero, or all negative numbers for that matter, were intended to be valid inputs. If so, the correct output for zero or negative would be 1, probably easiest just to add a test, if less than or equal to zero, just output 1. The "count up until palindrome is found" routines would not have this problem with zero, but would presumably have to test for negatives.

[Gene]

Positive integers are > 0. :-) In my rules.

[Jeff O.]

(10-20-2021 12:50 AM)Gene Wrote:  Positive integers are > 0. :-) In my rules.

Well, yes, the palindromes were defined as positive integers. But for the input numbers, the rules only stated that they had to be less than 10^7. Zero and all negative numbers are less than 10^7...

[Gene]

Rats... could have had a really tough test case. lol.

Gene