Programming puzzles: processing lists!

[Gilles59]

#16. GoferList

Code:


.
.
.
.
.
.
.
.
.
.
.
.
.
a/

«
 1  
 DO
  1 + DUP 117 *
  ->STR Chars {"0" "8" "8" "2"} Intersect 
 UNTIL SIZE 4. == END
 117 *  
»

b/

«
 1  
 DO
  NEXTPRIME DUP
  ->STR Chars {"1" "3" "4"} Intersect 
 UNTIL SIZE 3. == END
»

c/

«
 1  
 DO
  1 + DUP 3 ^
  ->STR Chars {"6" "4" "0" "9"} Intersect 
 UNTIL SIZE 4. == END
 3 ^ 
»

[pier4r]

Added the #31 that I thought I already introduced (instead the #30 is part of it).

I solved it making use of a previous release of the David's library (I could not find an updated version with all the listed commands).

From 0 to users it is quick if the product is usable.

My (slow but useful) solution to #31 (more info: https://app.assembla.com/spaces/various-...stics101.s )

Code:


list2array
  @ works
  \<<
    @input: a list
    
    OBJ\->
    \->ARRY
  \>>

frequencyCalcHelp
"input:
L1: a list on elements of which we want to calculate the frequency in the list itself

output:
L3: the original list, sorted ascending, with no duplicates
L2: the frequencies of the elements in the original list.
L1: the matrix containing the two lists as columns for possible stats operations

example:
in: { 3 2 1 3 2 1 2 1}

Out: {1 2 3} { 3 3 2} [ [1 3] [2 3] [3 2] ]

requirements:
- it requires the list library done by davidM
check hpmuseum.org's forum topic keywords 'processing lists!'
"
  
    frequencyCalc
    \<<
      0                "inListSize" DROP
      {}             "resListNoDup" DROP
      {}              "resListFreq" DROP
    
      \->
      @input
      inList
      
      @local var
      inListSize
      resListNoDup
      resListFreq
      \<<
        inList SORT LDDUP 'resListNoDup' STO
        
        @counting the frequency now.
        resListNoDup
        1
        \<<
          inList SWAP LCNT
            @ we count the number of times the element was in the input
            @ list
        \>>
        DOSUBS
        'resListFreq' STO
        
        resListNoDup
        resListFreq
        @making the matrix
        resListNoDup list2array
        resListFreq list2array
        2
        COL\->
      \>>
    \>>

[DavidM]

(06-05-2017 11:38 AM)pier4r Wrote:  One thing I noted on hpcalc.org is that people put there great work (even if still in progress) but with little documentation. You have your list package in some post before and that is great, but you missed the documentation in the package. That is, the user should copy your post to procide a "txt" on the 50g to mention how the commands works because one does not always have a link to your post.

So my request/tip is. Could you put your nice documentation together in the zip package, so one knows that he has an help guide when needed. For the rest, kudos! I hope you will share your most updated version when you can.

I certainly don't mind posting interim versions (with whatever command documentation I have), but there's one wrinkle to be aware of:

As I add new commands, my inclination is to reorder the command positions alphabetically (with some strongly-related commands side-by-side instead). This allows commands to be more easily located when the library's soft menu is displayed. It also creates a potential problem: older programs stored on your calculator using that library's commands may now be referencing entirely different entries than those when the program was last saved.

If you are keeping your source files on your computer as text, this isn't an issue. You would simply need to transfer the files to the calculator again and save them after the new library is installed.

[DavidM]

(06-05-2017 11:48 AM)Gilles59 Wrote:  What about a DOPERM command to handle list permutations.
Something like :

Code:



INPUT
 { 1 2 3 4 }             @ A list
 2                       @ Number of elements for permutation
 << My program >>        @ to handle each permutation
DOPERM
 
OUPUT (If MyProgram does nothing}
{ {1, 2}, {1, 3}, {1, 4},{2, 1}, {2, 3}, {2, 4},{3, 1}, {3, 2}, {3, 4},{4, 1}, {4, 2}, {4, 3} }

I'll think about that. As I'm sure you're aware, the resources of the calculator imply that any command for permutation/combination iteration is likely to have significant limitations. While your given example is certainly feasible, the iterations increase rather quickly with even minimal increases in the numbers. And even if the computation speed can be minimized, processing large lists tends to create memory and garbage collection issues that also hamper overall use of the system. What is the scope of this type of command that you would find reasonable?

@Pier: while we're on this subject, challenge #17 isn't realistic for a 50g, unless I'm totally misunderstanding what you've written. Are you really intending to compute/present all 3628800 permutations? If so, your 50g is somehow very different from mine (and you are far more patient than I am).

[pier4r]

(06-05-2017 04:49 PM)DavidM Wrote:  I certainly don't mind posting interim versions (with whatever command documentation I have), but there's one wrinkle to be aware of:

As I add new commands, my inclination is to reorder the command positions alphabetically (with some strongly-related commands side-by-side instead). This allows commands to be more easily located when the library's soft menu is displayed. It also creates a potential problem: older programs stored on your calculator using that library's commands may now be referencing entirely different entries than those when the program was last saved.

If you are keeping your source files on your computer as text, this isn't an issue. You would simply need to transfer the files to the calculator again and save them after the new library is installed.

Since I always end up copying the last version of my source, I would not mind and when I don't copy new stuff, neither I have the need to change the library. Good tip about the library part though, I would have expected that the "call" would have searched the function based on the name, and the location would have been fixed at every new restart.

