HHC 2021 Programming Contests - Surprise !

[Gene]

Many years, people have said they wish they had more time to try the programming contests.

Here you go. Coding can start now. Entries at the conference are going to be due early Sunday afternoon, exact time TBD.

If you are remote, do NOT post any programs until after 6pm CENTRAL USA time Sunday please. Also please do ** not ** post questions to the list. Your question may help someone else get the answer.

Enjoy. RPL and RPN files attached.

[Paul Dale]

Interesting....

Pauli

[sjthomas]

Gene does not have internet access at the moment, so has asked me to post:

“Solutions may now be posted. The winning RPN solution was 40 bytes, and the winning RPL entry was 128.5 bytes.”

Go forth and program!!

sjthomas

[Didier Lachieze]

[Edited according to the comments from Gene, here]

My RPN solution in 35 bytes (31 bytes if the 41 is configured with FIX 0 and CF 29, and you remove these two instructions before LBL 01):

Code:

00 { 35-Byte Prgm }
01▸LBL "PAL"    // Program must be called PAL
02 FIX 0        // FIX 0 and CF 29 needed to ensure ARCL will put only 
03 CF 29        //  the value of X without decimals nor separators in Alpha
04▸LBL 01
05 1
06 +            // Start looking for palindrome from the next number
07 CLA          // Clear Alpha register
08 ARCL ST X    // Put current number in Alpha (up to 7 digits as the number is < 10^7)
09 SF 25        // Set error flag to ensure next error will not stop the program
10 1            // One byte value as key code for PASN, it will not be used and is invalid 
11 PASN         // This instruction has been chosen as it will put up to seven characters
                //  of the function name in Alpha into the scratch register Q in reverse order
                //  so reversing the digits of the number we put in Alpha at step 08.
                // The number in Alpha is searched within the existing functions and program names,
                //  as it is not found it should generate a NONEXISTENT error message,
                //  but it doesn't since flag 25 is set. If there was a global label identical to the
                //  name in Alpha, the invalid keycode in X ensures no assignment is done, and flag 25
                //  ensures that the execution continues.                
12 RCL Q        // Recall the reversed number (in alphanumeric form)
13 STO M        // Store it in the first 7 characters of Alpha, replacing the previous value
14 ANUM         // Convert the reversed number in Alpha to it's numerical value in X
15 R^           // Get the initial number
16 X≠Y?         // Compare it to it's reversed form 
17 GTO 01       // If the two numbers are different, it's not a palindrome, goto next number
18 END          // The two numbers are identical, we have found the next palindrome

There are two synthetic instructions at step 12 and 13 that I've entered with the Zenrom module as this is one of the simplest way to enter synthetic instructions.

This program is pretty slow as for each loop there is a search for a non existent label but it works for input numbers less than 10^7 as specified for the contest.

It is based on the REV program in the Q-loader section of Wickes' Synthetic Programming book, page 57, where I've saved a few bytes by using PASN instead of GTO IND M.

Code:

01 LBL "REV"
02 ASTO M
03 SF 25
04 GTO IND M
05 RCL Q
06 STO M
07 END

The program REV uses the fact that the Q register is used as a scratch register by the 41 OS to store - in reverse order - strings that are usually entered by the user, for example as functions names. The program REV uses 'GTO IND M' to avoid having the user entering the string, but this GTO IND requires the label name to be first ASTO'ed in a register (here M is used, the first register of Alpha), so only strings of 6 characters can be used as the first byte in the register is used to indicate that the register contains a string and not a number.

To be able to reverse 7 digits numbers I initially used ATOX and XTOA:

Code:

01 LBL "REV"
02 ASTO M
03 SF 25
04 ATOX
05 GTO IND M
06 RCL Q
07 STO M
08 X<>Y
09 XTOA
10 RDN
11 END

Then I looked at the different functions of the 41CX that use a user-entered string, and found that with PASN which uses a string in Alpha the Q register was directly loaded with 7 digits from the Alpha register in reverse order, so no more need for ASTO, nor ATOX and XTOA.

