Programming puzzles: processing lists!

[pier4r]

New solutions and timings.

#11
50 lists of 100 elements, average time
Pier: 0.054 s
David: 0.047 s

#13 (this is an interesting one)
50 lists of 100 elements, average time
Pier: 4.03 s

#11 input generator

Code:


    c11listGen
    @ it seems to work
    \<<
      0 @resultList
      \->
      @input
      listSize
      @local var
      resultList
      \<<
        IF
          RAND 2 * IP 
        THEN
          @make a list palindrome
          
          @first half
          listSize 2 / IP 
          1 listSize
          getRandomList
          DUP
            @it will leave a copy on the stack
          'resultList' STO
          
          IF
            listSize 2 MOD 0 \=/
          THEN
            @add a random number in the middle
            
            RAND listSize * IP 1 +
            +
          END
          
          @add the first half reverted
          resultList REVLIST
          +
          @ the result list is already on the stack, no more actions needed.
        ELSE
          listSize
          1 listSize
          getRandomList
        END
      \>>
    \>>

#11

Code:


    c11vaV1
    @ given a list of positive integers, verify that it is palindrome
    @ it seems to work
    
    @timings: 50 lists of 100 elements 0.054 secs
    \<<
      0 @inputListSize
      \->
      @input
      inputList
      @local var
      inputListSize
      \<<
        inputList SIZE 'inputListSize' STO
        
        @ if the number of elements are odd, the central one will stay there,
        @ so no problem.
        
        @ extract the first half of the list
        inputList
        1 inputListSize 2 / IP
        SUB
        
        @extract second part
        inputList
        @starting point
        IF
          inputListSize 2 MOD 0 ==
        THEN
          inputListSize 2 / 1 +
        ELSE
          inputListSize 2 / IP 2 +
          @ 1 2 3 4 5 6 7 , we want to start from 5
        END
        @end point
        inputListSize
        SUB REVLIST
        
        @ now on the stack we have the first part of the list
        @ and the second part reverted.
        @ we check if they are equal.
        ==
        1 0
        IFTE
      \>>
    \>>

#13 input generator and code

Code:


    c13incrListValueWithLimitHelp
"input:
L2: reference list to define the max value for every position
L1: list to increase, same size of reference list

output:
L1: list increased according to the limit of the reference list.
If overflow, all zeroed.
"
    
    c13incrListValueWithLimit
    @ given a reference list for a max value
    @ add 1 to a given list, and perform carry operations
    @ if the increased element in the list "hit" the maximum
    @ value in the reference list.
    @ The reference list and the input list are incremented
    @ right to left like numbers, although in some cases this may be not
    @ necessary, but this means that the procedure may be reused also to
    @ compute numbers in base N exploded, digits by digits, in a list
    
    @it seems working.
    \<<
      0  @currValue
      0  @currRefValue
      10 @ufCarry
      \->
      @input
      referenceList
        @ like { 2 2 3}
      listToIncrease
        @ like { 2 0 1} output { 2 0 2}
      @local var
      currValue
      currRefValue
      ufCarry
      \<<
        @ reverse the lists to process them from the "lower" digit
        @ assuming that the input consider lower digits the end digits
        referenceList REVLIST 'referenceList' STO
        listToIncrease REVLIST 'listToIncrease' STO
        
        ufCarry SF
          @ we need to carry the operation.
        
        listToIncrease
        1 @one element at time
        \<<
          IF ufCarry FS? THEN
            'currValue' STO
            
            IF
              currValue 1 +
              referenceList NSUB GET
              >
            THEN
              0 @ produce a zero
            ELSE
              @ increment and stop
              currValue 1 +
              ufCarry CF
            END
          END
          @ otherwise we leave the read value as it is
        \>>
        DOSUBS
        
        IF
          ufCarry FS?
        THEN
          @total reset
          DROP
          
          0
          referenceList SIZE
          NDUPN
          \->LIST
        ELSE
          @do not forget that the list were reverted
          REVLIST
        END
      \>>
    \>>
    
    c13factorsCompositionHelp
"input:
L1: a positive integer

