Post Reply 
Programming puzzles: processing lists!
04-28-2017, 09:51 PM (This post was last modified: 05-02-2017 06:33 AM by pier4r.)
Post: #58
RE: Programming puzzles: processing lists!
@DavidM: thanks for the answer, and yes I created this challenge also to force myself to think more in terms of list operations, that seems pretty optimized (at least, avoiding MAP) although, as you said, sometimes seems to return or complain for counterintuitive reasons. The point about the "variable not yet local" makes a lot of sense, but why then it works for the first 5 inputs, maybe it is luck.

I already linked the source file containing the entire code for my solutions, here, the code for single challenges will follow below (but likely will not be as updated as the linked file). Moreover once reminded about SUB, I tried to use it because a bit more practical in some cases than DOSUBS or DOLIST. (STREAM I cannot love it, aside for very simple stuff. Moreover I love the fact that one can just call operations between lists, like 'equal' . great function library from the 50g).

Average timings for 50 lists of 100 elements (note that I adapted the output of the DavidM functions to return 1 or 0 for easier comparison.
#6 (that is very similar to #10, my bad)
Pier: 3.04 seconds (impressive the slow down even using DOSUBS)
DavidM: waiting for fix, or using the result for #10

#7
Pier: 0.050 s
DavidM: 0.053 s

I guess we do mostly the same approach

#8
Pier: 0.29 s (thanks David for the double check)
DavidM: 0.034 s

#9
Pier: 0.26 s
DavidM: 1.83 s

#10 (like #6)
Pier: 1.58 s (impressed that SUB overused is faster than __one__ DOSUBS)
DavidM: 2.77 s

As usual, results and timings on other platforms are welcomed.

#6 input gen
Code:

    c6listGen
    @ given alist of length 100 of positive integers
    @ ensure that every integer appears in the list a numbeer of times
    @ equal to its value.
    @ generates valid and invalid lists, with a naive approach
    
    @ok it seems correct.
    \<<
      0   @validValuesList
      0   @addedElements
      0   @elementToAdd
      0   @duplicatesAdded
      { } @resultList
      \->
      @input
      listSizeV
      @local var
      validValuesList
      addedElements
      elementToAdd
      duplicatesAdded
      resultList
      \<<
        @ plan v1
        @ Instead of partitioning a number, we make a more
        @ trivial approach. 
        @ We know that if the list size is 10, 10 times 10 would fill it,
        @ so we take all the numbers from 1 to 10. 11 would not fit by default
        @ for example.
        @ We then generate a list with all this numbers.
        @ We then randomize the list.
        @ We consume the elements of the list and we put them inside the resulting
        @ list a number of times equal to their value.
        @ Only few lists generated in this way will be valid, but
        @ it is better than a totally random approach, because it is more likely
        @ that a list composed by 1 and 9 (for a 10 size list) could happen.
        \<< n \>> 'n' 1 listSizeV 1 SEQ 
        'validValuesList' STO
        
        validValuesList listSizeV 2 * shuffleList
        'validValuesList' STO
        
        WHILE
          addedElements listSizeV <
        REPEAT
          validValuesList listHead
          'validValuesList' STO
            @ on the stack we have the first element of the valid elements (lvl 2)
            @ and the remaining list (this level 1)
          'elementToAdd' STO
          
          0 'duplicatesAdded' STO
          WHILE
            duplicatesAdded elementToAdd <
            addedElements listSizeV <
            AND
          REPEAT
            'resultList' elementToAdd STO+
            'addedElements' 1 STO+
            'duplicatesAdded' 1 STO+
          END        
        END
        
        @ for more testing, shuffle the list a bit
        @ too easy when sorted.
        resultList listSizeV 2 * shuffleList
      \>>
    \>>

#6
Code:

    @ given alist of length 100 of positive integers
    @ ensure that every integer appears in the list a numbeer of times
    @ equal to its value.
    
    @it seems correct
    
    @avg: 50 lists 50 elements 3.04 seconds.
    @ impressive how certain list operations are faster than one list operation plus many variables
    @ (see dosubs) rather than several smaller list ops (see challenge 10)
    \<<
      0 @value
        @note that the input are positive integers.
      0 @value2
      0 @valueRepetitions
      10 @ufValid
      \->
      @input
      inputList
      @local
      value
      value2
      valueRepetitions
      ufValid
      \<<
        ufValid SF
          @ we assume the list is valid
        
        inputList SORT
          @list sorted, easier to operate on it.
        1
          @taking one element at time 
        \<<
          IF
            ufValid FS?
          THEN
            'value2' STO
              @save the input value
              
            @debug ###
            @value2
            @value
            @valueRepetitions
            @debug ###
            IF
              value2 value ==
            THEN
              'valueRepetitions' 1 STO-
                @I always get tricked by the order of the STO-
              
              IF
                valueRepetitions 0 <
              THEN
                ufValid CF
              END
            ELSE
              IF
                valueRepetitions 0 ==
              THEN
                value2 'value' STO
                value2 1 - 'valueRepetitions' STO
              ELSE
                ufValid CF
              END
            END
          ELSE
            DROP
              @should just drop the read element
          END
        \>>
        DOLIST
        
        IF
          valueRepetitions 0 \=/
          @ended with an incomplete repetition value.
        THEN
          ufValid CF
        END
        
        ufValid FS?
        1 0
        IFTE
      \>>
    \>>

#7
Code:

  @ given an input list of even length of positive integers, put a -1 in the middle.
    
    @ it seems correct
    @ avg time 50 lists 100 elements 0.050 sec
    \<<
      \->
      @input
      inputList
      \<<
        inputList
        DUP SIZE
        -1 SWAP
        @ stack
        @ l3: input list
        @ l2: -1
        @ l1: size of the list (even)
        2 / 1 +
         @we want the position equal to size/2 + 1
        addElementInList
      \>>
    \>>

#8 input gen
Code:

    @ for challenge 8 list generator of lists that have
    @ sometimes the second part repeated, and sometimes not.
    \<<
      \->
      @input
      listSizeV
      \<<
        IF
          RAND 2 * IP
        THEN
          @if 1
          listSizeV 2 / 
          1 10 getRandomList
          DUP
          +
        ELSE
          listSizeV 1 10 getRandomList
        END
      \>>
    \>>

#8
Code:

    @ verify if an even list is made by two lists
    @ it seems correct
    @ avg time 50 lists of 100 elements: 0.029 secs
    \<<
      0
      \->
      @input
      inputList
      @local var
      listSizeV
      \<<
        inputList SIZE 'listSizeV' STO
        
        @ get first half
        inputList 
        1 
        listSizeV 2 / 
        SUB
        
        @ get second half
        inputList 
        listSizeV 2 / 1 +
        listSizeV
        SUB
        
        @subtract
        -
        
        @sum the resulting list
        \GSLIST 0 ==
        1 0
        IFTE
          @ 1 if valid result
          @ 0 otherwise
      \>>
    \>>

#9 input gen
Code:

    @ for challenge 9 list generator of lists
    @ list with 3 parts of equal size, sometimes with
    @ first and third part equal, all the parts made out
    @ of one integer repeated.
    \<<
      3 / IP 3 *
        @fixing the input when not multiple by 3
        @ int(input / 3) * 3
      \->
      @input
      listSizeV
        @assumed multiple by 3
        @if not, we fix it.
      \<<
        IF
          RAND 2 * IP
        THEN
          @if 1
          3
          listSizeV 3 /
          NDUPN DROP
          5
          listSizeV 3 /
          NDUPN DROP
          3
          listSizeV 3 /
          NDUPN 3 *
            @we reuse the 'n' left on the stack by NDUPN
          \->LIST
        ELSE
          listSizeV {3 5} getRandomListFromValues
        END
      \>>
    \>>

#9
Code:

    c9vaV1
    @ verify that a list has a structure { A B C}
    @ where A, B, C are sublists with same length.
    @ A and C are equal
    @ All three contains the repetition of the same positive integer.
    
    @it seems correct
    @ time 50 lists 100 elements: 0.26 sec
    \<<
      0  @listSizeV
      0  @tempElement
      0  @firstThird
      0  @secondThird
      0  @thirdThird
      \->
      @input
      inputList
      @local var
      listSizeV
      tempElement
      firstThird
      secondThird
      thirdThird
      \<<
        inputList SIZE 'listSizeV' STO
        
        @extracting the parts
        inputList
        1 listSizeV 3 /
          @it is assumed that the list size is of the proper length
          @otherwise checks should be added.
        SUB 'firstThird' STO
        
        inputList
        listSizeV 3 / 1 +
        listSizeV 3 / 2 *
        SUB 'secondThird' STO
        
        inputList
        listSizeV 3 / 2 * 1 +
        listSizeV 
        SUB 'thirdThird' STO
        
        IF
          firstThird thirdThird ==
        THEN
          @the first and the last third are equal, but now we need to know
          @ if they are made of the proper elements.
          
          firstThird DUP HEAD -
          secondThird DUP HEAD -
          +
          thirdThird DUP HEAD -
          +
          \GSLIST 0 ==
            @ if all the three parts are composed by the same element
            @ thanks to the neat built in functions
            @ subtracting the head element from the list returns a list of 0
            @ adding all those lists together
            @ and then summing them with \GSLIST
            @ if it is equal to zero means that all is good.
            @ otherwise not.
          1 0
          IFTE
        ELSE
          0 @invalid
        END
      \>>
    \>>

#10
Code:

    c10vaV1
    @ actually like challenge #6 but I want to approach differently
    @ because, different approaches may give more ideas or at least more fun
    @ or more data.
    
    @ it seems correct
    @avg: 50 lists 50 elements 1.58 seconds.
    \<<
      
      0  @curElement
      1  @curFirstPos
      0  @listSize
      10 @ufValid
      \->
      @input
      inputList
      @local var
      curElement
      curFirstPos
      listSize
      ufValid
      \<<
        ufValid SF
          @assuming good result.
        inputList SIZE 'listSize' STO
          @we save the last position that at the start is the size of the list.
          
        inputList SORT 'inputList' STO
          @we sort the list
        
        @ now we extract the elements and we assume that they are repeated
        @ enough times, and we extract sublists to check if those
        @ are really composed by the repeated subelements.
        inputList HEAD 'curElement' STO
        
        WHILE
          ufValid FS?
          curFirstPos listSize \<=
            @we don't want to go over the borders.
          AND
        REPEAT
          inputList
          curFirstPos
          curFirstPos curElement + 1 -
            @ { 1 4 4 4 4} we want to extract from 2 to 5, not from 2 to 6
          SUB
          curElement -
            @if the extracted sublist is composed by repetition of the element
            @it will be equal to all zero.
            @ so we compare to a list of the same type
            @ (this because \GSLIST is not so reliable with list of one element)
            @ note that SUB returns an empty list when the index for the extraction
            @ are "outside the list"
          0 curElement NDUPN \->LIST
          
          IF
            ==
          THEN
            curFirstPos curElement + 'curFirstPos' STO
              @ ideally, if it is valid until the end,
              @ this will overflow the list size of 1
            IF
              curFirstPos listSize \<=
            THEN
              inputList curFirstPos GET 'curElement' STO
            END
          ELSE
            ufValid CF
          END
        END
        
        @result
        ufValid FS?
        1 0
        IFTE
      \>>
    \>>

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Programming puzzles: processing lists! - pier4r - 04-28-2017 09:51 PM



User(s) browsing this thread: 3 Guest(s)