HP49-HP50 : when {list of repeated solutions} —> {list with no rep. sol}

[Gil]

Suppose that I find the following solution set:
{ [ 1 1 '1/3' 0 0 1 '26/3' ]
[ 1 1 '1/3' 0 0 1 '26/3' ]
[ 1 1 '1/3' 0 0 1 '26/3' ]
[ 5 1 '1/3' 0 0 1 '26/3' ]
[ 5 1 '1/3' 0 0 1 '26/3' ]
[ 5 1 '1/3' 0 0 1 '26/3' ]
[ 5 1 '1/3' 0 0 1 '26/3' ]
[ 5 1 '1/3' 0 0 1 '26/3' ]
[ 10 1 '1/3' 0 0 1 '26/3' ]
[ 20 1 '1/3' 0 0 1 '26/3' ]
[ 30 1 '1/3' 0 0 1 '26/3' ]
[ 30 1 '1/3' 0 0 1 '26/3' ] }.

Suppose now that I want the corresponding list without having the repeated vector in my list:
{ [ 1 1 '1/3' 0 0 1 '26/3' ]
[ 5 1 '1/3' 0 0 1 '26/3' ]
[ 10 1 '1/3' 0 0 1 '26/3' ]
[ 20 1 '1/3' 0 0 1 '26/3' ]
[ 30 1 '1/3' 0 0 1 '26/3' ] }

My solution is using SREPL.

First I put each solution element, repeated or not, as a string like :

{"[ 1 1 '1/3' 0 0 1 '26/3' ]"
"[ 1 1 '1/3' 0 0 1 '26/3' ]"
"[ 1 1 '1/3' 0 0 1 '26/3' ]"
"[ 5 1 '1/3' 0 0 1 '26/3' ]"
"[ 5 1 '1/3' 0 0 1 '26/3' ]"
"[ 5 1 '1/3' 0 0 1 '26/3' ]"
"[ 5 1 '1/3' 0 0 1 '26/3' ]"
"[ 5 1 '1/3' 0 0 1 '26/3' ]"
"[ 10 1 '1/3' 0 0 1 '26/3' ]"
"[ 20 1 '1/3' 0 0 1 '26/3' ]"
"[ 30 1 '1/3' 0 0 1 '26/3' ]"
"[ 30 1 '1/3' 0 0 1 '26/3' ]" }

and save that big list of string.solutions under sol.list.

Then use the following program:
\<< sol.list \->STR \-> s
\<< sol.list SIZE 1
FOR i s sol.list i GET DUP UNROT "" SREPL DROP + 's' STO -1
STEP "\|>" s + "\|>" "{" SREPL DROP "\|>" + "\|>" "}" SREPL DROP OBJ\-> OBJ\-> HALT SWAP DROP 1 - \->LIST
\>>
\>>

Or equivalently
« sol.list —>STR —> s
« sol.list SIZE 1
FOR i s sol.list i GET DUP UNROT "" SREPL DROP + 's' STO -1
STEP "AAAAA" s + "AAAAA" "{" SREPL DROP "AAAAA" + "AAAAAA" "}" SREPL DROP OBJ—> OBJ—> SWAP DROP 1 - —>LIST
»
»

My question:
Is there a better or simpler way to get the same result, without using this string manipulation & also not using any kind of special Library?

Thanks in advance for your insight.

Gil Campart

[Werner]

Yes ;-)
Remove duplicates from a list:

Code:

@ LUNQ - keeps first position
\<<
  \-> L
  \<<
    L
    1.
    \<< L OVER POS NSUB \=/ DROPN \>>
    DOSUBS
  \>>
\>>

Cheers, Werner

[Gil]

Really HP wonderful!

Great.

Thanks,
Gil

[David Hayden]

Here's another solution using SORT and STREAM. You have to use it after converting the list items to strings because you can't sort a list of arrays. This should be faster O(n*log(n)) than Werner's (O(n²))when the input is large.

Half the code is devoted to converting the results from individual items on the stack back into a list. Maybe there's an easier way that's still fast.

Code:

« DEPTH  → D
  «
  SORT
  « DUP2 IF == THEN DROP END »
  STREAM
  DEPTH D - 1. + →LIST
  »
»

[Werner]

Code:

\<<
  SORT
  DUP
  1.
  \<< DUP2 SAME DROPN \>>
  DOSUBS