output:
L1: list of all evently divisors of the number, the number itself excluded
but 1 included.
"
    
    c13factorsComposition
    @ given a number in input
    @ retrieve the factors of the number
    @ and then the posible compositions.
    @ For example 100 -> 2, 4, 5, 10, 20, 25, 50, 100 (the last excluded since it is not interesting)
    @ this using the multiplicity of the factors and increasing it.
    
    @ it seems working.
    \<<
      0 @sf3
      0 @sf105
      {}      @factorsResult
      {}      @factorsElements
      {}      @factorsMultiplicity
      {}      @currentCombList
      { 1 }   @resultList
      \->
      @input
      inputNumber
      @local var
      sf3
      sf105
      factorsResult
      factorsElements
      factorsMultiplicity
      currentCombList
        @current combination of multiplicity list
      resultList
      \<<
        -3 FS? 'sf3' STO
          @ either 0 when clear, or 1 when set.
        -3 CF
          @this for factors and ISPRIME
        
        -105 FS? 'sf105' STO
        
        inputNumber \->Q FACTORS 'factorsResult' STO
        
        IF
          -105 CF
            @this for ISPRIME
          inputNumber ISPRIME?
          -105 SF
            @ speed up
        THEN
          @only one factor, the entire list
          @since it is not interesting, return the basic factor, 1
          resultList
        ELSE
          @there are more than one factor, so let's iterate on the
          @possible combinations of factors.
          
          @extract the factor list
          factorsResult
          1
          \<<
            @they are in odd positions
            IF
              NSUB 2 MOD 0 ==
            THEN
              DROP
            END
          \>>
          DOSUBS
          'factorsElements' STO
          
          @extract the multiplicity list
          factorsResult
          1
          \<<
            IF
              NSUB 2 MOD 1 ==
            THEN
              DROP
            END
          \>>
          DOSUBS
          'factorsMultiplicity' STO
          
          @the hp 50g functions library is awesome.
          @ if I have list A and list B, I can do A^B
          @ and every element of A gets the power of the corresponding element of B.
          @ How much "I have to do it on my own, or I need to search" is saved.
          
          0 factorsMultiplicity SIZE NDUPN \->LIST 'currentCombList' STO
            @the variable containing the actual exponentiations
          DO
            factorsMultiplicity
            currentCombList
            c13incrListValueWithLimit
            'currentCombList' STO
            
            'resultList'
            factorsElements currentCombList ^
            1 +
            \PILIST
              @product. profuct list and sumlist complain for list of size 1, so we always add a 1
              @ (in the case of the produt) to the list to be used. So there are always two
              @ elements.
            STO+
          UNTIL
            currentCombList
            factorsMultiplicity
            ==
              @we stop when the current list it is exactly like the
              @multiplicity list (it means we are finished)
          END
            
          @we pop out the tail, since it should be the number itself
          resultList
          tailList
          DROP
            @real result list on the stack
        END
          
        IF sf3 THEN
          -3 SF
        ELSE
          -3 CF
        END
        
        IF sf105 THEN
          -105 SF
        ELSE
          -105 CF
        END
      \>>
    \>>
    
    c13listGen
    @ produce list generated by sublists sometimes.
    @ it seems to work
    \<<
      0 @subSize
      0 @resultList
      \->
      @input
      listSize
      @local var
      subSize
      resultList
      \<<
        IF
          RAND 2 * IP 
        THEN
          @make a list generated by a sublist
          
          @random feasible size for the sublist
          listSize c13factorsComposition
            @list of possible sizes for sublists
          DUP SIZE
            @ take the size
          RAND * IP 1 +
            @take a random value between 1 and size
          GET 
            @interesting GET accept several floats, I fixed with IP
            @ quite late.
          DUP 'subSize' STO
          1 listSize getRandomList
            @generate a random list of positive integers
          
          @now duplicate it enough times
          listSize subSize /
          NDUPN @it leaves the number of duplications on the list
          1 - @reduce it of 1
          1 SWAP
            @ stack: 1 numb_duplications_minus_one
          START
            + @concatenate lists
          NEXT
        ELSE
          listSize
          1 listSize
          getRandomList
        END
      \>>
    \>>
    
    c13vaV1
    @ given a list, finding the smallest generating sublist starting from the head
    @ of the main list.
    
    @ since we know the size of the size of the list, the generating sublist is
    @ one of the possible composition of the factors of the size of the list.
    @ That is, if the listSize is a prime number, no sublists exists.
    
    @timings: 50 lists of 100 elements 4.03 s
    \<<
      0    @listSizeV
      0    @possibleSubLengths
      0    @listSize2
      0    @sublistLength
      1    @counter
      0    @testingSublist
      11   @ufValid
      \->
      @input
      inputList
      @local var
      listSizeV
      possibleSubLengths
      listSize2
      sublistLength
      counter
      testingSublist
      ufValid
        @ TODO:
        @ to use the same user flag I should use store and save flags in every program
        @ and subprogram, so I never have conflicts of values in flags.
      \<<
        inputList SIZE 'listSizeV' STO
        
        @ we get the possible sublist lengths
        listSizeV c13factorsComposition
        DUP SIZE 'listSize2' STO
        'possibleSubLengths' STO
        
        ufValid CF
        
        @then we consume the list of possible length checking if they
        @match the original list
        WHILE
          counter listSize2 \<=
          ufValid FC?
          AND
            @if the counter is within the list size and no valid
            @sublist are found.
        REPEAT
          @extract the sublist made out of the amount of elements specified
          @by the possible length list
          
          possibleSubLengths counter GET 'sublistLength' STO
          
          inputList
          1 sublistLength
          SUB
            @sublist on the stack
          
          @ now we replicate the sublist to match the list length
          listSizeV sublistLength /
          NDUPN
            @this leaves the number of replications on the stack
          1 - @decrementing it of one.
          1 SWAP
            @ stack: 1 number_of_repetitions_minus_one
          START
            +
              @concatenate the sublists
          NEXT
          
          @we have the sublist concatenated on the stack
          @now we compare with the original
          IF
            inputList ==
          THEN
            ufValid SF
            listSizeV sublistLength /
              @the result is "how many sublists"
          ELSE
            1 'counter' STO+
          END
        END
        
        IF ufValid FC? THEN
          0
            @0 generating sublists
        END
      \>>
    \>>

