Programming puzzles: processing lists!

[pier4r]

Challenge #1a userRPL, 50g.

more functions: http://www.hpmuseum.org/forum/thread-8114.html

I noted that the test failed almost immediately and so I started to estimate the probabilities.

If I'm not mistaken, the test will succeed - given a random list - with probability:
1/2 for 2 elements
1/4 for 3 elements
1/8 for 4 elements
1/2^(n-1) for n elements

so it is very likely to fail.

Therefore I made the random input list smaller , only 10 elements, and I let the test execute 2048 times.

I should expect around 4 successes. let's see how long it takes to compute all this.

Code:


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
      \>>
    \>>