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
\>>
\>>
Search
Member List
Calendar
Help
/
Programming puzzles: processing lists!