added also #16 and #17 as processing list challenges (and the more "list things" I see, the more I will add. Of course I know that I miss a lot of possible challenges that I don't see at the moment, but those are ok)

#16

Code:


    c16vaV1
    \<<
      { 0 8 8 2 }  @mult117
      { 1 3 4 }    @primeN
      { 6 4 0 9 }  @intCubed
      0 @iterations
      0 @stoFlags
      \->
      mult117
      primeN
      intCubed
      iterations
      stoFlags
      \<<
        RCLF 'stoFlags' STO
        @-3 SF
      
        @ multiple117
        @ I could compute multiples of 117 until I get the right digits
        @ but I need to convert a number in digits then.
        @ so let's try with permutations. I could write a function
        @ to return all the permutations of a list, but so far I put it
        @ in the todo. So we do random permutations (shuffle) of a list.
        @ it will eventually hit the mark.
        WHILE
          mult117 { 1000 100 10 1 } *
          \GSLIST
          117 MOD 0 \=/
        REPEAT
          mult117 8 shuffleList
          'mult117' STO
          1 'iterations' STO+
        END
        
        iterations
        mult117    
        
        0 'iterations' STO
        WHILE
          primeN { 100 10 1 } *
          \GSLIST
          ISPRIME? NOT
        REPEAT
          primeN 8 shuffleList
          'primeN' STO
          1 'iterations' STO+
        END
        
        iterations
        primeN
        
        0 'iterations' STO
        WHILE
          intCubed { 1000 100 10 1 } *
          \GSLIST
          3 XROOT
            @now we have the cube root of the value
          FP 0 \=/
            @continue until the cube root is not returning an integer.
        REPEAT
          intCubed 8 shuffleList
          'intCubed' STO
          1 'iterations' STO+
        END
        
        iterations
        intCubed
        
        stoFlags STOF
      \>>
    \>>