\>>

Of course, SORT in this case, while also being O(n*log(n)), takes a lot of time.
Take LSORT instead ;-) It being a very faithful replacement though, it doesn't sort array objects, either.

Cheers, Werner

[Joe Horn]

If your code only needs to run on the HP 50g, not a 48, then #2FD006h FLASHEVAL is a built-in routine for removing duplicates from any list.

Example:

{ 1 2 3 2 5 5 4 } #2FD006h FLASHEVAL --> { 1 2 3 5 4 }

[David Hayden]

(12-21-2022 06:13 PM)Werner Wrote:  Of course, SORT in this case, while also being O(n*log(n)), takes a lot of time.
Take LSORT instead ;-) It being a very faithful replacement though, it doesn't sort array objects, either.
Cheers, Werner

I didn't know that SORT is slow. Do you know why it's slow? What makes LSORT faster?

[Werner]

(12-22-2022 02:48 PM)David Hayden Wrote:  I didn't know that SORT is slow. Do you know why it's slow? What makes LSORT faster?

Do you have an hour or two? ;-)
SORT is written in SysRPL, and LSORT is almost pure Saturn machine language.
As SysRPL goes, SORT is as good as it gets (insertion sort with binary search, where the insertion, usually the bottleneck, is a stack UNROLL statement that is very fast). LSORT uses median-of-three quicksort with selection sort for small subarrays.
I made LSORT to be as fast as I could make it, and also as compatible with SORT as possible. The current (and by the looks of it, final) version 0.6b does everything SORT does, apart from units, and lists with both real and decimal integer elements (on the 49 and up). I have no solution to incorporate either of these.

You mention that my LUNQ program is O(n^2). Technically, yes. But the built-in SORT is so slow your version will never outperform mine, I think. But with LSORT, it will.
(probably again not in this case as you have to turn the array elements into strings, which is also a costly operation)
Some run times: LSORT vs. (SORT):
[48] 50 random reals: 0.0657_s (1.7_s)
[48] 1024 random reals: 1.8_s (104_s)
[48] 744 strings (49G command list) : 1.4_s (70_s)
[48] 1024 lists of 2 random reals: 2.34_s (Not Enough Memory..)
[49] 1024 decimal integers created with RAND 1.E10 * CEIL R\->I: 1.8_s (217_s)
[49] 2048 strings length between 11. and 19. : 3.97_s ()
[49] 1024 binary integers : 1.8_s (114_s)

.. or more than 50 times faster.

Cheers, Werner

[Gil]

Sorry, I checked in my HP manual:

\<<
SORT
DUP
1.
\<< DUP2 SAME DROPN \>>
DOSUBS
\>>

I understand that the 1 is because I want to
compare 1 element at a time with another one —> OK.

DOSUBS command is used normally for 1 previously string (obtained by the DUP).

Then you write DUP2 to establish the comparison. I know that we have to compare one element down with the other ones of a list. But, from your program, I understand — wrongly — that we do compare one single element but with the entire list obtained by SORT command.

In fact, which elements of which lists are compared?

It's clear that 2 lists are used, but how do we know it (from your program) that we take just one element even in the first list?

As I finally understood, if we have
{"1“, “2“, “3“}, you SORT and DUP each separate element from SORT with the ones in DUP and you eliminate the repeated elements from DUP. Correct?

Sorry for this elementary question and thanks for your kind comprehension.

Regards,
Gil

[Werner]

DOSUBS loops over all list objects, and compares it to the previous object.
The very first object doesn't have anything on the stack to compare against, so I place an object on the stack that will never be equal to it: the list itself ;-). So the first object is always kept.
From then on, if they are the same, I drop it, else I keep it.
That, I do with DROPN and the result of SAME, which is 0 or 1.
At the end, DOSUBS wraps up all result objects in a list.
Ah I see I actually still have to DROP the duplicate list from level 2 ;-)

Cheers, Werner

[Gil]

Thanks, Werner, for your explanations.

I understood at the end, but could not reproduce something similar, for sure.

Let's say, to be kind, that my brain is somewhat rusted.

Your first suggestion seems the most interesting, not using strings.

I imagine that the code # SYSEVAL is a compiled version of yours, adding, as you mentioned, SWAP DROP instructions at the end.

