Post Reply 
Programming puzzles: processing lists!
05-14-2017, 02:08 PM (This post was last modified: 05-14-2017 02:59 PM by pier4r.)
Post: #81
RE: Programming puzzles: processing lists!
So I'm trying to go through the #21 but the RPL syntax, at least with my approach, is not really manageable with such problem.
As usual before one of my programs work I need to debug it and fix those 20+ little mistakes (my average fix rate so far) before it runs. The disadvantage of DOLIST and DOSUBS in this case is the debug mode, one cannot really debug those. At least for what I know.

If one uses NSUB, for example, in the debug mode it is not available (since DBUG executes the program, not DOSUBS), therefore one is doomed to have errors.

Another problem is that I'm not really sure when DOSUBS accepts that the program does not leave on the stack anything, so it can avoid to build a list, or when I should leave on the stack something, so it does not complain.

So I'm a bit stuck and the alternative is to write routines that let me avoid to use DOLIST and DOSUBS for better debug alternatives. I though about iterating lists with FOR and GET or GETI, but they are quite slow.
Just iterating though the elements of a list (adding +1 to the positive integer in the list, then dropping it). DOSUBS with 1000 elements takes 4 seconds, FOR with GET 35 seconds, START with GETI 56 seconds.
I can (of course I'm not thinking about sysRPL or other ways) explode the list and managing it on the stack with a list operation routine but this will lower the tradeoffs of remaining in the (user)RPL realm.

Any ideas? Maybe I should just use another language due to the debug limits, or accept the execution time needed with a FOR loop, but in this case the time will likely explode with a input list of 100 elements for the #21 .

I also did some searches, here on this site google did not help. On the comp.sys.hp48 newsgroup (are there other relevant newsgroups/forums ? Aside from the official but chaotic official HP forum) the search returned slightly related topics, one quite interesting about DOLIST (that I linked on wiki4hp). Surely comp.sys.hp48 is another goldmine that I should read one day, also because it should be more focused on the 48,49,50 series as far as I understood, rather than other great but different HP calculators.

The code, not working so far (DOSUBS complain "BAD argument error") is the following
Code:

    c20vaV1
    @ given a directed graph in a certain format 
    @(I will create also the list generator but also see the comments)
    @ say { { S1 D1 T1 } { SN DN TN } ... { SN DN TN } } 
    @ where Si is a source node
    @ Di is a destination node
    @ Ti is a connection type node
    @ find a clique in it. Or that
    @ a node can reach any other node (even if indirectly)
    @ with a connection of type 1 or type 2 (type 3 is including both)
    
    @TODO: generalize the graph operations for a graph saved with lists
    @ that has a certain structure?
    @TODO: this is a problem to solve that tells me that while userRPL
    @big programs are feasible, trying to nest DOLIST and DOSUBS
    @makes the debugging a nightmare and therefore either another layout is used
    @or another programming language.
    \<<
      
      0  @listSize
      0  @maxNodes
      {} @internalGraphStructure
      {} @internalSubL
      {} @tempSubL
      {} @tempSubL2
      0 @isChangedBool
      
      \->
      @input
      inputList
      @local var
      listSize
      maxNodes
      internalGraphStructure
      internalSubL
      tempSubL
      tempSubL2
      isChangedBool
      
      @Plan:
      @  First we need to parse the input and build an internal empty
      @  version of the graph.
      @  Then we start to fill the graph structure.
      @  Then we need to go through the graph structure and prune it
      @  with possible nodes that have the right connection type.
      @  Then we need to check which of those resulting nodes are connected
      @  to each other.
      \<<
        inputList SIZE 'listSize' STO
          @list size is necessary to create an empty graph structure
          
        @ the internal graph structure has the following format
        @ { L1 L2 L3 ... LN }
        @ where Li is a list containing the information about how the node i
        @ is connected towards the other nodes. In particular:
        @ Li: { LD1 LD2 LD3 ... LDN }
        @ Where LDj is a list containing information about how a the destination
        @ node 'j' is reached. In particular
        @ LDj; Tj
        @ that is, it contains the connection type towards that node.
        @ For how the input is defined, we know that Tj: 1, 2, 3
        @ when Tj is zero, there is no connection.
        @ since the structure cannot be sparse, since it uses positions,
        @ it has to be initialized with all "no connections" so zero values.
        @ This is what we are going to do. Knowing that the number of nodes
        @ cannot exceed the inputSize.
        @ so note that for an input of size X we are going to have X^2 elements in total.
        @ so with 100 we have 10000. Hmm, no, too much so let's modify the input.
        @ If the input if of size X , it can mention maximum sqrt(X) nodes
        
        0 @the initial value of all the connections
        listSize \v/ 0 RND
        DUP 'maxNodes' STO
        NDUPN \->LIST
        'internalSubL' STO
          @this will be the list for destinations.
        
        @ now we need to replicated this enough times to make room for all the
        @source nodes
        
        @1 listSize \v/ 0 RND
        @FOR counter
        @  internalSubL
        @  1 counter PUT
            @ we need to actually fill the source nodes
            @ instead of zero
        @NEXT
          @ we do not need to place the value of a node inside the list,
          @ actually that will stay equal to zero, like
          @ if one transform the internal lists in a matrix
          @ a diagonal of zeroes.
        
        internalSubL
        maxNodes 
        NDUPN
        \->LIST
        'internalGraphStructure' STO
          @now we have the basic graph structure
          
        @processing the input
        inputList
        1
          @normally dosubs is able to determine the number of
          @inputs accepted by the program, but being explict
          @helps, for example readability
        \<<
          @we have the sublist from the input
          @explode it
          OBJ\-> DROP
            
          0 @sourceList
          0 @tmpConnT
          
          \->
          @input
          sourceN
          destNconnT
          connectionT
          @local var
          sourceList
          tmpConnT
          
          \<<
            @ we get the source list
            internalGraphStructure
            sourceN GET
            DUP 'sourceList' STO
            
            destNconnT GET
              @we get the connection type from the source list
            DUP 'tmpConnT' STO
            
            IF
              connectionT \=/
                @we compare the previous connection type
                @with the new one, if they are equal
                @there is no change
            THEN
              @ if the connections are unequal we can sum them
              @ and cap their sum at 3
              tmpConnT connectionT +
              3 MIN
              'tmpConnT' STO
              
              @now we update the source list
              @and then we put it in the internal graph
              internalGraphStructure
              sourceN
              sourceList destNconnT tmpConnT PUT
              PUT
              'internalGraphStructure' STO
            END
          \>>
        \>>
        DOSUBS
        
        @internalGraphStructure
          @debug
          @so far, it works.
          
        @now we need to see from which node which other node we reach.
        @
        @ to do this we observe that at the end what we need is the reachability
        @ list from one node. A node either is reached directly (with a certain
        @ type of connection, or it is reached indirectly).
        @ So, for example if A reaches B, then A reaches all that B reaches.
        @ (I'm pretty sure there exist better algorithms but it is a good training
        @ to try on one's own at least once)
        @ In the end, therefore, we need to sum all the values of the lists of
        @ reachable node given one node (excluding from the sum the source node itself)
        @ and since one node can be reachable from the source node only after few sums,
        @ we need to repeat the process until we have passed on all the nodes
        @ and there was no change in the data.
        
        
        DO        
          0 'isChangedBool' STO
            @assumming no change in the next iteration
          
          1 maxNodes
          FOR sourceN
            @extract the list related to sourceN
            internalGraphStructure
            sourceN
            GET
            DUP 'tempSubL2' STO
              @useful for additions later while iterating on the other duplicate.
            'tempSubL' STO
            
            @ iterate on the elements bigger than zero of the list
            @ extracting the relative position of the list, without
            @ considering sourceN itself.
            tempSubL
            1
            \<<
              0 @ doListCounter
              
              \->
              @input
              destNconnT
              @local var
              doListCounter
              
              \<<
                IF
                  destNconnT 0 >
                    @if the node is reachable
                  NSUB sourceN \=/
                    @if the current examined position is not the same of the
                    @sourceN
                  AND
                THEN
                  @reset
                  1 'doListCounter' STO
                    @to avoid certain elements since we don't have NSUB
                    @see code later
                  
                  @now we put on the stack the actual
                  @list related to the source node and
                  @we get the list of the destination node.
                  tempSubL2
                  internalGraphStructure
                  NSUB
                  GET
                  
                  @now we have on the stack 2 lists, we want to add them
                  @with certain constrainst to keep the connection type
                  @ (if from source I can send only type 1, I cannot make use of the connections of type 2)
                  @and to avoid that the sourceN can reach itself.
                  1
                  \<<
                      @so one element from both lists
                      @saying how the node equal to the position in the list is reached
                      @by source and dest
                    \->
                    @input
                    @the more an algorithm is long, the better to make it readable.
                    @CPU speed comes after brain speed in terms of value
                    @for an individual.
                    connTypeSource
                    connTypeDest
                    @local var
                    
                    \<<
                      IF
                        doListCounter sourceN ==
                      THEN
                        @avoiding to do additions for the position equal to the source.
                        @while the destination itself should have 0 in its list
                        @so won't add anything.
                        @leave 0
                        0
                      ELSE
                        IF
                          connTypeSource connTypeDest ==
                            @if the two elements are equal
                          connTypeSource 3 ==
                            @or the source node already reaches the end node perfectly
                        THEN
                          @we keep only the first element, from the source list
                          @even if the source may not reach the destination properly
                          @the point is that nothing will change.
                          connTypeSource
                        ELSE
                          @if not, it is a bit more complicated
                          @at least for me, to understand why it is complicated, a graph on paper
                          @is helpful, I try to summarize it here.
                          @ (but really a graph with all the possibilities helps
                          @ people like me)
                          
                          @ A, B, C
                          @ A does not reach C
                          @ A reaches B with 1
                          @ if B does not reach C, then A neither
                          @ if B reaches C with 1 or 3, A reaches C with 1
                          @ if B reaches C with 2, A does not reach C
                          
                          @if A reaches C directly or with another node.
                          @if A reaches C already with 3, no further computation is needed
                          @if A reaches C with 1, reaches B with 2, and B reaches C with 2
                          @ then A reaches C with 3 (if A reaches C with 2, nothing changes)
                          @ if A reaches C with 1 and B with 1, nothing changes
                          @ if A reaches C with 1, and B reaches C with 2 and A reaches B with 2
                          @ then A reaches C with 3.
                          @ then there is again the limit on B (if A reaches B with 1 and B reaches C with 2
                          @ nothing changes.)
                          @ etc.
                          
                          IF
                            connTypeSource 0 ==
                              @if the source node cannot reach the further node
                          THEN
                            
                            IF
                                destNconnT 3 <
                                connTypeDest 3 <
                                AND
                              destNconnT
                              connTypeDest
                              \=/
                              AND
                                @if the source reach the destination with 1 or two
                                @ the dest reach the other node with 1 or two
                                @ but those are two connections are different
                                @ there is no improvement on the reachability of the source.
                            THEN
                              connTypeSource
                            END
                            
                            IF
                              destNconnT 3 ==
                                @if the source reaches the destination perfectly
                            THEN
                              connTypeDest
                                @we improve the reachability of the other node using
                                @the reachability of the destination node.
                            END
                            
                            IF
                                destNconnT 3 <
                                connTypeDest 3 ==
                              AND
                                @if the source reach the destination with 1 or two
                                @ the dest reach the other node with 3
                                @then the flow is uninterruped
                            THEN
                              destNconnT
                            END
                          END
                          
                          @###
                          IF
                            connTypeSource 1 ==
                              @if the source node can reach the further node only with 1
                          THEN
                            
                            @now I try to avoid simplification and I follow the schema done on paper
                            @it is uglier but it is ok, also, no CASE ... END
                            @but shortened IFT
                            @Moreover once wrote I can see patterns and collapse code
                            
                            destNconnT 1 ==
                              @if the destination is reached by 1 
                              @ with the dest reaching other with 1, only 1 pass
                              @ if dest reaches other with 2, nothing passes but the
                              @ original connection of the source is 1 (so connTypeSource )
                              @ if the dest reach other with 3, still only 1 passes
                            destNconnT
                            IFT
                          
                              destNconnT 2 ==
                              destNconnT 3 ==
                              OR
                            connTypeDest 1 ==
                            AND
                              @different types of flow, the original
                              @flow remains because the flow of type 2 
                              @(the part missing at the moment)
                              @cannot flow
                            connTypeSource
                            IFT
                            
                              destNconnT 2 ==
                              destNconnT 3 ==
                              OR
                              connTypeDest 2 ==
                              connTypeDest 3 ==
                              OR
                            AND
                              @the source reaches the dest at least with 2, and the dest reaches
                              @other with 2 or 3, the entire flow is improved since
                              @the source can reach other with 1 and (since cannot be 
                              @that it evolved from this node) now also with 2, so it
                              @reaches it with 3.
                            \<< connTypeSource connTypeDest + 3 MIN \>>
                              @we sum and we limit at 3
                            IFT
                          END
                          
                          @###
                          IF
                            connTypeSource 2 ==
                              @if the source node can reach the further node only with 2
                          THEN
                            destNconnT 2 ==
                              @if the destination is reached by 2 
                              @ with the dest reaching other with 2, only 2 pass
                              @ if dest reaches other with 1, nothing passes but the
                              @ original connection of the source is 2 (so connTypeSource )
                              @ if the dest reach other with 3, still only 2 passes
                            destNconnT
                            IFT
                          
                              destNconnT 1 ==
                              destNconnT 3 ==
                              OR
                            connTypeDest 2 ==
                            AND
                              @different types of flow, the original
                              @flow remains because the flow of type 1 
                              @(the part missing at the moment)
                              @cannot flow
                            connTypeSource
                            IFT
                            
                              destNconnT 1 ==
                              destNconnT 3 ==
                              OR
                              connTypeDest 1 ==
                              connTypeDest 3 ==
                              OR
                            AND
                              @the source reaches the dest at least with 1, and the dest reaches
                              @other with 1 or 3, the entire flow is improved since
                              @the source can reach other with 2 and (since cannot be 
                              @that it evolved from this node) now also with 1, so it
                              @reaches it with 3.
                            \<< connTypeSource connTypeDest + 3 MIN \>>
                              @we sum and we limit at 3
                            IFT
                          END  
                        END
                      END
                      1 'doListCounter' STO+
                    \>>
                  \>>
                  DOLIST
                    @this works on multiple lists, dosubs only on one.
                  
                  @ now we should have the addition and we store it with
                  @ the original list.
                  'tempSubL2' STO
                END
                @otherwise if a dest node is not reachable, no changes.
                
                0 @dropping a 0 otherwise DOSUBS complains, why I don't know.
              \>>
            \>>
            DOSUBS 
            DROP
              @dropping the results of dosubs that we do not need.
            
            @here we have finished an iteration of trying to expand the reachability
            @of the nodes in the graph through other middle nodes.
            @so we put back the result as new "source list"
            
            internalGraphStructure
            sourceN
            tempSubL2
            PUT
            @this will return the list
            'internalGraphStructure' STO
            
            @still, for every node the program tries to update the
            @reachability of the other nodes using indirect connections,
            @therefore if this happened, could be that after a further iteration
            @more indirect connections are possible.
            @therefore we check if the source list changed after
            @the procedure above
            IF
              tempSubL tempSubL2 \=/
            THEN
              1 'isChangedBool' STO
            END
            
          NEXT
        UNTIL
          isChangedBool 0 ==
            @there is no change
        END
        
        internalGraphStructure
      \>>
    \>>

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



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