+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: Programming puzzles: processing lists! (/thread-8209.html)
RE: Programming puzzles: processing lists! - pier4r - 05-14-2017 02:08 PM
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
\>>
\>>RE: Programming puzzles: processing lists! - DavidM - 05-24-2017 12:44 AM
After having attempted a handful of these challenges, I realized that I tended to use a couple of recurring methods for several of them. I thought it might be useful for future explorations in list-land if I simply created a few list functions of my own as a challenge to myself. Here's some of the functions I came up with, and samples of how they could be used in the context of these challenges:
LSHF (List Shuffle)
Input
1: { list of 0 or more objects }
Output
1: { same objects as input, in random order }
Shuffles a list of 1000 reals in about 7.3 seconds. This one is more useful for generating test data than any of the actual challenges themselves.
LDDUP (List DeDup)
Input
1: { list of 0 or more objects }
Output
1: { same list with duplicates removed }
This is simply a UserRPL wrapper around the internal COMPRIMext command. Makes short work of #21:
Code:
\<< LDDUP \>>LREPL (List Replace)
Input
3: { list of 0 or more objects }
2: { list of target objects }
1: { list of replacement objects }
Output
1: { list from SL3 with objects matched in SL2 list replaced by objects in SL1 list }
The following examples would be solutions to challenges 2 & 12:
Code:
Ch2
\<< { 3 5 } { 4 7 } LREPL \>>
Ch12
\<< { 3 5 } { 5 3 } LREPL \>>LROT (List Rotate)
Input
2: { list of 0 or more objects }
1: rotation value [integer] (neg. for left rotation, pos. for right)
Rotation value of 0 leaves the list unchanged. Rotation wraps accordingly if the rotation value is greater than the size of the list. Sample use for challenge #3:
Code:
\<<
DUP SIZE
3 / FLOOR LROT
\>>LMRPT (List Multiple Repeat)
Input
2: { list of 0 or more objects }
1: repeat factor [integer]
Output
1: { list with same objects from SL2 input repeated as directed by repeat factor }
A repeat factor of 1 returns the same list. A repeat factor of 0 returns an empty list. Otherwise, the list contents are repeated in the same order as the original list. This one wouldn't be hard to do in UserRPL, but this version's advantage is that it is quite speedy -- creating a list containing 20 repeats of 50 real numbers (for 1000 final list elements) completes in about 0.09 seconds. Examples:
Code:
{ 1 2 3 } 0 LMRPT => { }
{ 1 2 3 } 1 LMRPT => { 1 2 3 }
{ 1 2 3 } 3 LMRPT => { 1 2 3 1 2 3 1 2 3 }LSUM (List Sum)
Input
1: { list of 0 or more objects }
Output
1: <the result of the list elements added together>
This command is essentially the same as \GSLIST, but it also accepts an empty list or a list with only 1 element as input. I chose to give a result of 0 for any empty list, simply because it fit my needs.
The sum of a single element is simply that same element. In the same fashion as \GSLIST, object types must be compatible or an error will result.LEQ (List Equal)
Input
1: { list of 0 or more objects }
Output
1: 0 (FALSE) or 1 (TRUE)
This checks to see if there are any non-matching elements in the list. For purposes of this function, an empty list assumes a result of TRUE as there are no non-matching elements. Likewise, a list of 1 element is also assumed to be TRUE for the same reason.
LRPCT (List Repeat Count)
Input
1: { list of 0 or more objects }
Output
1: { { elements in the order encountered } { number of repetitions of each element in the prev. list } }
Example: { 1 1 1 2 3 1 } => { { 1 2 3 1 } { 3 1 1 1 } }
An empty list will result in a list of two empty lists { } => { { } { } } for consistency. This one proved to be useful for several of the challenges, especially when combined with LEQ:
Code:
Ch6
\<<
SORT LRPCT
LIST\-> DROP NIP
LEQ
\>>
Ch9
\<<
LRPCT
LIST\-> DROP
LEQ SWAP
{ 3 5 3 } ==
AND
\>>
Ch10
\<<
SORT LRPCT
LIST\-> DROP
==
\>>I did this mostly as a personal exercise for myself, but I'm happy to share the library containing these commands if anyone's interested.
RE: Programming puzzles: processing lists! - John Keith - 05-24-2017 01:33 PM
(05-24-2017 12:44 AM)DavidM Wrote: ... but I'm happy to share the library containing these commands if anyone's interested.
Of course we are. :-)
RE: Programming puzzles: processing lists! - DavidM - 05-24-2017 03:29 PM
(05-24-2017 01:33 PM)John Keith Wrote:(05-24-2017 12:44 AM)DavidM Wrote: ... but I'm happy to share the library containing these commands if anyone's interested.Of course we are. :-)
OK, now that I've given some thought to this, a potential issue has come to mind. 5 of the functions I created do inherent equality comparisons between elements of a list. In the case where the elements are numeric, there's a distinct difference between approximate and exact integers (eg. "1" vs. "1." [or "1," depending on your current fraction mark]). The way things are currently handled, "1" is considered to be different from "1.". So, for example, the LEQ command referenced above returns FALSE (0.) for the list { 1 1. }. It's not clear to me right now if this is actually a problem, or simply a non-intuitive feature.
Even some of the built-in functions handle this situation differently. For example:
{ 1 } { 1. } == returns 0., whereas 1 1. == returns 1 (note that you have to be in exact mode to begin with when typing this in manually).
I could change the commands to make them look for this situation and accommodate it, but it would degrade performance somewhat. Is it worth it?
RE: Programming puzzles: processing lists! - pier4r - 05-24-2017 03:51 PM
David I started the processing list challenges exactly with the idea that slowly I would have created my library of solutions to understand better the list processing, so yay that it worked also for someone else! (whoever created libraries, please share!)
Sure sharing is great (why not the software library section?) and I do think that one could provide two versions of the command if needed, one generic and one optimized.
I'm still blocked with the challenge on the graph, due to debugging problems with list operations. Either I go with for loops, but it is super slow (I'll try later with the new rpl), or I substitute dolist and dosubs with routines easy to debug, using the stack, but it is super not motivating. The alternative is to try other languages (no sysrpl) like new rpl / basic / hpgcc.
Since I'm interested to solve the damn problem I'm using it to explore sqlite, so at the moment I'm solving it with sql only (of course not on the 50g, not yet at least, I'm using an embedded device that has half of the power of a Hp prime. Actually writing a sqlite like db on the prime is an idea) but still I fight with bugs. As soon as I'm finished I'll dive in new rpl vs user rpl using more list processing (I accumulated in the meanwhile like 10 other challenges to define).
RE: Programming puzzles: processing lists! - DavidM - 05-24-2017 06:12 PM
A quick test shows that the performance degradation is significant when comparing reals and integers for equality. A worst-case situation for LEQ checking 1000 list elements went from 0.69 seconds to 3.14. A similar test for LRPCT went from 0.66 seconds to 3.07. I may be able to speed that up by pre-checking types to see if the more permissive equality check is even needed. The additional tests may offset the advantage, though.
I could do two versions of the affected commands, and I could also create a command to convert any integers in a list to reals. That would allow pre-processing the initial list to a consistent (and faster) domain to begin with, so subsequent operations could all use the simpler equality test. Converting 1000 integers to reals takes about 5 seconds. Not insignificant, but it could still be worth it if it sets up the use of the optimized commands later.
I realize that this set of commands is a bit more application-specific than something like GoferLists. But they may still be of some use.
RE: Programming puzzles: processing lists! - DavidM - 05-24-2017 06:43 PM
(05-24-2017 03:51 PM)pier4r Wrote: I'm still blocked with the challenge on the graph, due to debugging problems with list operations. Either I go with for loops, but it is super slow (I'll try later with the new rpl), or I substitute dolist and dosubs with routines easy to debug, using the stack, but it is super not motivating. The alternative is to try other languages (no sysrpl) like new rpl / basic / hpgcc.
Since I'm interested to solve the damn problem I'm using it to explore sqlite, so at the moment I'm solving it with sql only (of course not on the 50g, not yet at least, I'm using an embedded device that has half of the power of a Hp prime. Actually writing a sqlite like db on the prime is an idea) but still I fight with bugs. As soon as I'm finished I'll dive in new rpl vs user rpl using more list processing (I accumulated in the meanwhile like 10 other challenges to define).
I will confess that I've had no desire to approach that particular challenge, partially because it's probably been at least 20 years since I had to code any kind of graph-traversal routines. Also because it made my head spin every time I tried to reconcile the problem description with any kind of RPL approach. That said, I don't think I'd like to use SQL for it, either. I applaud your efforts and will be happy for you when you solve it.
RE: Programming puzzles: processing lists! - pier4r - 05-24-2017 08:28 PM
(05-24-2017 06:12 PM)DavidM Wrote: A quick test shows that the performance degradation is significant when comparing reals and integers for equality.
I realize that this set of commands is a bit more application-specific than something like GoferLists. But they may still be of some use.
I'm a fan of "look this works under those conditions". Making super generic routines is surely helpful and maybe fun, but one has to start small, otherwise one never starts.
So once you define properly the expected input, that's it. Another person can improve it (as it was done for the GoFerList. Open source has this strength).
(05-24-2017 06:43 PM)DavidM Wrote: I will confess that I've had no desire to approach that particular challenge, partially because it's probably been at least 20 years since I had to code any kind of graph-traversal routines. Also because it made my head spin every time I tried to reconcile the problem description with any kind of RPL approach. That said, I don't think I'd like to use SQL for it, either. I applaud your efforts and will be happy for you when you solve it.
I do believe the #20 (I mistook with the #21 all the time, damn me) is not that difficult to solve, at least trivially. Just for me it is divided in 3 parts:
- generate the input, done.
- process it to let it be analyze by the "find the clique" routine. That is the part where I#m stuck because I tried to use DOLIST and DOSUBS that are not debug friendly. And the idea to process the input is not even that difficult, but the details are.
- compute the largest clique (naively), still undone part but I have the basic algorithm in mind.
Graphs can be nasty, but not that of a problem. I mean especially when I pick the challenges from sites like careercup.com , even if I variate them a bit, the problems cannot be too hard because are meant to be solved in some hours (with python or other comfy languages I guess).
As I wrote multiple times, I got frustrated by the attempts to debug DOLIST/DOSUBS (because sometimes they accept empty stacks as result of the program, sometimes not, for example, it is not so clear) and I started to look elsewhere before trying again. Since one of my todo-s is to explore SQLite (that is pretty beefy in terms of capabilities, I was not expecting that), I started to use it there.
The code, not working, in userRPL, is here: https://app.assembla.com/spaces/various-works-only-code/git-2/source/master/hp48-50_series/programs/general/listOperations.s
lines 2583 - 3117 (as usual, mostly are comments). The list generator and the input collector works. The part to extend the reachability of the nodes does not.
In SQL is here: https://app.assembla.com/spaces/various-works-only-code/git-2/source/master/shell-posix/linux/sqlite_training/graph_sortofclique_201705.sh
So far it works, although the debug was intensive, but now I need to see how to determine the largest clique. I have the algorithm in mind but not its translation in SQL and I don't want to end up to use WITH RECURSIVE ... SELECT . Or maybe yes? dunno.
If I have to be honest, I do think that, in the cause I had debug-friendly DOLIST and DOSUBS, the userRPL approach is way less weird than the SQL approach because userRPL has all those nice functions for lists, SQL does not have much functions to make actions between tables. Or at least I do not know them so far. So the actions allowed by userRPL give more freedom to the user.
edit: I forgot, thanks for the moral support! I actually feel really bad, the #20 was a variant of a question for an amazon software engineer position and I guess they allowed like 1 hour to solve it, and I'm stuck since days.
RE: Programming puzzles: processing lists! - John Keith - 05-24-2017 11:14 PM
(05-24-2017 03:29 PM)DavidM Wrote: OK, now that I've given some thought to this, a potential issue has come to mind. 5 of the functions I created do inherent equality comparisons between elements of a list. In the case where the elements are numeric, there's a distinct difference between approximate and exact integers (eg. "1" vs. "1." [or "1," depending on your current fraction mark]). The way things are currently handled, "1" is considered to be different from "1.". So, for example, the LEQ command referenced above returns FALSE (0.) for the list { 1 1. }. It's not clear to me right now if this is actually a problem, or simply a non-intuitive feature.
Even some of the built-in functions handle this situation differently. For example:
{ 1 } { 1. } == returns 0., whereas 1 1. == returns 1 (note that you have to be in exact mode to begin with when typing this in manually).
I could change the commands to make them look for this situation and accommodate it, but it would degrade performance somewhat. Is it worth it?
I would leave them as they are. One can use I->R and R->I as necessary to convert. I believe it is better to have faster, simpler functions wherever possible.
OTOH, if you decide to post the code for your functions, you may want to post both versions and let subsequent users decide which version they want to use.
John
RE: Programming puzzles: processing lists! - pier4r - 05-25-2017 12:42 PM
(05-24-2017 11:14 PM)John Keith Wrote: I would leave them as they are. One can use I->R and R->I as necessary to convert. I believe it is better to have faster, simpler functions wherever possible.
OTOH, if you decide to post the code for your functions, you may want to post both versions and let subsequent users decide which version they want to use.
John
I agree with this idea.
RE: Programming puzzles: processing lists! - DavidM - 05-25-2017 04:33 PM
OK. I stewed on this for a bit (over)thinking through various options, but ultimately decided to leave things as they were.
For a short time, I considered having the commands check the status of system flag 105 (exact/approximate mode) to see whether they should use the faster equality check (1<>1.) or the slower one (1=1.). But ultimately I feel it's more important that the commands produce consistent results. So I opted against that.
Besides the resounding feedback
, the kicker for me was the realization that the internal command that LDDUP uses (COMPRIMext) also treats integers and reals as not being equivalent. Keeping the other commands as-is maintains consistency with how this built-in command operates.As has already been mentioned, it's simple enough to use I→R on a list to convert all the integers to reals before further processing. That mitigates any potential equivalency issues, and therefore allows all of the routines that need to perform these checks to use the faster methods.
All of these commands were implemented in a Debug4x project as standard SysRPL objects, with a small amount of Saturn code sprinkled in as well. I'll be happy to share it with anyone that's interested -- PM me if you'd like to receive it. I do consider this to be a work in progress, so updates may occur at any time.
Here's a complete list of the commands included in the attached library (#1423):
LCNT (List Count)
Input
2: { list of 0 or more objects }
1: Any object
Output
1: Count
Returns the number of instances of the object in SL1 that exist in the list from SL2.
LDDUP (List DeDup)
Input
1: { list of 0 or more objects }
Output
1: { same list with duplicates removed }
The objects in the result list are in the same order encountered in the original list.
LEQ (List Equal)
Input
1: { list of 0 or more objects }
Output
1: 0 (FALSE) or 1 (TRUE)
Checks to see if there are any non-matching elements in the list. For purposes of this function, an empty list assumes a result of TRUE as there are no non-matching elements. Likewise, a list of 1 element is also assumed to be TRUE for the same reason.
LGRP (List Group)
Input
1: { list of 0 or more objects }
Output
1: { list of 0 or more objects }
Returns the same list with only the first instance of any objects that are repeated. Objects are in the same order as they are encountered.
LMRPT (List Multiple Repeat)
Input
2: { list of 0 or more objects }
1: repeat factor [integer]
Output
1: { list with same objects from SL2 input repeated as directed by repeat factor }
A repeat factor of 1 returns the same list. A repeat factor of 0 returns an empty list. Otherwise, the list contents are repeated in the same order as in the original list.
LREPL (List Replace)
Input
3: { list of 0 or more objects }
2: { list of target objects }
1: { list of replacement objects }
Output
1: { list from SL3 with objects matched in SL2 list replaced by objects in SL1 list }
Example
{ 1 2 3 }
{ 1 3 }
{ 7 8 }
LREPL
result: { 7 2 8 }
LROT (List Rotate)
Input
2: { list of 0 or more objects }
1: rotation value [integer] (neg. for left rotation, pos. for right)
Output
1: { list of 0 or more objects }
Returns the same list rotated per the given rotation value. A value of 0 leaves the list unchanged. Rotation wraps accordingly if the rotation value is greater than the size of the list.
LRPCT (List Repeat Count)
Input
1: { list of 0 or more objects }
Output
1: { { L1 } { L2 } }
L1: Same as LGRP result
L2: The count of each item in L1 that was in the input list
An empty list will result in a list of two empty lists { } => { { } { } } for consistency.
Example
{ 1 1 1 2 3 1 }
LRPCT
result: { { 1 2 3 1 } { 3 1 1 1 } }
LSHF (List Shuffle)
Input
1: { list of 0 or more objects }
Output
1: { same objects as input, in random order }
Randomizes the order of the elements in the list given as input.
LSUM (List Sum)
Input
1: { list of 0 or more objects }
Output
1: <the result of the list elements added together>
This command is essentially the same as ΣLIST, but it also accepts an empty list or a list with only 1 element as input. An empty list as input results in 0. The sum of a single element is simply that same element. Object types must be compatible for addition or an error will result.
LSWP (List Swap)
Input
3: { list of 0 or more objects }
2: index1 [real]
1: index2 [real]
Output
1: { list of 0 or more objects }
The result is the same list with elements <index1> and <index2> swapped.
RE: Programming puzzles: processing lists! - pier4r - 05-25-2017 07:38 PM
Nice! I have two questions though:
(a) why not the software library section ? (to be reached by Google, otherwise here it will be difficult)
(b) redundancy is never bad, so why not also hpcalc.org?
I mean you just mention the code as beta if you don't want to be bold and that's it.
Kudos anyway.
RE: Programming puzzles: processing lists! - DavidM - 05-25-2017 08:06 PM
(05-25-2017 07:38 PM)pier4r Wrote: Nice! I have two questions though:
(a) why not the software library section ? (to be reached by Google, otherwise here it will be difficult)
(b) redundancy is never bad, so why not also hpcalc.org?
I mean you just mention the code as beta if you don't want to be bold and that's it.
Kudos anyway.
Answers to all of the above are the same right now: It's an evolving work that has limited value at present.
I've actually already added a couple of commands since I posted the one above, and I'm thinking there could be a few more in the near future. I really don't feel that it has enough value to warrant posting to Eric's site (hpcalc.org) just yet. It might later, though. I'm still in "exploration mode" and new ideas for more commands are creeping into view. Plus, I still need to take a look at some of the other tools available. I suspect I'm reinventing the wheel with some of this.
Once the command set stabilizes I'll add something to the General Software Library.
RE: Programming puzzles: processing lists! - John Keith - 05-25-2017 09:57 PM
Thanks for posting that, David. I will be very busy for the next week or so but I will give it a try when I get the chance. SysRPL and Saturn assembly are mostly "above my pay grade" but I can see that several of the library functions will be very useful for the sort of programming that I do, and hopefully for others as well. I therefor strongly (and selfishly!) encourage further development of this library.
John
RE: Programming puzzles: processing lists! - pier4r - 05-26-2017 06:36 PM
About reinventing the wheel: maybe, but one never knows the possible future ramifications if one does not start. So, if it is fun, great. I will post more processing challenges and then I'll try to solve them without and with your library (you see, already the idea of using go fer lists lost some priority)
RE: Programming puzzles: processing lists! - John Keith - 05-26-2017 10:48 PM
(05-25-2017 09:57 PM)John Keith Wrote: Thanks for posting that, David. I will be very busy for the next week or so but I will give it a try when I get the chance. SysRPL and Saturn assembly are mostly "above my pay grade" but I can see that several of the library functions will be very useful for the sort of programming that I do, and hopefully for others as well. I therefor strongly (and selfishly!) encourage further development of this library.
John
I tried several of the functions, all with lists of 1000 exact integers.
LCNT, LROT, and LSWP are impressively fast, taking less than 1/4 of a second.
LDDUP is faster than GoferList's Nub (5.3s vs. 6.2s on the list I tried) and returns the same result list.
LGRP takes around 3.2s on a list of 1000 integers in the range 0..9.
LSHF takes about 8.8s and about 0.4s for a list of 52 integers.
There seems to be a bug in the LREPL function- it works properly when executed from the command line but does nothing when used in a program, e.g.:
\<< {10} {999} LREPL \>>
I have not yet tried any other functions.
John
RE: Programming puzzles: processing lists! - DavidM - 05-26-2017 11:47 PM
(05-26-2017 10:48 PM)John Keith Wrote: ...LDDUP is faster than GoferList's Nub (5.3s vs. 6.2s on the list I tried) and returns the same result list.
Wish I could take credit for that! It's using a built-in ROM routine which is apparently nicely optimized.
(05-26-2017 10:48 PM)John Keith Wrote: LSHF takes about 8.8s and about 0.4s for a list of 52 integers.
I could make that one faster, but I chose to stick with using the built-in RAND functions. This requires a couple of extra conversions between reals and BINTs (System Integers), but I figured it was better than me trying to come up with an acceptable alternative for a pseudo-random algorithm.
(05-26-2017 10:48 PM)John Keith Wrote: There seems to be a bug in the LREPL function- it works properly when executed from the command line but does nothing when used in a program, e.g.:
\<< {10} {999} LREPL \>>
Hmmm... is there any possibility that this is one of those situations where the program has approximate numbers as targets and the source list has exact (or vice-versa)? Those wouldn't match, thus appearing as though it wasn't working. Otherwise I'm not sure what else might be happening, as I can't seem to replicate the issue. Any other details you can share would be greatly appreciated.
Thanks for testing this out, John! I'll try a few more tests with LREPL to see if I can get it to misbehave. For the moment, it seems to be working as expected for me. But I'm not assuming that I've tried every possible combination of things that might trip it up.
RE: Programming puzzles: processing lists! - John Keith - 05-27-2017 07:40 PM
All of my tests were with exact integers in exact mode. I have the library stored in port 2 (flash) if that makes a difference.
Example input:
{1 2 3 4 5 6 7 8}
{4}
{9}
Output:
{1 2 3 9 5 6 7 8}
Example 2:
{1 2 3 4 5 6 7 8}
\<< {4} {9} LREPL \>> EVAL
Output: {1 2 3 4 5 6 7 8}
(That is, no replacement)
HTH,
John
RE: Programming puzzles: processing lists! - DavidM - 05-27-2017 08:07 PM
(05-27-2017 07:40 PM)John Keith Wrote: Example 2:
{1 2 3 4 5 6 7 8}
\<< {4} {9} LREPL \>> EVAL
Output: {1 2 3 4 5 6 7 8}
(That is, no replacement)
HTH,
John
John, I appreciate your trying this out. This is truly puzzling.
I just tried the exact same steps you outlined above (in exact mode as well), and got the expected result of { 1 2 3 9 5 6 7 8 }. I also tried putting all three lists into a program, and still had the correct results after execution. There's obviously still something very different about our setups that isn't apparent. I'd love to know what it is.
What happens if you change the numbers? Or better yet, what happens if you use letters (identifiers) instead? Something like
{ A B C D E F G H }
\<< { D } { Z } LREPL \>>
If I do the above, I get the expected result:
{ A B C Z E F G H }
What result do you get?
RE: Programming puzzles: processing lists! - John Keith - 05-28-2017 06:31 PM
DOH!
I realized what the problem was: I had a program in my HOME directory called LREPL, a similar program I had been working on a few weeks ago. I renamed that program and everything is working fine now. ;-)
Sorry for wasting your time, I really appreciate your effort.
Homer Simpson (aka John)