HHC 2016 RPL Programming Contest

[Gene]

HHC 2016 RPL Contest

Please post your results AFTER 6pm USA Central time on Sunday.

Enjoy.

[Gene]

Question arose at the conference...

When the program is called, the stack will be EMPTY except for the input string.

Upon program completion, the stack should be empty except for the answer, the Maximum Character Separation Value. Does not matter if that is an integer, real, etc., but only the value is to be on the stack.

[Gene]

Also, assume RPN mode not ALG is the default state. I mean, you're running a 48/49/50g and you have it in ALG mode? :-)

[Wes Loewer]

System RPL? or strictly User RPL?

[pgyore]

I am curious - not trying to start a revolt - why the 28C is mentioned in Gene's PDF as not allowed.

Best regards.

[Gene]

User RPL only please and the 28C was just to limit what I had to look over here at the conference.

I love my 28S and will be glad here on the forum to see anything in USER RPL running on the 28 series. :-)

[Wes Loewer]

(09-17-2016 01:39 PM)Gene Wrote:  Please post your results AFTER 6pm USA Central time on Sunday.

It's not yet 6pm your time, but it's bed time on this side of the world and I don't think I can improve my code any further. I won't post my solution or even the size till tomorrow, but for confirmation my CRC is #5843h.

Looking forward to seeing others' solutions.

(By the way, was that 6pm Central or Mountain time?)

-wes

[Gene]

Post after 6pm CENTRAL time please.

Programming contest is complete here at HHC, but let's hold the line for another 3 hours to be fair to all.

Hope it has been enjoyable.

[DavidM]

I decided to use this contest as yet another excuse to try out some list processing features. May not have been the best approach, but at least it forced me to experiment some more!

I assumed that a string with a single character was valid input and had to be handled with 0 as the result. This added 10 bytes to the final code.

This version has been tested with a Rev. R 48gx and Rev. 2.15 50g, and weighs in at 166 bytes:

Code:

%%HP: T(3)A(R)F(.);
\<<
  @ Explode string into char list
  1 OVER SIZE
  FOR n
    DUP n DUP SUB
    SWAP
  NEXT
  DROP
  DEPTH \->LIST

  @ Build First Char Pos/Last Char Pos lists
  1 2 START
    DUP 1 OVER
    \->STR "«" SWAP + "SWAP POS»" +
    OBJ\->
    DOLIST
    SWAP REVLIST
  NEXT

  @ Compute "difference" list
  SIZE 1 + SWAP - REVLIST
  SWAP -

  @ Find greatest value from difference list
  {0} +  @ Just in case there was only one char in string
  \<< MAX \>> STREAM

\>>

[Wes Loewer]

Here's my 50g entry weighing in at 76.5 bytes, but with a qualification.

Code:

\<< 
@ initialize max distance to zero
0.

@ reverse string (see note below)
OVER SREV

@ and away we go...
1. OVER SIZE
START
  TAIL
  @ putting size of remaining string here keeps track of times through loop, used in subtraction below
  LAST SIZE
  LAST HEAD
  5. PICK SWAP
  POS
  -
  ROT
  MAX
  SWAP
NEXT

@ clean up stack
DROP NIP
\>>

Notice the use of SREV which depends on lib 256 being attached. It's not clear to me whether or not this lib is attached by default. According to HLP49, on some ROMs, the lib 256 menu is attached automatically. If not, then I suppose SREV could be replaced by a SYSEVAL. ;-)

In any case, I found the exercise educational and mentally stimulating. Thanks Gene.

-wes

[3298]

Okay, I'm so rusty in UserRPL that I couldn't get anything better than 94.5 bytes, and even for that I had to look at the solutions already posted here to find out that POS is a thing. Earlier iterations used a slow bulky UserRPL loop doing roughly the same...
I'm more experienced in SysRPL, so I'll post that one instead. 40 bytes, checksum #EC76h:

Code:

::
  ZERO OVERLEN$ ONE_DO
    OVER CDR$ DUP4UNROLL
    ROT CAR$ OVERLEN$ POSCHRREV
    #MAX
  LOOP SWAPDROP UNCOERCE
