(50g) (userRPL) additional operations with a list

Code:


%%HP: T(0)A(D)F(.);

@ alternative found online %%HP: T(3)A(R)F(.);

@ You may edit the T(0)A(D)F(.) parts.

@ The earlier parts of the line are used by Debug4x.



@ in npp, just select language "normal" to get rid of the highlight.





@ Operations on list, also trying to recollect previous utility functions done before

DIR



  generalRemarks

"- the library is built out of necessity, so it assume good

usage, without much error checking and checks for corner cases.

It can be even substituted by an existing library if this exists,

it is found and it is reliable. If you know one, please share!

Contact me: pier4r on the museum of HP calculators forum!"



  builtIn50gFunctions

"see 50g user manual chapter 8 and relative commands in AUR"



  communityLibraries

"users on the hpmuseum.org/forum suggests goferlists10.zip"

  



  IncListElFuncHelp

"input:

L3: a list

L2: position of the element

L1: increment to apply



output:

L1: list with incremented element"



  IncListElFunc

  \<<

    @ program to increase the value of an element in a list

    @ trying to use a bit more stack instead of list operations,

    @ but still limiting it for maintainability.

    @ Done, it worked. Total execution of single round robin, 50 iterations, 857 seconds

    @ one iteration 17 seconds on avg.

  

    @ input on the stack, see variables

    

    @output, the list in input, modified, on the stack

    

    0

    \->

    @external inputs

    lList 

      @list

    lPosV 

      @position of the element

    lincV 

      @increase

    @local var

    numEl

    \<<

      lList OBJ\->

        @list on the stack, with end part number of elements.

      'numEl' STO

      

      @now to access the element in position, starting from the back

      @we need to do (numberOfelements - position) +1 steps.

        

      numEl lPosV - 1 +

        @the position on the stack to pick from the back

      @we recall the element

      ROLL

        @Something like the following

        @{ 1 2 3 5}  1  1         1

        @2 (pos)     2  2         3

        @            3  3         5

        @            5  5         2

        @            4  (4-2+1)

      

      @increment the value on the stack

      lincV +

      

      @roll it back, the same number of postions like before

      @so to counter the previous roll.

      numEl lPosV - 1 +

      ROLLD

      

      @recreate the list and leave it on the stack.

      numEl

      \->LIST

    \>>

  \>>

  

  shuffleListHelp

"input:

L2: a list

L1: numbers of shuffles (affecting single elements)



output:

L1: shuffled list



remarks:

to work properly the number of shuffles should not be low,

like the number of elements should do it"

  

  shuffleList

  @ TODO: consider something like this http://www.hpmuseum.org/forum/thread-2889.html

  @       the point is that one receives a list, it is not creating it from the start.

  @ TODO: consider analyze the results to suggest a proper number of shuffles or to

  @       implement a better algorithm.

  \<<

    @program that receives a list in input, and shuffles the elements

    @returning the shuffled list in output on the stack

    

    @arguments on the stack.

    @ 2: list

    @ 1: number of random elements to shuffle around

    

    0

    \->

    @external inputs

    inputList

    noShuffles

    @local var

    numEl

    \<<

      @explode the list on the stack

      inputList OBJ\->

      @save the num of elements

      'numEl' STO

      

      @roll randomily the elements in the list

      1 noShuffles

      START

        numEl RAND * 1 + IP

        ROLL

      NEXT

      

      @build the list back

      numEl

      \->LIST

    \>>

  \>>

  

  headListHelp

"input:

L1: list



output:

L2: list without head element

L1: head element"

  

  headList

  \<<

    @given a list in input, leaves on level1 the first element

    @ and on level 2 the rest of the list.

    

    @0 

      @numEl

    \->

    @external input

    list

    @local input

    @numEl 

      @elements in the list.

    \<<

      list OBJ\-> 1 - \->LIST

        @reducing the number of elements of 1 for the new list

        @we have the tail on level 2

      SWAP

        @now the head element is on the level 1 stack

    \>>

  \>>

  

  listHeadHelp

"input:

L1: list



output:

L2: head element

L1: list without head element"

  

  listHead

  \<<

    @given a list in input, leaves on level1 the rest of the list

    @ and on level 1 the head of the list

    

    @0 

      @numEl

    \->

    @external input

    list

    @local input

    @numEl 

      @elements in the list.

    \<<

      list OBJ\-> 1 - \->LIST

        @reducing the number of elements of 1 for the new list

        @we have the tail on the level 1

        @ head level 2

    \>>

  \>>

  

  tailListHelp

"input

L1: list



output:

L2: remaining list without tail element

L1: tail element

"

  

  tailList

  \<<

    @given a list in input, leaves on level1 the first element

    @ and on level 2 the rest of the list.

    

    0 @tailEl

    \->

    @external input

    listV

    @local input

    tailEl

    \<<

      listV OBJ\-> 

        @list exploded

      2 ROLL 'tailEl' STO

        @pick the tail from the stack, save it

      1 - \->LIST

        @reducing the number of elements of 1 for the new list

        @we have the remaining list on level 1

      tailEl

        @ we have the tail element on level 1, level 2 is the remaining list

    \>>

  \>>

  

  getRandomListHelp