Reference: Sections 4B. THE ALPHA REGISTER, p31, 4C. REGISTER Q, p33 and 5I. The Q-LOADER, p55 in Synthetic Programming on the HP-41C by W.C. Wickes.

[3298]

Well, I had enough time available on Saturday to get multiple variants into a working and somewhat optimized state before noon, with finishing touches in the evening. But that may be because I'm not an on-site parrticipant, so I don't have HHC panels demanding my attention...

Anyway, the scoring criteria (particularly the time elapsed on an unspecified "sample test problem") mean that I don't know what to optimize for. In UserRPL I have a pretty slow one that gets below the threshold where only the size matters, and a much faster one that comes in at exactly 100 bytes (that's enough for the timing branch of the scoring procedure, right? Because it says "if less than 100 bytes", not "if less than or equal to 100 bytes"), meaning that if the sample input is small, it can take advantage of a sub-second time to get a good score. In SysRPL I ended up with just one real variant (which predictably wipes the floor with the UserRPL version) because the fast one is so small already. For the same scoring reasons as in UserRPL, I simply padded it to just barely break the threshold, though if the sample input is large enough to make the calculation take more than about 0.7_s, that may be a liability.

The general approach is the same across all variants: generate a long enough portion of the Golomb sequence, cut it to the requested range, then square the elements and sum them up. I can't avoid generating the starting portion of the sequence (from 1. to L) even if the inputs make me drop that part afterwards, because the definition makes the later elements depend on the earlier ones.

Note that for valid inputs (1. <= L < R < 1.E4) the sum can only reach about 5.7E8 (568210755. to be exact), so the requirement to calculate in mod 1.E9 can be safely ignored, just add the numbers up normally. Nice bit of misdirection there.

It's obvious (to me, anyway) that the Golomb sequence consists of groups of multiple consecutive same-magnitude numbers, so I went for an algorithm that generates a whole group in on go. As the definition makes clear, the length of the group can be looked up in the already-generated part of the sequence; the NDUPN command takes it from there. Compared to the straightforward method of generating one element at a time, this is much quicker, and it also saves some commands for figuring out if an element needs to be the same as the previous one or 1 greater (i.e. part of the same group or not). There is a possibility that this approach slightly overruns the upper limit requested via the R input, but cutting the sequence to the appropriate range with the right command gives me safety on that end for free.