For the #17, I was thinking about using the SD card but it is also true that I should care about the computing time. In userRPL to generate millions of permutations it would take long time. Maybe in sysRPL not.

But remember that the challenges are not only for the 50g, in general those are for whatever calculator, even a fast DM42, prime, ti nspire and so on.

I'll see with newRPL now that I'm slowly setting it up.

[Gilles59]

#7 HP50G + GoferList

Code:

 DUP SIZE 2. / Split -1 SWAP + +

[Gilles59]

#9 HP50G + GoferList

Code:

«
 DUP ->STR  -> Liste s
 «
  Liste Nub  1.  « s SWAP ->STR " " + " " SWAP + " X " SREPL NIP » DOSUBS
  IF Nub SIZE 1. == THEN Liste ELSE "Inv." END
 »
»

[Gilles59]

(06-05-2017 05:33 PM)DavidM Wrote:  DOPERM

I'll think about that. As I'm sure you're aware, the resources of the calculator imply that any command for permutation/combination iteration is likely to have significant limitations. While your given example is certainly feasible, the iterations increase rather quickly with even minimal increases in the numbers. And even if the computation speed can be minimized, processing large lists tends to create memory and garbage collection issues that also hamper overall use of the system. What is the scope of this type of command that you would find reasonable?

The idea is not, in general, to return a list with all the permutations of the list (this is only possible for small list permutations because of the limited RAM).

But see this puzzle, for example :

Quote:
13597 is a prime number. What are all the prime numbers with these 5 digits ?

Code:


<< 
 { 1 3 5 9 7 } 5 
 << 
   {10000 1000 100 10 1 } * ΣLIST 
   IF DUP ISPRIME? NOT THEN DROP END
 >>
 DOPERM
>>

This will return the list of all the prime numbers with all the 1 3 5 9 7 digits.

[pier4r]

So I was using the LSHF (list shuffle) command from the library of David.

I was curious how solid it was in shuffling the list, since I do not know the algorithm (any chances to share the idea?).

So I created the following program:

Code:


testingLSHF
    @ using the library from davidM
    @ want to check wheter the shuffling is good enough or not.
    @ if that check is possible.
    @ The expected value of matches given a base list of 100 elements
    @ should be, if I am not mistaken, '\GS(I=1,100, IxCOMB(100,I)x(1-1/100)^(100-I)x(1/100)^I'
    @ let's see if a simulation fits
    \<<
      {} "basePerm" DROP
      {} "lshfPerm" DROP
      0 "sumNoMatches" DROP
    
      \->
      @input
      iterations
      listSize
      
      @local var
      basePerm
      lshfPerm
      sumNoMatches
      \<<
        listSize seqList 'basePerm' STO
        
        1 iterations
        START
          basePerm LSHF
          basePerm
          2 @taking one element from 2 lists
          \<< == \>>
          DOLIST
          
          @here we have a list with 1 or 0 according to match or not match
          @ we add 0 to avoid complains
          0 +
          
          @we count how many matches there were
          \GSLIST
          
          @we save the result
          'sumNoMatches' STO+
        NEXT
        
        iterations "iterations" \->TAG
        listSize "listSize" \->TAG
        sumNoMatches iterations /
        "avgNumMatches" \->TAG
      \>>
    \>>

Now if I'm not mistaken, the chance of an element to end up in a position should be 1/n .

Therefore the chances of an element to end up exactly in the original place, should be \( \left (1 - \frac{1}{n} \right )^{n-1} \cdot \left ( \frac{1}{n} \right ) \) .

Since there are 'n' original elements, I can sum this term 'n' times.

Then the chances that 2 elements ends up in exactly their original place are \( \left (1 - \frac{1}{n} \right )^{n-2} \cdot \left ( \frac{1}{n} \right )^{2} \)

The amount of times this can happen are all the possible combinations of 2 elements, so \( \binom{n}{2} \)

If I continue and pack this in a formula, plus I consider the resulting matches between the original list and the shuffled list (so I want the expected value of the number of matches), I have:
\( \sum_{i=1}^{n} \left [ i \cdot \binom{n}{i} \cdot \left (1 - \frac{1}{n} \right )^{n-i} \cdot \left ( \frac{1}{n} \right )^{i} \right ] \)

Once again, if I am not mistaken, this should average (thanks 50g) to 1 match if n=100 .

And my test found out that my expectation through formulas seems to match the expectation through computation. So LSHF seems to work very well. Now I'm interested how it works. David could you explain the procedure behind LSHF ?

Side note: it is possible that I made a lot of errors together, and by coincidence I got the same result.

[DavidM]

(06-06-2017 01:44 PM)pier4r Wrote:  I was curious how solid it was in shuffling the list, since I do not know the algorithm (any chances to share the idea?).

Certainly.

LSHF is essentially a faster/more efficient SysRPL implementation of this routine, which you may recognize from another posting:

Code:

ShufList
\<<
  @ explode the list onto stack and save the size (sz)
  OBJ\-> \-> sz

  \<<
    @ loop: for list item positions 1 to (sz-1), choose a
    @ random item from the remaining candidates and move it
    @ to the target position

    @ note: stack positions (sz...1) are numbered inversely to
    @ list positions (1...sz)

    @ x represents the current target position
    sz 2 FOR x

      @ pick a random item position from the remaining pool
      x RAND * CEIL

      @ move the chosen item to stack level 1
      ROLL

      @ move the chosen item to the current target position
      x ROLLD

    @ update target to the next position
    -1 STEP

    @ implode the resulting list data
    sz \->LIST
  \>>
