HHC 2021 Programming Contests - Surprise !

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