HHC 2015 RPL Programming Contest

[David Hayden]

Could someone post the HHC 2015 RPL Programming Contest? I'm looking at you Bill Butler....

Dave

[David Hayden]

Bill sent me an email with the contest handout. It is attached.

Dave

[C.Ret]

Not sure this is the fastest way of doing it.

But it is simple:

Code:

« 1. * DUP SORT ΔLIST SWAP ISPRIME? + 0. POS NOT »

It is the concatenation of the two tests:
A list of distinct numbers:

Code:

« SORT ΔLIST 0. POS NOT »

A list of primes:

Code:

« ISPRIME? 0. POS NOT »

The 1. * is only here to convert the list of exact integer (aka TYPE 28) into regular 'dot' integers (aka TYPE 0). The ISPRIME? function aways returns 0. or 1. 'dot' integer.

[Joe Horn]

(10-07-2015 04:59 PM)C.Ret Wrote:  The 1. * is only here to convert the list of exact integer (aka TYPE 28) into regular 'dot' integers (aka TYPE 0).

RPL has a I→R function for that purpose.

[C.Ret]

Oh! Thank you, I miss this instruction.

I also just realise that the 'dot integers' are in fact just reals;
Sorry for that, I am new in HP-50g, I am only a native user of HP-28's RPL !

So, I have to post a new version, a Joe Horn version :

Code:

« I→R DUP SORT ΔLIST SWAP ISPRIME? + 0. POS NOT »

But I am in trouble, I am not confident in this code, due to the SORT instruction that may be slow on large lists

[David Hayden]

I worry that your solution won't work if the list contains integers that exceed to precision of real numbers.

I thought of a way to do it without sorting: the list is distinct primes if the least common multiple of the list is the same as the product of the list:

Code:

« DUP œLIST  SWAP  @ Put product of list in lvl 2
  1 +                   @ ugh. So STREAM works if list size == 1
  « LCM » STREAM           @ Get LCM of list
  ==
»

But this isn't quite right. If the list contains one or more copies of 1, it will incorrectly report that it is distinct primes. My next attempt was faster so I abandoned this.

Here's a version that tries to take advantage of the large size of the list. It exits as soon as it finds a duplicate or a non-prime. This takes advantage of DOLIST and error processing for speed, and to get a consistent stack when it's done.

Code:

«
  IFERR
  1 SWAP SORT
  1.
  «
    @ L2 = last number. L1 = current number
    IF DUP UNROT ==  @ duplicate?
       OVER ISPRIME? NOT OR THEN 1. DOERR END
  »
  DOLIST
  THEN 0.  @ Error thrown
  ELSE 1.
  END
  NIP
»

I generated a list of the first 250 primes larger than 8000. If finishes this list in 20.65 seconds (on the emulator set at authentic speed). But if I add 88 to the list, it finishes in just 12.13 seconds.

[Claudio L.]

(10-20-2015 02:18 AM)David Hayden Wrote:  I generated a list of the first 250 primes larger than 8000. If finishes this list in 20.65 seconds (on the emulator set at authentic speed). But if I add 88 to the list, it finishes in just 12.13 seconds.

Don't be so afraid to use SORT, the following code:

Code:


<< DUP ISPRIME? * DUP 
IF πLIST THEN
     SORT ΔLIST πLIST NOT NOT
ELSE
     DROP 0.
END
>>

Runs the same list of 250 primes bigger than 8000 on 11.9 seconds on a real 50g. Adding the number 88 at the end does it in 7.2 seconds.

[Gerald H]

Edit: See next posting, author of quoted programme is Werner Huysegoms. Thank you, Jacob, for the reference.

If you want to sort a list of integers (no dots) quickly, try this:

Code:


::
  CK1&Dispatch
  BINT5
  CODE 008EB 8FB976084A73415238D341508DAA56087A6F85A706124F50CCD206B8008FB9760D230F74514​4D818FAE13313114016E1321008F7986314213016479414931101331C41451C414174701657D6142​572F14B47F507DF477507A154A47C407A964F3714006118818FAE10807818F2E16A70774B18DF663​0773034202008DBD66275206C1F1101311CE143174147134EAF417414703200411813418E142818F​09EA34E4A2014416414001143130349E5501428A20016434B2130D51428A0008F910301428A00003​8F2D760071348D94150D58F60860818FA5400ED400068F8DA600703AD1D58151C434B2130D7CD400​1361341451C41451CA8F910301468A7CD174811D903CC101119D7142131147135147D534CF8208A5​70133D817434CFA208A531D214FE6133CACA53C13314016FCF52B119D718F1461351C41478A500CF​59E3447A208A160D4036C7F796033920DA000001001A000C2A20821009C100D8000416204F100392​009700084E2064100E610056000D6E2023100A510015000000000713418E16E1468AA001648A6FE1​46132130CA101164146132130CA102164146132C20603152715772294270A4C019329230594C312E​90A0090C4001ABEAB5B2AB21B30019521194870B5A01B5201200317815B61CB15B517E153325305B​0A93C50A9026A0C47025B9881C0114216414717421D58B6D023D88B24022819F1CDCDCD41414A14F​9E6001611719627E0314A16114F171D121AE59E6DC23AE89E23C225EB0D0D0114F25A90A6E4F41C1​15B523A9025A6E4B317315B3AE0A6E6B2014725A90818FA649117015B5CE4D017315B3CECE480173​14B91C00E401142CC136C21361524147CE133CA13315749C2009C667948D0132133132DE8B6008B2​C5818FA54F480D0F6D5CD4E118F15271CF15779F6009725E2103D2809132EA133EA1301531156199​6009926020032103143137CEC21351534818F842430D90C31A0EF01C015B09081F25B92D6A9A9480​0B9801AF0E403D8CD16514218513111A7F82158516FCD53E03D8D3818F39819F18AD2F8B30011806​D6CE132D5818F9C53211007EA500818FA91340614216414656D130102D5F2C210B0681DF1C01317D​A1521152715771517154707137136067C81573152715771517154707137067E61421152715771517​1547071370615270713607061360615072515211CF15719926F99690793154E07136137062515711​6F15219926F99690711154E132078B642130135152715771517154707061360650904D707818F290​611AD5E3F711BE2F68B760DCDF141174145DCDF6F9E03818FAF40018FAD2154516FD6CE061361341​351CF2515210407CE49C16F17FA981521990BE0699490745043D136134062515671537150718F1CF​1537996FE1547992907F1055D07609F2515211571996009124003165146185136D71751471C51370​61197B2007135DB1344000D50016A14218A17A1471CA8BE000181B3D8CD818FA9109400110131174​146D7136068F91030DB136EB111818F0FEA1014558FC07600713416FCD55C34B2130145174110133​130174147068F127621101303447A2014416407144030702
;

I can't remember where I found the programme - I'm definitely not the originator. (Anyone know who wrote it?)

[Jacob Wall]

(10-20-2015 02:47 PM)Gerald H Wrote:  I can't remember where I found the programme - I'm definitely not the originator. (Anyone know who wrote it?)

That would appear to be LSort, written by Werner Huysegoms, indeed very fast http://www.hpcalc.org/details.php?id=2828

[Werner]

I don't know (any more) how to compile that (in EMU48), so I can't be sure.
If it's mine it'll be the one from hpcalc.org, that's v0.4.
I have a more recent version (prompted by your request last year, Jacob) that corrects a number of bugs, and includes binary integers (supporting wordsize).
No, no speed gain - I squeezed the max out of that already.
The only thing missing is units support, and that will most probably never make it, the 'sort engine' can't support it.
I'll see if I can upload it (well, them, as now there's a 48 and a 49/50 version, due to 'getwordsize' being unsupported and in different places. If anyone would know how to get the wordsize within an ASM program, independent of the model, that would be great).

Cheers, Werner

[Jacob Wall]

(10-21-2015 07:16 AM)Werner Wrote:  The only thing missing is units support, and that will most probably never make it, the 'sort engine' can't support it.
I'll see if I can upload it (well, them, as now there's a 48 and a 49/50 version, due to 'getwordsize' being unsupported and in different places. If anyone would know how to get the wordsize within an ASM program, independent of the model, that would be great).

Cheers, Werner

Good to hear you did some work with LSort, and IMHO unit support isn't a big deal, others may disagree. Unfortunately I am of no help regarding your wordsize query within ASM.

Did you manage to implement a "natural" order sorting algorithm for strings? Much later after our discussions it dawned on me that if I wanted a more "natural" order for strings (especially for strings containing numeric values) I could simply pad all the strings with spaces (or any character really) so that the content is right justified with empty place holders to the left, then the standard sting sorting algorithms would probably handle them just fine and result in a sort order that I would prefer. One would simply need to check for the longest string, then pad all other strings to the same length. After sort, removing spaces and be done with it. I never got around to benchmarking such a implementation with System RPL, but in theory it shouldn't take that long even for 1000 elements in a list.

Jacob