\>>

Its "randomness" is entirely dependent on the quality of the internal RAND function. Although I didn't realize it at the time I wrote it, apparently this method has a name: Durstenfeld's Version of the Fisher-Yates Shuffle.

For what it's worth, this came about because I noticed that the previous routine I used ("RANL" from the 1-Minute Marvels) gave biased results. RANL is a bit smaller, but the results seem questionable to me. I'll leave the analysis up to those more qualified. If you take a quick look at sample results from RANL, though, I think you'll quickly see what I'm referring to. Here's a sample run of 20 iterations of running RANL on a single list containing the integers 1-20 in order:

{ 1 2 3 4 5 6 14 7 20 8 19 9 18 15 17 10 11 16 12 13 }
{ 1 2 3 4 5 14 6 7 8 9 19 10 18 11 16 15 20 12 17 13 }
{ 1 2 3 4 5 6 7 8 9 15 20 14 10 11 19 12 18 13 16 17 }
{ 1 2 3 4 5 6 16 18 7 20 8 9 10 11 15 19 17 13 12 14 }
{ 1 2 3 17 4 5 6 7 8 14 9 13 10 11 19 12 16 18 15 20 }
{ 1 2 3 15 4 5 6 12 20 7 8 9 14 16 10 11 13 17 19 18 }
{ 1 2 3 4 5 6 7 17 16 15 8 19 18 9 10 11 12 20 13 14 }
{ 1 2 3 20 4 5 6 7 8 9 10 11 19 12 15 18 13 17 16 14 }
{ 1 2 3 4 5 6 20 14 7 15 18 16 8 9 19 17 13 10 11 12 }
{ 1 2 3 4 18 5 6 16 7 8 9 19 20 10 11 14 13 12 17 15 }
{ 1 2 3 4 5 20 6 7 15 8 17 9 14 10 13 11 18 12 19 16 }
{ 1 2 3 14 4 19 5 6 7 13 8 9 16 10 15 11 20 18 12 17 }
{ 1 2 3 15 4 5 18 6 7 14 8 9 16 20 10 11 12 17 13 19 }
{ 1 2 3 15 4 5 6 7 20 8 9 10 12 11 19 18 17 16 13 14 }
{ 1 2 3 4 5 6 7 8 9 10 18 19 11 20 17 15 16 12 14 13 }
{ 1 2 16 3 4 5 19 6 15 7 8 9 10 17 14 11 12 18 13 20 }
{ 1 2 3 16 4 5 6 18 14 7 19 17 8 9 10 11 12 13 20 15 }
{ 1 2 3 4 5 6 17 18 7 8 15 13 9 10 12 20 14 16 11 19 }
{ 1 2 3 19 4 15 5 6 7 8 9 10 11 12 13 17 18 16 14 20 }
{ 1 17 2 3 4 5 6 7 18 8 15 14 9 10 11 12 19 13 16 20 }

...and the same test using the ShufList routine:

{ 14 10 3 1 12 11 18 19 17 7 13 2 9 4 16 5 20 15 6 8 }
{ 14 11 8 6 9 1 7 5 19 17 2 13 4 18 3 12 20 10 16 15 }
{ 3 15 10 6 19 20 11 5 9 16 2 8 4 13 18 17 14 12 7 1 }
{ 15 8 5 3 1 12 9 2 13 16 11 18 6 14 20 7 19 10 4 17 }
{ 17 10 5 9 20 11 19 7 18 16 8 6 3 13 2 14 1 12 4 15 }
{ 13 9 7 11 8 2 16 3 4 20 5 18 14 15 17 6 10 19 12 1 }
{ 4 17 1 8 16 13 2 11 14 20 19 9 18 10 3 7 6 12 5 15 }
{ 8 20 2 3 4 16 7 10 17 5 13 14 6 1 18 11 15 9 12 19 }
{ 2 7 3 8 16 12 17 5 13 1 14 19 10 18 9 15 11 4 6 20 }
{ 9 3 20 11 5 13 19 2 1 18 7 4 16 8 10 15 6 17 12 14 }
{ 17 15 6 5 11 3 4 20 16 7 19 13 14 2 8 12 18 10 9 1 }
{ 18 13 4 20 1 17 5 7 6 15 8 11 10 16 2 9 19 3 14 12 }
{ 11 4 13 16 6 8 7 12 15 19 2 1 5 18 10 14 9 3 17 20 }
{ 20 8 3 11 6 18 15 12 4 2 16 9 13 19 1 14 10 17 7 5 }
{ 6 11 9 12 15 13 4 3 20 2 17 10 19 7 8 14 16 1 18 5 }
{ 4 10 18 16 20 19 17 3 12 11 7 2 9 15 5 6 8 14 13 1 }
{ 18 5 11 14 17 15 20 7 19 2 16 3 10 4 1 6 8 9 12 13 }
{ 18 15 6 10 5 8 4 12 17 13 20 1 3 7 16 9 2 14 11 19 }
{ 3 6 17 7 10 5 4 19 16 1 13 9 12 18 8 20 11 15 2 14 }
{ 2 4 14 6 7 1 13 16 3 10 12 19 20 17 5 9 18 8 11 15 }