"input:

L3: number of elements

L2: min value

L1: max value



output:

L1: a list of random elements between min and max value

with a size of number of elements"

  

  getRandomList

  \<<

    @0

    \->

    @input

    numElements

    minValue

    maxValue

    @local var

    @counter

    \<<

      \<<

        maxValue RAND * IP minValue +

      \>>

      'counter'

      1 numElements 1

      @ from 1 to numElements, increment of 1

      SEQ

    \>>

  \>>

  

  getRandomListFromValuesHelp

"input:

L2: number of elements

L1: list of usable values



output:

L1: a list of random elements picked from the list

of usable values, with possible repetitions.

"  

  

  getRandomListFromValues

  \<<

    0 @listUsableVsize

    \->

    @input

    numElements

    listUsableV

    @local var

    listUsableVsize

    @counter

    \<<

      listUsableV SIZE 'listUsableVsize' STO

        @not sure if sequence calls the program in input

        @multiple times

        

      \<<

        listUsableV

        listUsableVsize RAND * IP 1 +

        GET

      \>>

      'counter'

      1 numElements 1

      @ from 1 to numElements, increment of 1

      SEQ

    \>>

  \>>

  

  rotateListTailHelp

"input:

L2: list

L1: number of rotations 

(the last elment becomes the first, the first becomes the second)



output:

L1: rotated list

"

  

  rotateListTail

  \<<

    

    0 @numElements

    \->

    @input

    listV

    numRotationsV

    @local var

    numElements

    \<<

      listV OBJ\-> 'numElements' STO

      

      1 numRotationsV

      START

        numElements ROLLD

      NEXT

      

      numElements \->LIST

    \>>

  \>>

  

  addElementInListHelp

"input:

L3: input list

L2: new element 

L1: element position (if just append needed, please use '+' builtIN function)



output:

L1: list with element added in wanted position

"

  

  addElementInList

  \<<

    0 @numElements

    \->

    @input

    inputList

    newEl

    newElPos

    @local var

    numElements

    \<<

      inputList OBJ\->

        @explode list

      'numElements' STO

      

      @ then we move it in the wanted position

      @ assuming that we want to add -1 in position 2

      @ 1 2 3 4 5 -1 

      @ we have to go 5 levels of the stack over.

      @ so (num elements + 1) - position + 1

      newEl 

      numElements 1 + newElPos - 1 + ROLLD

      

      numElements 1 + \->LIST

    \>>

  \>>

  

  moveElementInListHelp

"input:

L3: input list

L2: element position

L1: new element position (within list size)



output:

L1: list with element moved from original position to new

position.

"

  

  moveElementInList

  \<<

    0 @numElements

    \->

    @input

    inputList

    elPos

    newElPos

    @local var

    numElements

    \<<

      inputList OBJ\->

        @explode list

      'numElements' STO

      

      @ moving on the top of the stack the wanted element

      @ notice that the position in the list is "reversed"

      @ compared to the position of the list exploded on the stack

      @ like { 1 2 3 4 5 } position 2 will be on stack level 4.

      @ L5: 1, L4: 2, L3: 3, L2: 4, L1:5

      numElements elPos - 1 + ROLL

      

      @ then we move it in the wanted position

      @ assuming that we picked the position 2

      @ for example position 1 or position 2

      @ 1 3 4 5 2 , 2 is not an input of ROLLD (the input of rolld is the num of levels)

      @ position 2 is now 'numElements - wanted position + 1' with ROLLD

      @ aka 5 - 2 + 1 = 4

      @ 1 (2) 3 4 5

      @ So like before, just with the wanted position

      numElements newElPos - 1 + ROLLD

      

      numElements \->LIST

    \>>

  \>>

  

  selectionSortListAscHelp

"input:

L1: list to order



output:

L1: ordered list with smallest elements in the front, biggest in the rear

