Post Reply 
Programming puzzles: processing lists!
05-06-2017, 03:21 PM (This post was last modified: 05-06-2017 03:23 PM by pier4r.)
Post: #78
RE: Programming puzzles: processing lists!
So I had to fix my #6, all the time I mixed with the the #10 damn me.

timings (average on 50 lists of 100 elements)
#6
Pier: 2.87 s
David: 2.74 s

#13
Pier: 3.92 s (was 4.03 s)
David: 2.67 s

All code: https://app.assembla.com/spaces/various-...erations.s

#6 input gen
Code:

  \<<
      0    @possibleSubLengths     
      0    @chosenLength
      0    @possibleElements
      { }  @resList
      \->
      @input
      listSize
      @local var
      possibleSubLengths
      chosenLength
      possibleElements
      resList
      \<<
        IF
          2 RAND * IP 0 >
        THEN
          @generate a valid list
          @the repetition of the elements can be only a multiple of
          @the size.
          listSize c13factorsComposition
            @we get the possible subLengths
          listSize +
            @we also add the length itself
          'possibleSubLengths' STO
          
          @we randomize the list
          possibleSubLengths
          DUP SIZE 2 * shuffleList
          HEAD 'chosenLength' STO
          
          @now we create a list of all the numbers util lengthSize
          @repetitions so
          'n' 'n' 1 listSize 1 SEQ
          @shuffle
          listSize 2 * shuffleList
          @save
          'possibleElements' STO
          
          @now we consume those adding them to the result list a proper
          @number of times
          1 listSize
          FOR counter
            possibleElements headList
            @we save the list without the head
            SWAP 'possibleElements' STO
            
            resList SWAP
            @ we have the head, we replicate it
            @ and then we add it to the result list
            chosenLength NDUPN
            \->LIST +
            'resList' STO
          chosenLength STEP
          
          @leave the result but mixed
          resList listSize 2 * shuffleList
        ELSE
          @generate a random list
          listSize 1 listSize getRandomList
        END
      \>>
    \>>

#6 solver
Code:

    \<<
      0  @listSize
      0  @subSize
      0  @counter
      12 @ufValid
      \->
      @input
      inputList
      @localvar
      listSize
      subSize
      counter
      ufValid
      \<<
        @The plan:
        @sort the list
        @then if the list is valid all the elements will occupy equal
        @space in the list. So we can do it with sub.
        @To get the space of the list, we can use SORT and the reversed sort
        @so with POS we know the first and the last postion, if the know the
        @size of the list.
        @ a problem for this is a list with unique elements except some.
        @a no I have it, we ask for "different" in a dosub.
        inputList SIZE 'listSize' STO
        inputList SORT 'inputList' STO
        
        @assume positive
        ufValid SF
        
        @we know that the head element is in first position,
        @but how many times it appears?
        inputList
        DUP HEAD
        returnAllPos
        SIZE 'subSize' STO
          @we save the amount of positions
          @we could have also done it taking the last POS
          @ with a reverted list and then figuring out the size.
          @ but I want to use a routine that can be helpful.
          
        @now we can test all the sublists one after another.
        @but before a little check for possibility.
        IF 
          listSize subSize MOD 0 \=/
        THEN
          @no way it can be valid
          ufValid CF
        END
        
        IF
          ufValid FS?
            @if still it is valid
          subSize 1 >
            @if we have a sub that is larger than 1
          AND
        THEN
          1 'counter' STO
          WHILE
            ufValid FS?
            counter subSize * 1 + listSize <
              @the starting point of the next sub is within the size
            AND
          REPEAT
            inputList
            counter subSize * 1 + 
              @starting point
            counter 1 + subSize *
              @end point
            SUB
              @we have a sublist that should be done
              @of the same element, between counter*subSize + 1
              @ and (counter + 1)*subsize
              
            @we need to know if there is always the same element so
            @if it is so, if we test for inequality we get always zero
            2
            \<< \=/ \>>
            DOSUBS
            0 +
              @ to avoid \GSLIST complainst
            IF
              \GSLIST 0 \=/
            THEN
              @invalid list
              ufValid CF
            END
            
            1 'counter' STO+
          END
        ELSE
          IF
            ufValid FS?
              @if still it is valid
            subSize 1 ==
              @if we have a sub that is exactly one
            AND
          THEN
            inputList
            2  
              @2 elements one behind the other, if we get duplicates and not
              @uniques, we will see
            \<< == \>>
            DOSUBS
              @if we have only unique elements, the list should be made out of zeroes
            0 + @avoiding complaints from \GSLIST
            
            IF
              \GSLIST 0 \=/
            THEN
              @invalid list
              ufValid CF
            END
          END
        END
        
        ufValid FS?
          @valid 1, invalid 0
      \>>
    \>>

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 - 05-06-2017 03:21 PM



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