Post Reply 
Programming puzzles: processing lists!
06-14-2017, 06:02 PM (This post was last modified: 06-14-2017 06:04 PM by pier4r.)
Post: #158
RE: Programming puzzles: processing lists!
Werner nice input, although your very usage of the stack sometimes is not so easy to follow if one loses track of what is on the stack (like the fact that you collect only one input in a variable, the other is on the stack). I prefer something that may be bigger but easier to read if I did not touch it for long.

Anyway, the #35 , that with "for + get" is feasible (still, I think that even with for + get the #20 would be quite more demanding), seems working.

Actually I am not sure I tested all the corner cases so if you want to play along, do it.
It uses, I think, the library of david and also goferlist in case some commands were missing (but I avoided to replicate them)

The #35 requires the #36 and an helper.

If you have tips were I can improve (keeping things readable), let me know.

For the timings, well, I'll do if there is a bit of competition.

Code:

c35vaV1
    @check if an input list with a certain structure makes a balanced binary tree
    @requires list library of DavidM and goferlist
    
    @for the test done it seems working.
    \<<
      
      @plan: 
      @ - first finding the root that is the only sublist of the list containing
      @   0. Also this method of search will be crucial for all the other
      @   cases. So it is like a new processing list challenge:
      @   "return the positions of all the sublists of a list containing the given
      @   object"
      @ - put the position in LI (list input)
      @   of the object containing 0 in a separated list of "checked
      @   positions", called LCP
      @ - put the root in a separated list to consume to traverse the tree,
      @   called LTT
      @ - put the height of the current element added to LTT in a list of
      @   heights, LH. Note that the height in LH should match the position of the
      @   root in LTT
      @ - consume the first element (the root) from the list LTT.
      @   (since LTT has a relationship with LH, a way to consume it is
      @   to increment a counter after reading the element)
      @   check the positions of all the sublists containing it in LI
      @   (should be max 3, otherwise the tree is invalid)
      @ - put the destinations reached by the root , that have positions
      @   not present in LCP in LTT
      @ - put the heigths of those destinations in LH, with same positions
      @   as the destinations in LTT. Of course the heights are equal to
      @   the parent height (the root) plus one.
      @   We know who is the parent because we know which elements from LTT we are
      @   consuming.
      @ - put the returned positions in LCP (if you do this step before,
      @   you cannot use to discriminate new destinations)
      @ - generic step
      @   - Consume the next element E from LTT. Check all the sublists in LI that
      @     contains it. As usual, it should be max 3, of which max 2 sublists
      @     should be new (that is, their position is not in LCP). otherwise
      @     the tree is invalid (can still be invalid in other ways though)
      @   - put the destinations of the sublists where E appears, sublists that
      @     have positions not in LCP, in LTT.
      @   - collect the height of E from LH, and add plus one and put the heights of the
      @     new destinations in LH with positions relative to the position just added
      @     in LTT
      @   - add the positions retrieved before that are new in LCP
      @   - check. A node that has a single children (so only one destination)
      @     cannot have the children having children as well. So if given an element E
      @     only one destination is added, a check has to be done and 
      @     (a) the destination should appears only once in LTT
      @     (b) searching for sublists with the destination in LI 
      @         should return only one match that should be already in LCP in
      @         terms of positions
      @     otherwise the tree is invalid.
      @   - check. For the height. Since the procedure in theory is devised to
      @     explore the tree layer by layer, it means that every children has
      @     the height of the parent, plus 1. (because we add children when we
      @     expand a parent). Now when we have a node with no children, that is
      @     a leaf and we save the __minimum__ leaf height, then we continue to
      @     expand the rest.
      @     If we ever get a node that is +2 than the minimum leaft height
      @     then the tree is invalid because not balanced.
      
      0 "inL1Size" DROP
      {} "LExtractPos" DROP
      {} "LNodes" DROP
      1 "indexElToExpand" DROP
      {} "LNodesHeight" DROP
      0 "minHeight" DROP
      1 "parentNode" DROP
      0 "parentNodeHeight" DROP
      {} "LTemp" DROP
      0 "LTempSize" DROP
      {} "LTemp2" DROP
      {} "LTempSublist" DROP
      0 "tempScalar" DROP
      0 "isNotValid" DROP
      
      \->
      @input
      inL1
      
      @localVar
      inL1Size
      LExtractPos
      LNodes
      indexElToExpand
      LNodesHeight
      minHeight
      parentNode
      parentNodeHeight
      LTemp
      LTempSize
      LTemp2
      LTempSublist
      tempScalar
      isNotValid
      \<<
        inL1 SIZE 'inL1Size' STO
        
        @find the root
        inL1 0 c36vaV1 'LTemp' STO
        
        IF
          @if more than one node with 0 is returned
          @remember no duplicates allowed so we cannot have 2 roots
          LTemp SIZE 1 \=/
        THEN
          1 'isNotValid' STO
        END
        
        @check if the sublist in the position of the root is in the proper
        @structure
        IF
          @if the tree is still valid
          isNotValid 0 ==
          
          @but the sublist is not
          inL1 LTemp HEAD GET 'LTempSublist' STO
          LTempSublist 0 c35vaV1isSublistValid
          NOT
          
          AND
        THEN
          1 'isNotValid' STO
        END
        
        @if we are here, the root is valid
        @ so put the root in the list of elements to expand
        'LNodes' 
        LTempSublist 2 GET STO+

        @the add the height of the element that we will expand
        @the height is equal to the parent +1 in this case the root has height
        @ 0. The position should be the same of the position in the nodes
        'LNodesHeight' 0 STO+
        
        @then put the sublists' positions in the list telling us
        @which ones have we already extracted
        'LExtractPos' LTemp STO+
        
        @we set the minimum height to a value that unlikely will be matched
        inL1Size 'minHeight' STO
        
        @now let's proceed with the rest of the nodes
        WHILE
          @the tree is still valid
          isNotValid 0 ==
            @it does not need to be checked for every action always,
            @since isNotValid can get only 1, it dosn't need many checks.
            @when it fails, will be reported at the next iteration
            
          inL1Size indexElToExpand \>=
          AND
        REPEAT
          @ we take the next parent node
          LNodes indexElToExpand GET 'parentNode' STO
          LNodesHeight indexElToExpand GET 'parentNodeHeight' STO
          
          @we get the positions of sublists containing the parent node
          inL1 parentNode c36vaV1 'LTemp' STO
          
          @the sublists should be at least 1 and not more than 3
          LTemp SIZE 'LTempSize' STO
          IF
            LTempSize 0 <
            LTempSize 3 >
            OR
          THEN
            1 'isNotValid' STO
          END
          
          @#############
          @LTempSize 1 ==
          
          @if the sublist is just one, the parent node is a leaf
          @we can set if this leaf has the minium height so far
          @but we need to check that the returned sublist position is already
          @one checked
          IF
            LTempSize 1 ==
          THEN
            IF
              @if the sublist position is not what we got already
              LExtractPos LTemp HEAD POS 0 ==
            THEN
              1 'isNotValid' STO
            END
            
            IF
              @if the height of the node is smaller than the minimum
              @set it as new minimum
              minHeight parentNodeHeight >
            THEN
              parentNodeHeight 'minHeight' STO
            END
            
            IF
              @if the height of the leaf is 2 more than the minimum heght,
              @then the tree is invalid
              parentNodeHeight minHeight 1 + >
            THEN
              1 'isNotValid' STO
            END
          END
          
          @#############
          @LTempSize 2 ==
          
          @if the sublist returns 2. It means that there is the parent
          @and a child, but we need to check that this is a child
          @and if it is a child, it was not extracted before and
          @it won't have further children as well 
          IF
            LTempSize 2 ==
          THEN
            @if we have one position known and the other unknown,
            @we need to extract the unknown position (where the parent connects to a child)
            LTemp LExtractPos Diff 'LTemp2' STO @extract the unkown position
            
            IF
              @the positions extracted should be one known and one unknown
              @so the unknown should be 1
              LTemp2 SIZE 1 \=/
            THEN
              1 'isNotValid' STO
            END
            
            inL1 LTemp2 HEAD GET @get sublist
            'LTempSublist' STO
            
            IF
              LTempSublist parentNode c35vaV1isSublistValid
              NOT
              
              @destination already in the destinations (a loop)
              LNodes 
              LTempSublist 2 GET 
              POS 0 \=/
              
              AND
            THEN
              1 'isNotValid' STO
            END
            
            @so here the additional list is valid
            @we have to expand it
            'LNodes' LTempSublist 2 GET STO+ 
            
            'LNodesHeight' parentNodeHeight 1 + STO+
            
            'LExtractPos' LTemp2 STO+
            
            @if there is only a child, this child cannot have more children
            @this has to be checked now otherwise the script loses the "memory"
            @that there is only one child node
            IF
              @So now we have in how many sublists the destination/child node is present
              @this should be exactly one and already extracted, equal to the last
              @addition to LExtractPos

              inL1 LTempSublist 2 GET 
              c36vaV1 LTemp2 \=/
            THEN
              1 'isNotValid' STO
            END
          END
          
          @#############
          @LTempSize 3 ==
          
          @if the sublist returns 3. it means a parent and
          @ two children. Those have to be valid lists and that's it
          IF
            LTempSize 3 ==
          THEN
            LTemp LExtractPos Diff 'LTemp2' STO @extract the unkown position
            
            IF
              @the positions extracted should be one known and two unknown
              @so the unknown should be 2
              LTemp2 SIZE 2 \=/
            THEN
              1 'isNotValid' STO
            END
          
            1 2
            FOR index2              
              @get sublist
              LTemp2 index2 GET 'tempScalar' STO
              inL1 tempScalar GET
              'LTempSublist' STO
              
              @verity it is valid
              IF
                LTempSublist parentNode c35vaV1isSublistValid
                NOT
                
                @destination already in the destinations (a loop)
                LNodes 
                LTempSublist 2 GET 
                POS 0 \=/
                
                AND
              THEN
                1 'isNotValid' STO
              END
              
              @add the destination to the nodes to expand
              'LNodes' LTempSublist 2 GET STO+ 
            
              @add the height of the node just added
              'LNodesHeight' parentNodeHeight 1 + STO+
            NEXT
            
            @add the extracted position
            'LExtractPos' LTemp2 STO+
          END
          
          1 'indexElToExpand' STO+
        END
        
        isNotValid NOT
      \>>
    \>>
    
    c35vaV1isSublistValid
    @ given a list (sublists of another)
    @ assumes that the list contains 2 elements
    @ of which the one passed as argument is the source, so the first one.
    @requires list library of DavidM
    
    @it seems working
    \<<
      1 "isValid" DROP
    
      \->
      @input
      inL1
      source
      
      @local var
      isValid
      
      \<<
        IF
          inL1 SIZE 2 \=/
        THEN
          0 'isValid' STO
        END
        
        IF
          isValid 1 ==
        THEN
          IF
            inL1 source POS 1 \=/
            inL1 source LCNT 1 \=/
            OR
          THEN
            0 'isValid' STO
          END
        END
        
        isValid
      \>>
    \>>
    
    c36vaV1
    @given a list made of sublists
    @returns the sublists (positions) that contain a given element
    
    @it seems working
    \<<
      {} "resList" DROP
        @in the case it will be the result when no match is found
      
      \->
      @input
      inL1
      element
      
      @local var
      @L1size
      resList
      \<<
        
        1 inL1 SIZE
        FOR index
          inL1 index GET  @get sublist
          element POS @get the position
          IF
            @if the element is present (at least once)
            DUP 0 \=/
          THEN
            @at the position to the result
            'resList' index STO+
          END
          DROP @clean the stack
        NEXT
        
        resList
      \>>
    \>>

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 - 06-14-2017 06:02 PM



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