;

For an even better score you could omit the UNCOERCE at the end. This would leave the result as a BINT on the stack, but those are readable at least, even with SysRPL stack display off. That would bring the size to 37.5 bytes, with the checksum #F514h.
Being a SysRPL program it's disqualified of course. But I'd like to see if someone else can squeeze another command out of this.

[DavidM]

(09-19-2016 04:26 AM)Wes Loewer Wrote:  Here's my 50g entry weighing in at 76.5 bytes, but with a qualification...

Wes, your code is very efficient and I'd be surprised if the official winner was significantly shorter. Thanks for using NIP -- I don't use UserRPL much these days and had to look that one up. Nice to know that there's a SWAPDROP for UserRPL!

As for the SREV, on my 2.15 50g it's not available after a factory reset unless you attach LIB 256. So at worst, you could include "256 ATTACH" at the beginning of your code. A few more bytes, but it still seems to fit the criteria as defined (perhaps Gene will chime in on this).

(09-19-2016 02:10 PM)3298 Wrote:  ...I'm more experienced in SysRPL, so I'll post that one instead. 40 bytes...

I had a hard time taking SysRPL out of my head for this problem as well, and you used most of the same commands I was thinking of at the time. I'm sure yours is still optimized better than what I would have come up with, though. I'd also guess that yours is one of the fastest implementations as well (short of Saturn/ARM code, of course).

A philosophical side note:

Your final complete solution is almost the exact same size as the code block I had to use just to reformat the string into a list of individual characters. While there may have been a shorter way to reformat the string, I think it points out a concept that I run across every time I try to "shoehorn" list processing into a solution. Namely, if the data doesn't start out as a list in the beginning, getting it into that format may not be worth the effort. While it's nice to be able to apply functions and processes to an entire block of data all at once, I still find the resulting code very difficult to read and maintain. It's probably just my lack of experience with that methodology. But I actually find yours and Wes' programs to be more understandable than my own.

I'm still inclined to force myself to use list processing when I get the chance, just to get to know it better. But for now, it still seems like a very specialized feature that is best suited for special circumstances (and less applicable to general-purpose use). Inherent to the methodology is that the underlying iterations are repeated for each applied process, which brings some inefficiencies with it.

[Wes Loewer]

(09-19-2016 03:50 PM)DavidM Wrote:  Thanks for using NIP -- I don't use UserRPL much these days and had to look that one up. Nice to know that there's a SWAPDROP for UserRPL!

I assume it's called "NIP" as in "nip it in the bud," but I picture a bunch of guys sitting around the table saying, "SWAPDROP is too long. What else could we call it? How about NIP?"

(09-19-2016 03:50 PM)DavidM Wrote:  I had a hard time taking SysRPL out of my head for this problem as well,

I've dabbled a little with SRPL. I'm always amazed at how specific the commands are: DUP4UNROLL, OVERLEN$, POSCHRREV. I half expected there to be a command called MAXDISTCHAR$.

I also used list processing on my first attempt so that I could use REVLIST.

It's funny how the brain works. When I got it down to 138 bytes, I was convinced I had done the very best I could. Then I saw something that I could do to reduce it further, and further, and further, each time fully convinced that I was absolutely done. Optimizing is a very psychological process.

-wes

[DavidM]

(09-19-2016 08:36 PM)Wes Loewer Wrote:  I'm always amazed at how specific the commands are: DUP4UNROLL, OVERLEN$, POSCHRREV. I half expected there to be a command called MAXDISTCHAR$.