[pier4r]

Thanks! And the fisher Yates shuffle was already mentioned here: http://www.hpmuseum.org/forum/thread-795...l#pid71847

I did not recognize that in you code (that looks very similar to mine, but I was wondering whether I applied enough shuffles)

edit: RANL appears to be quite weak.

[DavidM]

(06-06-2017 03:47 PM)pier4r Wrote:  Thanks! And the fisher Yates shuffle was already mentioned here: http://www.hpmuseum.org/forum/thread-795...l#pid71847

I did not recognize that in you code (that looks very similar to mine, but I was wondering whether I applied enough shuffles)

edit: RANL appears to be quite weak.

I'm pretty sure that post is where I saw Fisher-Yates referenced the first time. Thanks for pointing it out.

Re: RANL, I presume you could achieve better results by calling it repeatedly on a list, but at that point you'd be wasting a lot of time for a few bytes savings. I believe the Fisher-Yates method is sufficient in a single invocation, or should be so long as RAND is adequate.

Revisiting this has reminded me that I wanted to test whether I could use the Inside-out method to speed up LSHF by building the shuffled list an element at a time instead of exploding it first. I'm cautiously optimistic about that given the positive results I've seen with some other functions.

[pier4r]

So, surprise surprise.

I wanted to use the David's library to test some properties of the matchmaking procedure of a competitive programming game ( gladiabots ) . Of course my first choice was to do it on 50g, to let the device "suffer" a bit; and because the mathematical library simplifies a lot of operations that on a pc would require specific libraries for programming languages or specific programming languages (scilab, R, and so on).

The problem is, summarized: generate a list of 20000 numbers between 1 and 8 (the id of maps in the game). Then pick randomly 1442 of those creating a second list. Then check in this second list how many times the sublist { 1 1 } (or { n n } with n € [ 1, 8 ] ) appears.

Note that 5 1 1 1 2 has 2 times the repetition of { 1 1 } . 5 [ 1 1 ] 1 2 and 5 1 [ 1 1 ] 2 .

In matchmaking terms it means "how many times, from the perspective of the player, the same map has to be played consecutively (that could be frustrating)". I wanted to compare it with a real sample. I have a sample of 20000 matches and the most active player played 1442 of those 20000.

The 50g did the test using the generation of random numbers between 1 and 8 (series of 1442 random numbers, iterated 100 times), I had to wait a bit, but it was possible. The result matched the real sample.

The I thought a bit and I proposed to the dev of the game the following. To lower the repetitions of maps and still handling all the maps in a non-predictable pattern (otherwise people may stop playing for a while to avoid maps that they do not like): make a permutation of the maps, consume it, and then make a new permutation, instead of just picking a random map each time that could lead to long repetitions.

So I set a program to concatenate random permutations of the same base list ( { 1 2 3 4 5 6 7 8 } ) . To create a final list 20000 long. Then pick 1442 random elements from it (without picking the same position twice) to sort of simulate the activity of a player (not really valid, since a player mostly can play in certain moment of the day), then check how many times the same map appears consecutively as explained above.

This is the current code (more info, check assembla)

Code:


simSamplingPermHelp
    "
input:
5: totalIterations
4: numPermutations to do in one iteration
3: numberPossibleResults to put in one permutation
2: the number of picks from the number of elements in all the permutations
of the itertion
1: listToMatch to determine that the results where picked.

output:
1: average number of appearances of the given list to match

example:

10 5 6 3 {1 1} simSamplingPerm