Thanks to all for sharing.

Gil

[Gjermund Skailand]

For sys-rpl I think the entry

apndvarlst
or
^AppendList
or possibly
ˆCOMPRIMext

might be what you are looking for
other suggestion would be to calculate checksums for each array, make a list of lists

<< OBJ->
-> N
<<
1 N FOR I
DUP BYTES DROP SWAP 2 ->LIST
N ROLLD
>>
N ->LIST
SORT @ or use LSORT


with list of lists user rpl SORT will use the first element as sorting index.
then a second step to scan through and remove lists with same checksum.

Maybe this is may be faster and less memory intensive than converting to strings

br Gjermund

[Werner]

Gjermund Skailand Wrote:SORT
(LSORT?)

with list of lists user rpl SORT will use the first element as sorting index.
then a second step to scan through and remove lists with same checksum.

Hi Gjermund.
You can remove the question mark ;-) LSORT also supports lists of lists.
Cheers, Werner

[Gjermund Skailand]

Hi Werner,
noted and corrected.

Have a good Xmas.
BR Gjermund

[pier4r]

(12-22-2022 02:40 AM)Joe Horn Wrote:  If your code only needs to run on the HP 50g, not a 48, then #2FD006h FLASHEVAL is a built-in routine for removing duplicates from any list.

Example:

{ 1 2 3 2 5 5 4 } #2FD006h FLASHEVAL --> { 1 2 3 5 4 }

Is this sorcery? More seriously: is this documented anywhere in the official docs? (just to understand how one could discover it) Does it use '==' or SAME ? How is its speed?

[Gil]

I didn't dare ask...

as for INOUT program

\<< RCWS RCLF \-> ws f
\<< 3 TRANSIO DUP TYPE 2
IF ==
THEN \->STR f SIZE 3 > # 193357d # 196971d IFTE SYSEVAL + STR\->
ELSE STD 64 STWS \->STR f SIZE 3 > # 193359d # 196297d IFTE SYSEVAL
END ws STWS f STOF
\>>
\>>

[rprosperi]

(12-23-2022 11:57 PM)pier4r Wrote:  Is this sorcery? More seriously: is this documented anywhere in the official docs? (just to understand how one could discover it) Does it use '==' or SAME ? How is its speed?

Probably found romping thru ROM using Nosy. Serious couch hackers like Joe have done that for hours (weeks?) on end finding all sorts of sorcery, magic and good old-fashioned shortcuts. What's more amazing though is how one keeps track of all the jewels and gems one finds along the way, and remembering that you've even found a routine to do this or that...

[DavidM]

(12-23-2022 11:57 PM)pier4r Wrote:  Is this sorcery? More seriously: is this documented anywhere in the official docs? (just to understand how one could discover it) Does it use '==' or SAME ? How is its speed?

Programming in System RPL by Eduardo M Kalinowski and Carsten Dominik is probably your best source of information for things like this.

SYSEVAL, LIBEVAL and FLASHEVAL are all UserRPL commands which allow an RPL program to execute code on the calculator that is normally only accessible to System RPL programs. Typos when entering the binary numbers used as input to these commands can wreak havoc with your calculator (including causing loss of data or corruption of random memory areas). The payoff, however, can be substantial for their use when managed appropriately.

The particular command that is executed using Joe's suggestion has a name: COMPRIMext. The description is simply:

Quote:( {} → {}' )
Suppress multiple occurrances (sic) in the list.

Generally speaking, SysRPL commands need very specific types of arguments. As long as you make sure that the needed arguments are present and are of the required type, you'll be fine.

In this particular case, the list elements are checked for binary equivalency. So in that respect its comparison is more like SAME than == if numbers are involved. Speed-wise you would likely find it to be faster than any "regular" User RPL code for performing the same non-sorted de-duplication. LDDUP from the ListExt library can be faster, though, especially for lists with 25 or more elements.

[pier4r]

Thank you David!

(12-24-2022 03:35 AM)rprosperi Wrote:  What's more amazing though is how one keeps track of all the jewels and gems one finds along the way, and remembering that you've even found a routine to do this or that...

I agree, for this I wish the community would compose documents to collect all those useful code snippets or references. Sure one can say that those are available, only scattered in forums, but I still think it would be great to have a centralized collection (and yes, I tried to start one, although late and with near no success)