"

  

  selectionSortListAsc

  @ time complexity O(n^2), space, in place or O(1) considering the amount of additional memory.

  @ en.wikipedia.org/wiki/Selection_sort

  @ the tricky part is not using additional list as helpers.

  

  @ 15:15 19.04.2017 works, but slow. I guess more pure stack operations are needed.

  

  @trying to use LIST functions

  \<<

    0 @numElements

    0 @remainingUnsortEl

    0 @maxPos

    0 @maxV

    

    10 @uFbool

    \->

    @input

    inputList

    

    @localVar

    numElements

    remainingUnsortEl

    maxPos

    maxV

    

    uFbool

    \<<

      inputList SIZE 'numElements' STO

      

      @now we find the maximum of the remaining elements

      numElements 1

      FOR counter

        @inputList \<< MAX \>> STREAM

          @ streams takes the first two elements of a list, run the program

          @ then takes the remaining elements one by one and for each run the same

          @ program. A smaller version of DOLIST/DOSUBS

          @ stream is not so usable, we don't have the position of the max

        

        uFbool CF

          @reset, it means that a new max has to be searched

        

        inputList

        \<<

          \->

          nextValue

          

          \<<

            IF

              NSUB counter \<=

            THEN

            

              IF

                uFbool FC?

              THEN  

                @if max was never set so far

                @first time for a new max

                nextValue 'maxV' STO

                NSUB 'maxPos' STO

                uFbool SF

              ELSE

                @we have a valid maxV already

                IF

                  nextValue maxV >

                THEN

                  nextValue 'maxV' STO

                  NSUB 'maxPos' STO

                END

              END

              

            END

          \>>

        \>>

        DOSUBS

        

        @ here we have the max value and the postion

        @ so we move the positions

        inputList

        maxPos

        counter

        moveElementInList

        'inputList' STO

      -1 STEP

      

      inputList

    \>>

  \>>

  

  selSortListAsc2

  @ like selection sort but with Stack operations instead of list

  @ operations.

  \<<

    "TODO"

      @nice way to leave notes around.

  \>>

  

  listOPusages

  DIR

    @####################################################

    @ Processing lists

    @ www.hpmuseum.org/forum/thread-8209.html

    

    c1tester

    \<<

      { } @timeList

      { } @positionCheckedList

      \->

      timeList

      positionCheckedList

      \<<

        1 100

        START

          100 {3 5} getRandomListFromValues

          'c1vaV1' TEVAL

          @collect the timing

          OBJ\-> DROP

          'timeList' SWAP STO+

          'positionCheckedList' SWAP STO+

        NEXT

        

        timeList

        positionCheckedList

      \>>

    \>>

    

    c1vaV1

    \<<

      @ given a list in input of 3 and 5, length 100+

      @ if those are not alterated, the list is invalid

      @ returning possible different values for statistics

    

      1 @lastPosChecked

      3 @uf3

      5 @uf5

      10 @ufInvalid

      \->

      @inputs

      inputL

      @local

      lastPosChecked

      uf3

      uf5

      ufInvalid

      \<<

        @flags as booleans

        uf3 CF

        uf5 CF

        ufInvalid CF

        

        @set the first value.

        @ with if then else

        IF

          inputL 1 GET 3 ==

        THEN

          uf3 SF

        ELSE

          uf5 SF

        END

        

        inputL

        \<<

          \->

          listEl

          \<<

            IF

              NSUB 1 >

              @we already used the first element

              ufInvalid FC?

              @ list not invalid

              AND

            THEN

              CASE

                  listEl 3 == 

                  uf5 FS? 

                  AND

                THEN

                  uf5 CF

                  uf3 SF

                END

                

                  listEl 5 == 

                  uf3 FS? 

                  AND

                THEN

                  uf3 CF

                  uf5 SF

                END

                

                @def                

                ufInvalid SF

              END

            END

            

            IF 

              ufInvalid FC?

            THEN

              'lastPosChecked' 1 STO+

            END

          \>>

        \>>

        DOSUBS

        

        @inputL

        @

        @IF

        @  ufInvalid FS?

        @THEN

        @  "invalid"

        @END

        lastPosChecked

      \>>

    \>>

    

    @####################################################

    testing

    \<<

      testSortComp2

    \>>

    

    testSortComp

    @comparing builtin sort functions

    @with added sort functions

    

    @ built in sort avg: 0.5 seconds for 50 elements

    @ selectionSortResultList avg: 42.5 seconds for 50 elements. Not really fast

    \<<

      0 @sampleList

      {} @sortResList

      {} @selectionSortResultList

      \->

      @input

      @local var

      sampleList

      sortResList

      selectionSortResultList

      \<<

        50 1 100 getRandomList

        'sampleList' STO

        

        1 10

        START

          \<< sampleList SORT \>> 

          TEVAL

          OBJ\->

            @ break the tagged time

          DROP

            @drop the seconds

          'sortResList' STO+ 

        NEXT

        

        1 10

        START

          \<< sampleList selectionSortListAsc \>> 

          TEVAL

          OBJ\->

            @ break the tagged time

          DROP

            @drop the seconds

          'selectionSortResultList' STO+ 

        NEXT

        

        sortResList

        selectionSortResultList

      \>>

    \>>

    

    testSortComp2

    @to test the sort of GoFerList library (see hpcalc.org)

    @ avg result for a list of 50 random positive integers

    @ 2.9 seconds

    \<<

      0 @sampleList

      {} @goFerResList

      \->

      @input

      @local var

      sampleList

      goFerResList

      \<<

        50 1 100 getRandomList

        'sampleList' STO

        

        1 10

        START

          \<< 

            sampleList  

            \<<

              <

            \>>

            Sort 

          \>> 

          TEVAL

          OBJ\->

            @ break the tagged time

          DROP

            @drop the seconds

          'goFerResList' STO+ 

        NEXT

        

        goFerResList

      \>>

    \>>

  END

END