Some SysRPL commands are specialized (like those you've mentioned above), but some others are simply a call to another SysRPL subroutine that does the indicated steps. I've always assumed that the latter of these were done simply to save precious space in the firmware. If you can replace even a small amount of 10-nibble command sequences with 5-nibble ones, you've saved more than enough space to justify the creation of a separate subroutine. That's probably one of the reasons there are so many special-case combo SysRPL commands.

(09-19-2016 08:36 PM)Wes Loewer Wrote:  It's funny how the brain works. When I got it down to 138 bytes, I was convinced I had done the very best I could. Then I saw something that I could do to reduce it further, and further, and further, each time fully convinced that I was absolutely done. Optimizing is a very psychological process.

It is. After looking at your code, I realized that I had an incorrect assumption in my head about the TAIL command, so I revisited that. I recoded the initial translation block of my program and saved a few bytes, but it ended up with a leftover null string at the end of the list. Purely by accident, this extra null string ended up helping the overall program by alleviating the need to handle single character inputs as a special case. Those changes (and one other small one) ended up saving 17.5 bytes. It's still way too big compared to a more traditional approach, but a nice savings.

But here's the catch: the code is now even harder to understand (IMHO). It's smaller, but some of its intended function is purely accidental and not at all obvious unless you painstakingly trace through the code (or provide copious comments to explain why things happen the way they do). And if I ever needed to re-use the code for a similar purpose, it probably wouldn't be as suitable.

Perhaps it's simply the types of problems I tend to code (combined with my lack of familiarity), but I still find that the list processing tools are often "a nail in search of a hammer". But I'll keep trying to find the hammer.

[pgyore]

Wife: "What have you been doing with that calculator all weekend?"
Me: "You have no idea."
Me:" (barely audible) hippopotamus, rattlesnake, porcupine, flamingo, hippopotamus, rattlesnake, porcupine, flamingo..."

[Juan14]

I initialized the distance to zero, then with a FOR-NEXT loop, get the distance from each letter to it's first appearance in the string (using the SUB command and POS command) and then use MAX to keep the maximum distance.

«
0 1 PICK3 SIZE
FOR j
j PICK3 DUP j j SUB POS - MAX
NEXT NIP
»

[DavidM]

(09-19-2016 11:43 PM)Juan14 Wrote:  I initialized the distance to zero, then with a FOR-NEXT loop, get the distance from each letter to it's first appearance in the string (using the SUB command and POS command) and then use MAX to keep the maximum distance.

«
0 1 PICK3 SIZE
FOR j
j PICK3 DUP j j SUB POS - MAX
NEXT NIP
»

(palm slaps forehead, and then the following thought...)

This is great, Juan. 60.5 bytes! You could even save 2 more bytes by using "j DUP SUB" instead of "j j SUB". Very nice!

[RMollov]

(09-19-2016 04:26 AM)Wes Loewer Wrote:  Here's my 50g entry weighing in at 76.5 bytes, but with a qualification.

Code:

\<< 
@ initialize max distance to zero
0.

@ reverse string (see note below)
OVER SREV

@ and away we go...
1. OVER SIZE
START
  TAIL
  @ putting size of remaining string here keeps track of times through loop, used in subtraction below
  LAST SIZE
  LAST HEAD
  5. PICK SWAP
  POS
  -
  ROT
  MAX
  SWAP
NEXT

@ clean up stack
DROP NIP
\>>

Notice the use of SREV which depends on lib 256 being attached. It's not clear to me whether or not this lib is attached by default. According to HLP49, on some ROMs, the lib 256 menu is attached automatically. If not, then I suppose SREV could be replaced by a SYSEVAL. ;-)

In any case, I found the exercise educational and mentally stimulating. Thanks Gene.

-wes

NIP is not on HP48G either, how then comparison can be made?

[Gene]

Winning solution at HHC 2016 came from Roger Hill at 56.5 bytes.

<< 0. 1. Pick3 Size
For n
n Pick3 Dup Pick3 Dup
Sub Pos -
Max
Next
NIP >>

[Wes Loewer]

(09-20-2016 12:23 PM)Gene Wrote:  Winning solution at HHC 2016 came from Roger Hill at 56.5 bytes.

<< 0. 1. Pick3 Size
For n
n Pick3 Dup Pick3 Dup
Sub Pos -
Max
Next
NIP >>

Very nice!

I played around with SUB in a similar manner, but for some reason abandon the idea. Now I can't recall why. These contests are very humbling. :-)

Well done to Roger and Juan.