In UserRPL there are two choices: generate the sequence in list form (smaller, by avoiding some of the other choice's stackrobatics), or generate it as what SysRPL programmers call a "meta", i.e. an exploded list (significantly faster by avoiding repeatedly copying already-generated elements to a new list). Cutting the sequence is best done with SUB which needs a list instead of a meta, but after this forced conversion to a list I once more have the choice between the short snippet making use of automatic list processing, or the fast snippet which explodes the list again and processes the elements one by one with an explicit loop. The latter is faster by avoiding creation of another intermediate list.

The code:
- short (85.5 bytes, #27CFh), \GS is the trigraph for uppercase sigma:

Code:

\<<
  { 1. 2. 2. }  @ initial piece of the sequence, necessary to for prior-element lookups while generating more elements
  4. PICK3 START  @ I let the loop counter run 1 ahead of the length of the sequence so it stops if the length reaches the R input exactly
    DUPDUP SIZE GET  @ last list element, please
    1. +
    DUP2 GET  @ look up how many times the new element repeats
    UNROT PICK3  @ save a copy of the count away above the sequence
    NDUPN \->LIST +  @ append the correct number of new elements to the sequence, newRPL would need ADD in place of + here
  SWAP STEP  @ advance the loop counter by the number of new elements
  UNROT SUB  @ cut away the parts outside the requested range
  SQ \GSLIST  @ square and sum up
\>>

- fast (100 bytes, #E141h):

Code:

\<<
  1. 2. 2.  @ initial piece of the sequence, necessary to for prior-element lookups while generating more elements
  3.  @ length of the exploded list
  4. 6. PICK START  @ I let the loop counter run 1 ahead of the length of the sequence so it stops if the length reaches the R input exactly
    OVER  @ last list element, please
    1. +
    DUP2 - 3. + PICK  @ look up how many times the new element repeats
    NDUPN  @ generate the correct number of new elements for the sequence
    DUPDUP 3. + ROLL +  @ retrieve the old sequence's length and add it onto a copy of the length of the new group
  SWAP STEP  @ advance the loop counter by the number of new elements
  \->LIST UNROT SUB LIST\->  @ cut away the parts outside the requested range
  0.  @ initial value for the sum
  1. ROT START  @ for each element in the range ...
    SWAP SQ +  @ ... pull up the element, square it, and add it onto the sum
  NEXT
\>>

In SysRPL there are few commands that support automatic list processing (basically only the UserRPL commands, because UserRPL is strictly a subset of SysRPL), and we have better support for handling metas instead. That means lists are doomed, metas are the way to go. Covering the other branch of the scoring criteria is achieved by adding one line that pushes a string and immediately drops it; its only purpose is to make the program big enough.

There is another quirk of this implementation, connected to the initial piece of the sequence. In the UserRPL programs I supplied the group of 2s so I don't get what would amount to an out-of-bounds read when looking up that I need two 2s while generating that group. In SysRPL I supply only the 1 at the start of the sequence, and let the out-of-bounds read hit the meta length. That should rightfully be 1 at the relevant moment, leading to wrong results, but I simply let the length be too great by 1 and correct it as needed. The combo commands of SysRPL allow this be a net win, while it would be a net loss in the meta-based UserRPL version and a guaranteed "Bad Argument Value" error in the list-based one.

I left out parameter count / type / value checking; make sure you supply two reals that satisfy the conditions for valid L and R, or this program will go ballistic. I could use up some of the padding space for it, but the padded version is where speed matters, and type checking definitely takes more CPU cycles than pushing and dropping a string.

Short version: 70 bytes, #1E4Fh; padded version: 100.5 bytes, #DE07h:

Code:

::
  "PADDING FOR SCORE . . ." DROP (leave this line out for the short version)
  COERCE2
  #TWO#ONE BINT2
  4PICK ONE_DO
    OVER #1+
    2DUP #- #2+PICK
    NDUPN
    DUP#1+ top& #1-SWAP
  +LOOP
  #1- SWAPUnDROP SubMetaOb
  %0 SWAP
  ZERO_DO
    SWAP UNCOERCE %SQ_ %+
  LOOP
;

This code is able to calculate the sum of squares over the sequence from 1. up to 1.E4 1. - in just over 23.7_s on real hardware. Shorter problems take less, obviously, 1. to 325. is just under the 0.7_s threshold where the two SysRPL versions get equal scores.
The UserRPL versions already tie at about 1. to 130. Out of curiosity I fed the full range into the faster of them just now, and it takes tens of minutes at least; not sure if I'm going to let it finish. In theory it should do so eventually, because it works fine on smaller requests, and I'm not aware of any hard limits it could bump into.

Also, dear curious judge, G_100 is 21. and G_500 is 56. Hacking the program to spit out specific values of the sequence instead of summing up from L to R took much longer than running it, even in the short and slow UserRPL variant, because I can't make these modifications in 3.2742_s. You may have underestimated the challenge there.

[John Keith]

I have two similar solutions for the RPL programming challenge. The first is the smallest, weighing in at 91.5 bytes and taking about 9.7 seconds on an HP 50g for a = 500 and b = 1000.

Code:


\<< \-> a b
  \<< 1. 2. b
    FOR k k OVER - PICK PICK 1. +
    NEXT b \->LIST a b SUB SQ \GSLIST
  \>>
\>>

My second solution is a bit larger (108 bytes) and a bit faster (about 8.9 seconds for the same values as above).

Code:


\<< \-> a b
  \<< 1. 2. b
    FOR k k OVER - PICK PICK 1. +
    NEXT 0. a b
    START SWAP SQ +
    NEXT a ROLLD a 1. - DROPN
  \>>
\>>

I do have a couple of minor grumbles regarding the contest rules which can be illustrated by the two programs.

I personally prefer the scoring method of (size in bytes) times (execution speed in seconds) regardless of program size. I recall this being the standard for most previous HHC contests although my memory may be faulty. My second program, though larger, does better on the size times speed metric but the current scoring rules favor the first program which is slower.

The other aspect I am grumbling about is that the second program will run on the 28S and 48S as long as the maximum value is, say, 1,000 instead of 10,000 so I question the need to exclude calculators earlier than the 48G. Including the earlier machines may even be seen as making the contest more challenging.

All grumbling aside, a thoroughly enjoyable contest and I eagerly await seeing the winning programs and all others as well.

Edit: 3298 posted while I was composing my post and made most of my points previously as well as providing superior and nicely commented programs. Bravo!

[David Hayden]

Here is my 40-byte program that won the RPN contest.

The program just counts up from the input number to find the first palindrome. To detect a palindrome, I reverse the digits, which can be done with very little code, and then compare the reversed number to the original.

Speed wasn't a contest criteria, except that the code couldn't appear to be in an infinite loop. By counting up by ones, I ran the risk of it taking too long, so I submitted to code on a DM42 for maximum speed and hoped that none of the test cases would take too long.

To reverse the digits of the original (old) number, I start with a new number of zero. Then in a loop do:
digit := old MOD 10
new := 10*new + old
old = (old-digit) / 10

For example, with an input number of 1234, igoes like this:

Code:

Iteration   old    new
0          1234      0
1           123      4
2            12     43
3             1    432
4             0   4321

Here's the code.

R01 = old number
R02 = new number
R03 = current candidate for a palindrome

Code:

01 LBL "PAL"    // program must be called PAL
02 LBL 02       // because GTO "PAL" is bigger
03 1
04 +            // Start looking for palindrome from the next number
05 STO 03       // candidate := input + 1
06 STO 01       // Old number is the same
07 0
08 STO 02       // "new" := 0
09 LBL 01
10 RCL 01       // old
11 10
12 ST*02        // new := new * 10
13 MOD          // old MOD 10 (the least significant digit)
14 ST-01        // old := old - digit, guaranteeing that old now ends in 0
15 ST+02        // new := new + digit
16 LASTX        // 10
17 ST/ 01       // old := old/10, but since it ends in zero, this shifts digits down
18 RCL 01       // old
19 X<>0?
20 GTO 01       // If more digit in old then go do another digit
21 RCL 02       // new, which is now the reverse of candidate
22 RCL 03       // Candidate
23 X<>Y?        // If they're different ...
24 GTO 02       // ... then candidate isn't a palindrome, go try the next one
25 END          // If you get here then candidate is a palindrome

[Gene]

Test cases I used for the RPN contest.

8
10
1220
1295
15151
19993
8999999
9000000


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

[3298]

(10-03-2021 11:51 PM)3298 Wrote:  Out of curiosity I fed the full range into the faster of them just now, and it takes tens of minutes at least; not sure if I'm going to let it finish. In theory it should do so eventually, because it works fine on smaller requests, and I'm not aware of any hard limits it could bump into.

In the end I went to sleep (it was already the middle of the night here in Europe), and relied on TEVAL and auto-OFF to take care of it. When waking up, the correct sum and a time of 7373.319_s were waiting for me. Yes, two whole hours and a little bit. I didn't think SysRPL would win by that much of a margin.
I blame LIST\-> putting object references into the list on the stack, which makes the garbage collection take forever each time it runs during the square-and-sum-up loop. Maybe a hybrid program using metas for sequence construction and \GSLIST afterwards would have been faster for such an extreme test, let's try ... uh-oh, it explodes on SQ with "Insufficient Memory" even though my real 50g has next nothing occupying memory on it (>220KB free). That means the compact SQ \GSLIST approach might not even qualify, because it fails to return correct results for extreme but valid inputs. (Granted, it could be a matter of needing just the few extra kilobytes which are occupied on my 50g.)
Let's try 0. SWAP 1. \<< SQ + \>> DOLIST after the SUB command instead: success after 60.7329_s. This makes it 108 bytes in size, checksum #A10Fh.

On the topic of speed, I suspect newRPL would demolish my results, both UserRPL and SysRPL. Does it still count as an RPL machine, though?

(10-04-2021 12:16 AM)John Keith Wrote:  taking about 9.7 seconds on an HP 50g for a = 500 and b = 1000.
[snip]
... and a bit faster (about 8.9 seconds for the same values as above).

For the sake of comparing apples to apples, my speed-optimized UserRPL solution takes 3.114_s (the size-optimized one takes 28.2468_s, but at less than 100 bytes, the score doesn't care about that anymore; the DOLIST one needs 3.7296_s), and the SysRPL version takes 1.1782_s.

And the speedy programs' time for the official test cases, now that we have them:
1 5 -> 27
UserRPL: .074_s (DOLIST edition: .0692_s), SysRPL: .0229_s
2 4 -> 17
UserRPL: .0398_s (DOLIST edition: .0607_s), SysRPL: .0209_s
5 5 -> 9
UserRPL: .0333_s (DOLIST edition: .0509_s), SysRPL: .0166_s
100 101 -> 882
UserRPL: .2469_s (DOLIST edition: .265_s), SysRPL: .0327_s
1000 1500 -> 4884182
UserRPL: 3.4551_s (DOLIST edition: 4.0587_s), SysRPL: 1.2148_s
2000 2300 -> 5724200 (my programs report 5724280 instead, is that a typo?)
UserRPL: 3.1559_s (DOLIST edition: 3.5319_s), SysRPL: .8707_s

For the last two test cases, the compact variants lose on score to the quick ones, and the one I edited to use DOLIST can't show its strength because the inputs aren't extreme enough.

[Gene]

Hello Didier !

What an amazing routine. RCL Q? I would never have expected that for sure.

Since the routine as written will not work without FIX 0 and CF 29, the routine should be listed as 35 (corrected) bytes I think.

Favor ?

Please write-up a step-by-step explanation for all of us. :-)

Gene

[Didier Lachieze]

(10-04-2021 12:33 PM)Gene Wrote:  Hello Didier !

What an amazing routine. RCL Q? I would never have expected that for sure.

I thought you had something like that in mind by specifying input numbers less than 10^7, as this means a maximum of 7 digits, which fits perfectly in a register.

Gene Wrote:Please write-up a step-by-step explanation for all of us. :-)

Sure, I'll do that by the end of the day.

[Didier Lachieze]

I've updated my initial post with the 35-byte version of my program, including step-by-step comments, as well as some details on the Q-register and how it works from Wickes' Synthetic Programming book, and also why I'm using PASN instead of GTO IND M to create the reversed string in the Q register.

[Gene]

(10-04-2021 09:03 PM)Didier Lachieze Wrote:  I've updated my initial post with the 35-byte version of my program, including step-by-step comments, as well as some details on the Q-register and how it works from Wickes' Synthetic Programming book, and also why I'm using PASN instead of GTO IND M to create the reversed string in the Q register.

Gene: Thank you. I saw what it was doing by SST through the code. Quite well thought out!

[dejanr]

Bravo Didier, this is just a superhuman solution! I mean PASN... what an idea!

I have a rather stupid question - is there some easy way to count bytes in a program? Here is my best attempt - how many bytes are there here:

Code:

LBL "PAL"
CF 29
FIX 0
STO 00
LBL 09
CLA
ARCL X
LBL 00
ALENG
2
X>Y?
GTO 01
-1
AROT
ATOX
ATOX
X=Y?
GTO 00
1
ST+ 00
RCL 00
GTO 09
LBL 01
RCL 00
.END

I think about 38 but I am not sure.

Sincerely, Dejan

[Didier Lachieze]

(10-05-2021 12:05 AM)dejanr Wrote:  I have a rather stupid question - is there some easy way to count bytes in a program? Here is my best attempt - how many bytes are there here:

When you do CATALOG 1 on the 41CX, it lists the user programs labels and END labels with the number of bytes (byte count is not displayed on a 41C or CV). Pack the memory before with GTO .. to remove the null bytes inserted during program edition.

For your program this gives:

Code:

PAL
END       45

So your program size is 45 bytes.

[Gene]

Dejanr, try writing one for the TI-59. :-) Be interesting to see it.

Gene

[Claudio L.]

(10-04-2021 08:00 AM)3298 Wrote:  On the topic of speed, I suspect newRPL would demolish my results, both UserRPL and SysRPL. Does it still count as an RPL machine, though?

Since you mentioned newRPL... I ran John Keith's first algorithm (and smallest).
The code needed no changes to run on newRPL, it was a straight copy/paste (and changed the trigraphs to proper characters).
With the arguments 2000 2300:

* From the keyboard, first run: 0.158 seconds, this is too fast so it completes before newRPL engages fast mode.
* After the calc is busy and switches to fast mode it runs on 0.0614 seconds

John Keith program takes 124 bytes in newRPL.

I also ran your first code (smallest), the only change needed as you documented was the ADD command.

Yours clocked at 0.258sec in slow mode and 0.169 sec in fast mode. The code ended up being 112 bytes, so it saved a few bytes (vs. John's) but pays the price in speed. John's algorithm gets the speed from building the list only once.

I did not run the faster version for either of you.


Now regarding your question: Why wouldn't newRPL count as an RPL machine? it runs the exact same RPL code you both posted (yours with a trivial change, granted), on the exact same hardware (50g).
I understand it may make the judges work difficult in judging the size * speed thing, but no more than an original 48G vs. a 50g: the code will have the same size on both machines, but the 50g will be faster, so how do you compare them? in the calc in which it was submitted or on the fastest? newRPL code is faster but is also larger, so there's a compromise there.
But other than that, running in newRPL you are still comparing your algorithm vs. John Keith's algorithm, the code didn't change at all so I don't see why it would matter. As long as you run both on the same platform to compare, it's valid.
You could end up having a userRPL winner and a different newRPL winner since the best code for one platform may not be the best code for the other.

Anyway, both routines are extremely compact and well written. Congrats to both of you!

[Gene]

The contest rules about allowed machines are for the ** conference ** to enable to judge (me) to be able to take entries and evaluate them in about 30 minutes early on Sunday afternoon.

That can be impossible if there are lots of different machines.

In reality this year, with 22 attendees at the conference, we only ended up with 2 RPL entries and 3 RPN entries.

The RPL entries were on the 50g while the RPN entries were HP-41CX (two of them) and one WP-34S.

Here in the forum, the allowed machines are not to be worried about. More importantly here is to share insights, innovative solutions, etc.

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

[dejanr]

(10-05-2021 06:13 AM)Didier Lachieze Wrote:  When you do CATALOG 1 on the 41CX, it lists the user programs labels and END labels with the number of bytes (byte count is not displayed on a 41C or CV). Pack the memory before with GTO .. to remove the null bytes inserted during program edition.

Thank you very much. I wrote the program on the HP-41CV, there is no such function there. But it is available on i41CX+ emulator for iPad, so I can "measure" programs in the future.

And to repeat - that PASN idea is just marvelous!

Dejan

[dejanr]

(10-05-2021 02:29 PM)Gene Wrote:  Dejanr, try writing one for the TI-59. :-) Be interesting to see it.

Gene

Good idea. Will try!

Dejan