Threaded Mode | Linear Mode

pier4r · (This post was last modified: 06-14-2017 06:04 PM by pier4r.)

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

      \>>

    \>>