requirements:
- it requires the list library done by davidM
check hpmuseum.org's forum topic keywords 'processing lists!'
    "
    
    simSamplingPerm
    @simSamplingFromPermutations and distributions.
    @the idea: we have a permutations of a base list over and over and we
    @sample from it random elements and then we see
    @if the distribution changes compared to the case where all the elements
    @can reappear every time.
    @
    @ 11:17 06.06.2017
    @ I launched yesterday a test with 100 iteration
    @ each which 2500 permutations of 8 elements (to match the 20000 samples of the
    @ gladiabots checks). Picking 1442 elements from every iteration
    @ and matching the list { 1 1 }
    @ It is still running after 8+ hours. Moreover expanding 20000 elements in one list
    @ I suppose is very hard for a calcualtor with 200kb of available RAM.
    @ So I have to compute this with faster systems and languages (the 50g is fast
    @ just one needs a proper system)
    \<<
      0    "sumMatchingSublist"            DROP
      0    "partialSumMatchingSublist"     DROP
      0    "randV"                         DROP
      {}   "lastRandomPerm"                DROP
      {}   "newRandomPerm"                 DROP
      {}   "basePerm"                      DROP
      {}   "newBasePerm"                   DROP
      0    "newBasePermLength"             DROP
      -1   "listToMatchSize"               DROP
      { }  "newSequencePicks"              DROP
      { }  "newSequence"                   DROP
      { }  "numMatchesResultList"          DROP
      
      \->
      @input
      totalIterations
      numPermutations
      numberPosResults
      noPickFromPerm
      listToMatch
      
      @local var
      sumMatchingSublist
      partialSumMatchingSublist
      randV
      lastRandomPerm
      newRandomPerm
      basePerm
      newBasePerm
      newBasePermLength
      listToMatchSize
      newSequencePicks
      newSequence
      numMatchesResultList
      
      \<<
        PUSH
        -3 SF
        -105 SF
        
        listToMatch SIZE 'listToMatchSize' STO
        
        numberPosResults seqList 'basePerm' STO
        
        @the main loop
        1 totalIterations
        START
          @ reset
          {} 'newRandomPerm' STO
          {} 'lastRandomPerm' STO
          {} 'newBasePerm' STO
          0 'partialSumMatchingSublist' STO
          {} 'newSequencePicks' STO
          {} 'newSequence' STO
        
          @loop to generate the permutations that generate the new sequence to pick from.
          1 numPermutations
          START
            @ every loop a permutation.
            newRandomPerm 'lastRandomPerm' STO
            
            DO
              basePerm LSHF 'newRandomPerm' STO
            UNTIL
              newRandomPerm lastRandomPerm \=/
            END
            
            'newBasePerm' newRandomPerm STO+
          NEXT
          @we have the new permutation list
          

          @now we decide random location of the permutation list
          @those cannot be repeated for the moment.
          numberPosResults numPermutations * 'newBasePermLength' STO
          1 noPickFromPerm
          START
            DO
              newBasePermLength RAND * 1 + IP
              'randV' STO
            UNTIL
              newSequencePicks randV POS 0 ==
            END
            
            'newSequencePicks' randV STO+
            @we may sort the list of picks or also not.
          NEXT
          
          @ then we pick the values
          newBasePerm
          1
          \<<
            IF
              newSequencePicks NSUB POS 0 ==
            THEN
              @not an element in the pick sequence
              DROP
            END
          \>>
          DOSUBS
          'newSequence' STO
          
          @now we need to check how many matching sublists are there.
          @if list is length 5 and sublist length 2
          @we want from 1 to 4 (because then we will pick 4 and 5)
          1 noPickFromPerm listToMatchSize 1 - -
          FOR indV
            newSequence
            indV indV listToMatchSize 1 - +
              @if index is 5 and sublist is length 2
              @ if index is 4 we want until 5
            SUB
            listToMatch
            
            IF
              @if the sublists are equal
              ==
            THEN
              1 'partialSumMatchingSublist' STO+
            END
          NEXT
          
          partialSumMatchingSublist 'sumMatchingSublist' STO+
          'numMatchesResultList' partialSumMatchingSublist STO+
          
        NEXT
        
        sumMatchingSublist totalIterations /
        numMatchesResultList
        
        POP
      \>>
    \>>

It is useless to say that after one night it had not finished all the 100 iterations that I wanted (to average the results).
So I said to myself. I need something faster with the same rich mathematical (in this case for list operations) environment.

I tried the ti nspire, but, as I reported here while Lua is very fast on it, its usage is very clumsly due to the lock down format of the ti nspire files. In short, either one has the ti nspire student software (through which one can create ti basic and lua programs) or one has to create the programs directly on the calculator for the exception of lua, but lua is mostly oriented on graphics. One could export the results from lua to math variables, but then one has to handle those using the calculator itself, without possibility to copy and paste on the Pc. Very, very clumsy.

So the ti nspire family for me it is out, I could not believe they made such "closed" system. It is all fine if one has stable final programs to load on the calculator, but for programs that need debug and so, it is absolutely not nice unless one has all the additional TI softwares. (at least this is valid for me when I compared it to the 50g and its workflow)

Then there is the newRPL but still I have to find a reliable way to export a program from the simulator. So even that is good for explorations but not big programs that require a lot of debug.
Therefore, before checking also HRAST basic (I do not have spare money at the moment), I decided to use the resources available on linux.

I thought again about using sqlite, but the random function of sqlite is, well, too verbose to handle to create permutations, so I decided against it.
At the end I settled on bash, that is one of the many languages that is not bad to explore (it may be useful afterwards), although quite limited (one has to create its own random function).

I wrote the script to run on my little headless server (my preferred choice for little stuff). It has 260 mhz arm processor and 32 mb of ram. Mostly like the prime, but with less optimizations I believe.

Well even the bash code, that required a lot of new knowledge (so was good), was super slow. I was actually not expecting bash to take so long to generate the result.
So, since the heaviest action was likely the list permutation, I decided to test the two environments.

The LSHF of David on my 50g (170 Kb of ram available)

Code:


testingLSHFspeed
    \<<
      {} "basePerm" DROP
    
      \->
      @input
      listSize
      iterations
      
      @local
      basePerm
      \<<
        \<<
          listSize seqList 'basePerm' STO
        
          1 iterations
          START
            basePerm LSHF DROP
          NEXT
        \>>
        TEVAL
      \>>
    \>>

and bash on the 260 mhz arm and 32 mbyte of ram (of which, 6 mbyte free)

Code:


permutate_array() {
  # 22:15 06.06.2017 it seems working.
  local input_array=( "${!1}" );
  
  local input_array_size_int=${#input_array[@]};
  declare -a permutation_res_array;
    #empty array
    #https://stackoverflow.com/questions/28055346/bash-unbound-variable-array-script-s3-bash
    #https://stackoverflow.com/questions/10806357/associative-arrays-are-local-by-default
  local random_int;
  local pop_int;
  
  # to shuffle, consuming the input putting it in random places in the output
  # we are going to use the input array as stack, popping elements
  for index in "${input_array[@]}"; do
    random_int=$( generate_random );
    random_int=$(( $random_int % $input_array_size_int )) ;
    
    pop_int=${input_array[$random_int]};
    if [[ $random_int -lt $input_array_size_int ]] ; then
      #swap the elements putting the one pointed by the random value
      #at the end
      input_array[$random_int]=${input_array[$(( $input_array_size_int - 1))]};
    fi
    
    #expand the result
    if [[ ${#permutation_res_array[@]} -gt 0 ]]; then
      # to avoid complains from set -u
      permutation_res_array=( "${permutation_res_array[@]}" $pop_int );
    else
      permutation_res_array=( $pop_int );
    fi
    
    #decrease the input
    unset input_array[$(( $input_array_size_int - 1))];
    input_array_size_int=$(( $input_array_size_int - 1));
  done
  
  globalretvalue=( "${permutation_res_array[@]}" );
}

testing() {
  local base_perm_arr=( $( seq 1 1000 ) );
  local total_interations_int=100;
  
  for ind in $(seq 1 $total_interations_int); do
    permutate_array base_perm_arr[@];
  done
}

100 times shuffling a list of 1000 elements. I hope the two version of the shuffling procedure are very similar (I tried to follow the Fisher-Yate procedure).

The results surprised me. I mean with newRPL maybe I would have expected that. Surely with hpgcc, maybe with HRAST BASIC. But userRPL + sysrpl , no, I could not expect that. On the other side, aside that my code in bash could be very slow, I was not expecting such taxing operations for the 260mhz arm device (although in bash there is a lot of array duplication).

LSHF testing, shuffling 100 times a list of 1000 elements: 4014 seconds.
bash shuffling the same list: 14532 seconds.

Woah, really well done David , I could not expect to have such an advantage on the 50g with the original RPL emulation.

To do my test I surely need to improve the speed of the bash list shuffle (like generating the result array before hand and then filling it) otherwise, well, it does not work well.


edit:
My code, mostly within bash, did not help, I was still around 600 seconds for 100 shuffles of a list of 100 elements. Against 83 seconds of LSHF
Using a binary, shuf, brought the asus 500 at advantage. 8.8 seconds, but still not as much as I thought.

50g + sysrpl are very impressive.

Code:


permutate_array_shuf() {
  #using the binary shuf to speed up things.
  # 23:28 07.06.2017
  # 100 lists 100 elements, 8.78 seconds
  local input_array=( "${!1}" );
  
  globalretvalue=( $( printf "%d\n" "${input_array[@]}" | shuf ) );
    #https://unix.stackexchange.com/questions/124478/how-to-randomize-the-output-from-seq
}

testing() {
  local base_perm_arr=( $( seq 1 100 ) );
  local total_interations_int=100;
  
  for ind in $(seq 1 $total_interations_int); do
    permutate_array_shuf base_perm_arr[@];
    # echo "${globalretvalue[@]}";
  done
}

[DavidM]

(06-07-2017 08:57 AM)pier4r Wrote:  ...83 seconds of LSHF

LSHF should be faster in the attached release. Not as fast as your binary shuf, of course, but on an ARM-based RPL calculator (49g+ or 50g) this version is about twice fast as the previous version in my testing. And that includes the new-and-improved range checking for the RAND seed as well.

You'll need to uninstall the previous library before installing this one. There's a handy command for doing that -- it's the last one in the library (so you can simply activate the library menu in the normal way, then go PREV to see it).

As a reminder, the command numbers have changed in this version, so be aware that any stored programs using the previous release's commands will now need to be edited appropriately.

A text file containing detailed descriptions of each command is included in the zip. Here's a summary of the current commands included:

LCLLT - collates a list of sublists
LCNT - counts objects in a list
LDDUP - removes duplicates from a list
LDST - distributes list items into sublists (reciprocal of LCLLT)
LEQ - checks list items to see if any do not match
LGRP - replaces repeated elements with a single instance
LMRPT - repeats list contents as indicated by count
LNDUP - creates a list by repeating an object as indicated by count
LREPL - replaces list elements with a substitute object as indicated
LROT - rotates list elements left or right as indicated by count
LRPCT - list with LGRP elements and another list of the count of each element
LSDIV - subdivides a list into <count> sublists
LSHF - shuffles the contents of a list
LSPLT - splits a list as indicated into two sublists
LSUM - ΣLIST that also handles lists with 0 or 1 element
LSWP - swaps the position of two list elements
LXIL - explodes inner sublists into individual elements (non-recursive)
LXILR - recursive version of LXIL
S→NL - converts a string to a list of numbers
NL→S - converts a list of numbers to a string
S→SL - converts a string to a list of characters
SL→S - converts a list of characters to a string

[pier4r]

Yay! So this version now is deserving also the gsl or not?

I'll use it ASAP (the best game is to use the 50g +math, why I forgot this for years. The best gaming console that one can get).

Edit:

installed. I love the "about" thing! How do you get that slick visualization of text? For a flashcard project I would like to show a large string but I do not see (did not try yet) how to activate the scrolling while the program is running.

[DavidM]

(06-11-2017 07:27 PM)pier4r Wrote:  Yay! So this version now is deserving also the gsl or not?

Well it's fully functional, and I'm not aware of any issues with any of the commands at this point. But there's still a couple more commands I'm thinking about (DOPERM, DOCOMB), along the lines of what Gilles mentioned earlier. I'd prefer to have the library at the point where the command set is stable before posting to the gsl (or hpcalc.org).

(06-11-2017 07:27 PM)pier4r Wrote:  I love the "about" thing! How do you get that slick visualization of text? For a flashcard project I would like to show a large string but I do not see (did not try yet) how to activate the scrolling while the program is running.

I use a specific SysRPL command (InputLine) to show the About information. It allows lots of customization. I've never tried to do it with UserRPL, but I believe you can do something similar with INPUT. See the description of that command in the AUR.

[pier4r]

So while I'm attacking the #33 I see a similar problem to the #20 (that it is still not solved in RPL, by me at least).

With the #20 I am stuck on debug problems in case of nested iterations on a list, like:

Code:


- given L1
for i in L1; do
  ...code...
  for j in L1; do
    ...code...
  done
  ...code...
done

If I try to do this with nested DOSUBS/DOLIST either I am super careful, or debugging it is very taxing.
So aside creating my own debug friendly dosubs/dolist (I am not so motivated) what could be workarounds since I need to iterate over a list?

Iterating with a FOR index L1 index GET NEXT is super slow for the quick test I made. (maybe in other 50g languages is faster)

The library of David gave me an idea (maybe an idea also for him?). Another way to iterate over a list is to rotate the list and get the head. Or consume the list (from the head/tail).
Another alternative still is to explode the list before the iteration, and then working on it with stack operations. But that is very messy in stack terms. One has to debug carefully.

Therefore I try to ask some more functions for the David Library, of course it is a wish no pressure whatsoever.

Having list operations (that I partially coded in userRPL) to iterate over a list in several ways:

- L1 listHead: returns on stack 2 the list, without the head, on stack 1 the head of the list
{ 1 2 3} -> { 2 3 } 1
- L1 listTail: returns on stack 2 the list, without the tail, on stack 1 the tail of the list
{1 2 3 } -> {1 2} 3
- L1 <num> listHeadIterate: returns the first <num> elements from the head of the list (in case it repeats making circle of the list), plus the list rotated (so the num+1 element now is in the head).
{ 1 2 3 4 5 } 2 -> { 3 4 5 1 2 } 1 2
- L1 <num> listTailIterate: returns the first <num> elements from the tail of the list, and then the list rotated
{ 1 2 3 4 5 } 2 -> { 4 5 1 2 3 } 5 4
- those above could be extended on multiple lists. To partially substitute DOLIST .
- other possible functions to iterate over/consume a list (a collection of lists)? (will be interesting to compare those with FOR + get , of course dolist/dosubs will be always faster)

I believe if I go through processing challenges using David's library, I'll find a couple more requests for sure. Again, I don't want to make pressure, those are just wishes. (I also believe that through -reasonable- wishes a library can grow very useful)

Main source repository changed the url: https://app.assembla.com/spaces/various-...Operations


Also #22

Code:


c22vaV1
    @Given two list of positive integers. 
    @ Add the elements (with equal position in the lists ) 
    @if those are different, don't add if those are equal.
    
    @it seems to work.
    \<<
      
      \->
      @input
      inputL1
      inputL2
      
      @local var
      \<<
        inputL1
        inputL2
        2 @pick one element from 2 lists
        \<<
          IF
            DUP2 ==
          THEN
            DROP @drop one
          ELSE
            +
          END
        \>>
        DOLIST
      \>>
    \>>

also #33

Code:


c33vaV2
    @ See V1 for metadata and notes
    @to avoid DOSUBS/DOLIST when operations are complicated
    @ it seems to work
    @ 11:52 12.06.2017 I can get even faster noticing that the
    @ element in position I gets children in position 2I and 2I+1
    @ timing is needed, after general timing of
    @ FOR + GET, dosubs, dolist, start+headlist
    \<<
      0 "l1Size" DROP
      0 "noMoreLeavesBool" DROP
      1 "counter1" DROP
      2 "counter2" DROP
      1 "counter3" DROP
      0 "source" DROP
      0 "dest" DROP
      { } "inputL1loop1" DROP
      { } "inputL1loop2" DROP
      0 "inputL1loop2size" DROP
      { } "resList" DROP
    
      \->
      @input
      inputL1
      
      @local var
      l1Size
      noMoreLeavesBool
      counter1
      counter2
      counter3
      source
      dest
      inputL1loop1
      inputL1loop2
      inputL1loop2size
      resList
      \<<
        inputL1 SIZE 'l1Size' STO
      
        @using a FOR/WHILE instead of dolist is way more flexible.
        @dosusbs shows the number of elements processed as well, but
        @well, not as flexible as a For, and not as debug friendly.
        @still the most common operations with FOR are slow.
        
        inputL1 'inputL1loop1' STO
        inputL1 headList DROP
        'inputL1loop2' STO
        l1Size 1 - 'inputL1loop2size' STO
        
        WHILE
          inputL1loop2size 0 >
        REPEAT
          inputL1loop1 headList
          'source' STO
          'inputL1loop1' STO
          
          1 'counter3' STO
          
          IF
            counter1 1 ==
          THEN
            @if it is the first element
            'resList' 0 source 2 \->LIST 1 \->LIST
            STO+
              @ we need double list to keep sublists with the "+" operation
              @TIL, I cannot just build a list within RPL, like { { 0 source } }, 
              @ I need to build it
              @programmatically. 11:42 12.06.2017
          END    
            
          
          @iterate on the rest of the elements
          WHILE
            counter3 3 <
            inputL1loop2size 0 >
            AND
          REPEAT
            inputL1loop2 headList
            'dest' STO
            'inputL1loop2' STO
            
            'resList' source dest 2 \->LIST 1 \->LIST
            STO+
            1 'counter3' STO+
            'inputL1loop2size' 1 STO-
          END
          
          'counter1' 1 STO+
        END
        
        resList
      \>>
    \>>

[DavidM]

(06-12-2017 08:37 AM)pier4r Wrote:  So aside creating my own debug friendly dosubs/dolist (I am not so motivated) what could be workarounds since I need to iterate over a list?

DOSUBS and DOLIST aren't "debuggable" in the usual manner. The only way I know of to debug this sort of thing is to simply write a test scenario where the stack is pre-loaded with sample contents and then you would put your << ... >> executeable on the stack for evaluation. Tedious, but you can at least step through things to see what happens with one iteration. You could always create a "feeder" app to call that one with several sample inputs.

(06-12-2017 08:37 AM)pier4r Wrote:  Iterating with a FOR index L1 index GET NEXT is super slow for the quick test I made. (maybe in other 50g languages is faster) ... Another alternative still is to explode the list before the iteration, and then working on it with stack operations. But that is very messy in stack terms. One has to debug carefully.

I usually try to avoid GET and PUT operations in any kind of looped operation for that very reason. "Explode-iterate-implode" requires care, but the payoff in performance is good. Most commands in the library I'm working on make use of either that model or a loop of "biting off" one element at a time.

(06-12-2017 08:37 AM)pier4r Wrote:  - L1 listHead: returns on stack 2 the list, without the head, on stack 1 the head of the list
{ 1 2 3} -> { 2 3 } 1

I could put something like this in the library, but it's still fairly easy (and efficient) in UserRPL as well:

DUP TAIL SWAP HEAD

(06-12-2017 08:37 AM)pier4r Wrote:  - L1 listTail: returns on stack 2 the list, without the tail, on stack 1 the tail of the list
{1 2 3 } -> {1 2} 3

Similar to the above, but requires a couple of extra REVLISTs. Fortunately, that command is fast (even for large lists):

REVLIST DUP TAIL REVLIST SWAP HEAD

(06-12-2017 08:37 AM)pier4r Wrote:  - L1 <num> listHeadIterate: returns the first <num> elements from the head of the list (in case it repeats making circle of the list), plus the list rotated (so the num+1 element now is in the head).
{ 1 2 3 4 5 } 2 -> { 3 4 5 1 2 } 1 2
- L1 <num> listTailIterate: returns the first <num> elements from the tail of the list, and then the list rotated
{ 1 2 3 4 5 } 2 -> { 4 5 1 2 3 } 5 4
- those above could be extended on multiple lists. To partially substitute DOLIST .

This is similar to a combination of (NEG) LROT with GoferList's Take, though the latter command returns its results in a list. I'm not sure what this would look like with multiple lists; could you provide an example?

[pier4r]

(06-12-2017 02:21 PM)DavidM Wrote:  I could put something like this in the library, but it's still fairly easy (and efficient) in UserRPL as well:

DUP TAIL SWAP HEAD

REVLIST DUP TAIL REVLIST SWAP HEAD

I have the userRPL (that explodes the list, yours are very compressed in terms of code. Neat) of those commands, I wondered if making a sysRPL version would have been (way) faster.

Quote:This is similar to a combination of (NEG) LROT with GoferList's Take, though the latter command returns its results in a list. I'm not sure what this would look like with multiple lists; could you provide an example?

Sure, it is all for iterations instead of using DOLIST
{ 1 2 3 4 5 } { 1 2 3 4 5 }
2 @num list
2 @pick elements from head and rotate lists
listHeadIterate

output
{3 4 5 1 2}
{3 4 5 1 2}
1
1
2
2

[DavidM]

(06-12-2017 04:48 PM)pier4r Wrote:  I have the userRPL (that explodes the list, yours are very compressed in terms of code. Neat) of those commands, I wondered if making a sysRPL version would have been (way) faster.

Well in this case barely faster. The UserRPL commands aren't much different from the SysRPL ones in this particular case. But I have no problem adding this, so I went ahead and created a new command "LHDTL" -- here's the detailed description:

Code:

______________________________________________________________________________

LHDTL (List Head Tail)

Input
1: { list of 0 or more objects }

Output
2: { remaining elements in a list }
1: object (first element from original list)

Returns the first element from a list, leaving the remaining elements in place in a
list in stack level 2.  If the list is empty, returns an empty list and NOVAL.

Examples:
{ 1 2 3 4 5 } LHDTL => { 2 3 4 5 } 1
{ } LHDTL => { } NOVAL

I don't much like commands that leave varying levels of results, so I chose to return NOVAL for an empty list's first object instead of returning just an empty list. Hopefully that's an acceptable approach. Also, it isn't a stretch to see that "REVLIST LHDTL" will get the last element, and I figured that if you are processing a list from the end you'd probably want to keep it reversed anyway. So I didn't see as much value in adding a separate command to get the last element.

(06-12-2017 04:48 PM)pier4r Wrote:  Sure, it is all for iterations instead of using DOLIST
{ 1 2 3 4 5 } { 1 2 3 4 5 }
2 @num list
2 @pick elements from head and rotate lists
listHeadIterate

output
{3 4 5 1 2}
{3 4 5 1 2}
1
1
2
2

I've added this to my list of "future considerations". I need to think about this one some more.