Programming puzzles: processing lists!
06-12-2017, 07:46 PM (This post was last modified: 06-13-2017 10:24 AM by pier4r.)
Post: #141
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Neat addition. And yes the revlist works.

So I got some surprising experiences. First the FOR is not as slow as I though compared to DOSUBS / DOLIST (I though was like 10 times slower).

10 times iterating over a list of 100 elements.
dosusbs: avg 0.48 s
dolist: avg 0.50 s
for get: avg 0.93 s (nice pun)
start geti: avg 1.19 s
start headList: avg 0.42 s (surprise! same speed category of dosusbs/dolist) . wrong, the code had a bug.
start DUP TAIL SWAP HEAD: avg 0.96 s
start lrot: avg 3.50 s (I had hopes on this, but likely rotating a list is not that easy)

So if exploding a list with userRPL gets a speed (maybe only for 100 elements, I need to test with 1000) comparable to dolist/dosubs and way better than the compact TAIL + HEAD (those may be few commands but I beleive are intensive), I was thinking that exploding the list and handling it with sysRPL would be super fast, like 3 times faster.

Also I was thinking that LROT would have been faster, maybe is the DUP + HEAD operations that makes it slow.

if the "headTail" procedure holds its speed, it is a great replacement for dosubs/dolists for iterations, at least in userRPL.
Also using a for is not as bad as I thought. Going for 1000 elements now.

Of course, if you see other ways (debug friendly) to iterate over a list, please tell me!

Code:
 headListHelp "input: L1: list output: L2: list without head element L1: head element"      headList   \<<     @given a list in input, leaves on level1 the first element     @ and on level 2 the rest of the list.          @0        @numEl     \->     @external input     list     @local input     @numEl        @elements in the list.     \<<       list OBJ\-> 1 - \->LIST         @reducing the number of elements of 1 for the new list         @we have the tail on level 2       SWAP         @now the head element is on the level 1 stack     \>>   \>> testIterationSpeed     @ testing the efficiency of different iteration approaches,     @ given that DOLIST and DOSUBS although fast are not     @ so debug friendly especially when nested     @ The approach tested the fact to get an element from the list     @ that then can be processed     \<<       {} "baseList" DROP       100 "baseListSize" DROP       {} "resListDosubs" DROP       {} "resListDolist" DROP       {} "resListForGet" DROP       {} "resListStartGeti" DROP       {} "resListStartheadList" DROP       {} "resListStarttailhead" DROP       {} "resListStartLrot" DROP       0 "temp" DROP              \->       @input       iterations              @localVar       baseList       baseListSize       resListDosubs       resListDolist       resListForGet       resListStartGeti       resListStartheadList       resListStarttailhead       resListStartLrot       temp       \<<         baseListSize seqList 'baseList' STO                1 iterations         START                      \<<             @ 10 times, list 100 el: avg 0.48 s             baseList             1             \<<               \->               elementIn               \<<                 elementIn               \>>             \>>             DOSUBS             DROP             @"dosusbs"           \>>           TEVAL DTAG           'resListDosubs' STO+                      \<<             @ 10 times, list 100 el: avg 0.50 s             baseList             1             \<<               \->               elementIn               \<<                 elementIn               \>>             \>>             DOLIST             DROP             @"dolist"           \>>           TEVAL DTAG           'resListDolist'STO+                      \<<             @ 10 times, list 100 el: avg 0.93 s             1 baseListSize             FOR pos1               baseList               pos1               GET DROP             NEXT             @"for get"           \>>           TEVAL DTAG           'resListForGet' STO+                      \<<             @ 10 times, list 100 el: avg 1.19 s             baseList             1             1 baseListSize             START               GETI DROP             NEXT             DROP             DROP             @"start geti"           \>>           TEVAL DTAG           'resListStartGeti' STO+                      \<<             @ 10 times, list 100 el: avg 0.42 s             baseList             1 baseListSize 1 -             START               headList DROP             NEXT             HEAD DROP             @ "start headList"           \>>           TEVAL DTAG           'resListStartheadList' STO+                      \<<             @ 10 times, list 100 el: avg 0.96 s             baseList             1 baseListSize 1 -             START               DUP TAIL SWAP HEAD DROP               @www.hpmuseum.org/forum/thread-8209-post-74498.html#pid74498             NEXT             HEAD DROP             @ "start tail head"           \>>           TEVAL DTAG           'resListStarttailhead' STO+                      \<<             @ 10 times, list 100 el: avg 3.50 s             baseList             1 baseListSize             START               DUP HEAD DROP               -1 LROT             NEXT             DROP             @ "start lrot"           \>>           TEVAL DTAG           'resListStartLrot' STO+         NEXT                  "dosubs"         resListDosubs         "dolist"         resListDolist         "for get"         resListForGet         "start geti"         resListStartGeti         "start headList"         resListStartheadList         "start tail head"         resListStarttailhead         "start lrot"         resListStartLrot       \>>     \>>

Wikis are great, Contribute :)
06-12-2017, 09:41 PM
Post: #142
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-12-2017 07:46 PM)pier4r Wrote:  So I got some surprising experiences. First the FOR is not as slow as I though compared to DOSUBS / DOLIST (I though was like 10 times slower).

10 times iterating over a list of 100 elements.
dosusbs: avg 0.48 s
dolist: avg 0.50 s
for get: avg 0.93 s (nice pun)
start geti: avg 1.19 s
start headList: avg 0.42 s (surprise! same speed category of dosusbs/dolist)
start DUP TAIL SWAP HEAD: avg 0.96 s
start lrot: avg 3.50 s (I had hopes on this, but likely rotating a list is not that easy)
...
Also I was thinking that LROT would have been faster, maybe is the DUP + HEAD operations that makes it slow.

I'm a little surprised that the GET/GETI commands did that well, but I'd guess you'd start to see them slow down a bit as the list sizes grow.

LROT is actually fairly simple, but it does take some time. It basically determines the two sublists that need to be swapped based on the given parameter, makes the sublists, then reassembles them. I might be able to speed it up some with a slightly different approach, but I'm guessing it won't be a significant difference in the final timings. I should add this to my list of things to check, though.

The bulk of the time in the LROT loop is probably from LROT itself. DUP is very fast (it simply copies a pointer, not the actual data), and HEAD is pretty fast as well. My testing on lists of 100 items showed an average timing of .0336 seconds, so a loop of 100 iterations taking 3.36 seconds just for LROT alone would be expected. The remainder of the time for the other commands (and loop overhead) seems reasonable to me.

The internal representation of a list isn't very sophisticated. It's basically a prologue token, each object's data one after the other, and an epilogue token. So any commands that access individual objects within a list have to (literally) traverse/skip each and every object before the one in question in order to access it. In the case of embedded sublists, each element in them also has to be traversed. There's no way to skip over entire embedded sublists, as lists don't contain size information. Even getting the length of a list requires traversing all contained elements. So you can see where the longer a list is, the more time is required to deal with the list's elements.

HEAD is relatively fast because only the first element has to be accessed. TAIL can quickly skip the first element, but it still has to make a copy of the remainder of the list. So it's more sensitive to list size.

I haven't yet traced through DOSUBS and DOLIST to see how they work, but I suspect they do something similar to STREAM (which I have looked at) that allows relatively quick access to list contents by isolating one element at a time in the runstream. That method isn't available to UserRPL programs, as it requires manipulation of the return stack -- a technique that has to be executed very carefully to avoid blowing everything up.
06-12-2017, 09:51 PM (This post was last modified: 06-12-2017 09:52 PM by pier4r.)
Post: #143
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
For lrot I thought you exploded the list and rolled the elements, as I do in user rpl.

This should be faster I think.

And thanks for sharing insights!

Wikis are great, Contribute :)
06-12-2017, 10:19 PM
Post: #144
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-12-2017 09:51 PM)pier4r Wrote:  For lrot I thought you exploded the list and rolled the elements, as I do in user rpl.

This should be faster I think.

And thanks for sharing insights!

Explode/roll/implode would work ok for an argument of 1/-1, but you'd have to loop the rolls for other numbers. Once list sizes get into the hundreds, rolls start to slow down. Try the "roll" method on a list of 1000 items rotated by 500 (or -500). How does it do? LROT handles that in about .19 seconds.

The method I want to test is similar to what I'm currently doing, but would involve loading the elements onto the stack from two different streams and then imploding the whole list. It may not actually be any faster than splitting a list into two pieces and reassembling them, but it's worth a try.
06-12-2017, 10:26 PM (This post was last modified: 06-13-2017 08:16 AM by pier4r.)
Post: #145
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
(06-12-2017 10:19 PM)DavidM Wrote:  Explode/roll/implode would work ok for an argument of 1/-1, but you'd have to loop the rolls for other numbers. Once list sizes get into the hundreds, rolls start to slow down. Try the "roll" method on a list of 1000 items rotated by 500 (or -500). How does it do? LROT handles that in about .19 seconds.

Understood, I thought it was always quite quick. Then Lrot seems to be effective on a big chunk of rotations but not many little ones. Good to know.

The test with lists of 1000 elements is still running, over an hour now.

I'll be interested in the results.

Wikis are great, Contribute :)
06-13-2017, 12:43 AM
Post: #146
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-12-2017 10:26 PM)pier4r Wrote:  The test with lists of 1000 elements is still running, over an hour now.

I'll be interested in the restults.

I ran a single cycle with 1000 list elements, and got these results:

"dosubs" { 7.8397 }
"dolist" { 7.7578 }
"for get" { 34.002 }
"start geti" { 54.728 }
"start tail head" { 33.1366 }
"start lrot" { 4244.4562 }

The LROT loop is most likely a victim of multiple garbage collection events, as the expected time based on previous timings would have been closer to 385 seconds.

Garbage Collections can be made worse by using certain techniques, though I must confess the reasons aren't always obvious. It could be that simply splitting a large list into two sublists is one of those techniques that causes problems. It doesn't make sense to me that it would be any worse than exploding everything then imploding it back, but the evidence speaks for itself!

I'll continue to test some other methods for LROT. I may also "special case" it to use a roll/unroll if the argument is 1 or -1, since that would almost certainly be better than creating two lists to join when one of them has only one element.
06-13-2017, 08:23 AM
Post: #147
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
(06-13-2017 12:43 AM)DavidM Wrote:  I ran a single cycle with 1000 list elements, and got these results:

"dosubs" { 7.8397 }
"dolist" { 7.7578 }
"for get" { 34.002 }
"start geti" { 54.728 }
"start tail head" { 33.1366 }
"start lrot" { 4244.4562 }

You saved me. The night is passed but the 50g is still working. Based on your measurements I would expect 13.5 hours for 10 cycles.

Impressive how headList dropped his efficiency and started to be not linear (so exploding a list does not help too) and impressive for + get. I remember now I tested it with 1000 elements and I was getting like 35 seconds. Even for it is not linear (one would expect 9 seconds, 10 times 0.9, not 35) but still only "5" times slower than the DOx commands. Also tail+head very quick.

Quote:The LROT loop is most likely a victim of multiple garbage collection events, as the expected time based on previous timings would have been closer to 385 seconds.

I'll continue to test some other methods for LROT. I may also "special case" it to use a roll/unroll if the argument is 1 or -1, since that would almost certainly be better than creating two lists to join when one of them has only one element.

Yes I guess special cases of an "handful" of elements rotated (I do not know a meaningful threshold, but maybe up to +10 , -10 ?) would make LROT really effective even for multiple calls.

Wikis are great, Contribute :)
06-13-2017, 10:06 AM (This post was last modified: 06-13-2017 11:49 AM by pier4r.)
Post: #148
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
In the meanwhile my 50g finished. Those are the results for 10 iterations over lists of 1000 elements (the same as the one from David, just to confirm the results. Wait not, there is one that does not fit)
"dosubs" avg { 7.85 }
"dolist" avg { 7.76 }
"for get" avg { 34.08 }
"start geti" avg { 54.86 }
wrong: "start headList" avg { 4.12 } (instead of 535 s. What's going on here? Surely replicating the test in different setups helps)
"start headList" avg { likely 535 as David tested } I found a bug and I checked the code for a list of 100 elements, it returns 1.66s on average (I corrected the older post). So likely it uses 530 seconds or more on 1000 elements. I do not have the time, at the moment, to let it run.
"start tail head" avg { 33.38 }
"start lrot" avg { 4867.04 }

I'll have to double check the headList result because it seems to good to be true. Moreover david reports 535 seconds, mine 4 seconds.

Edit: checked, indeed there was a bug.

Anyway, all in all, the for + get is quite feasible as subsitute for nested iterations of dolist/dosubs

Wikis are great, Contribute :)
06-13-2017, 06:23 PM
Post: #149
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-13-2017 10:06 AM)pier4r Wrote:  ...Anyway, all in all, the for + get is quite feasible as subsitute for nested iterations of dolist/dosubs

After spending more time than I care to admit trying alternative methods for LROT, I've come to the conclusion that any method that involves breaking the list apart into its constituent elements will eventually lead to a heart-stopping garbage collection if the function is called repeatedly in succession with a large-ish list as its argument. I was able to get it to the point where they were a bit less often, but it only delayed the inevitable.

So I've decided to try going the route I originally wanted to go in the first place, but thought might not be worth the hassle: I'll recreate the list by copying the two blocks of memory containing the reversed parts into a new list object directly. It will require a bit more setup (and a lot more code), but it should be a relatively fast option that is nicer to the overall memory footprint of the machine. It will be a good exercise that may have other benefits as well for the other functions I'm contemplating.

Regarding the GET performance, it occurs to me that I should probably temper my criticism of its performance. GET is better than PUT, owing to the fact that it's relatively quick to skip a series of objects when you don't actually have to explode them. But I still maintain that if you know you need to manipulate more than a couple of items in a list (or array, though they are a bit more efficient), it's better to break them apart and then reassemble them later than to loop a bunch of GET/PUT pairs.
06-13-2017, 10:00 PM
Post: #150
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Well from a completely ignorant point of view I somehow believe that consuming a list (for iterations) is somehow quick (indeed your tail head method is as fast as for + get). Just one has to extract elements properly. For this I asked you a sysrpl approach, because maybe there is a way.

Wikis are great, Contribute :)
06-14-2017, 05:40 AM
Post: #151
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-13-2017 06:23 PM)DavidM Wrote:  I'll recreate the list by copying the two blocks of memory containing the reversed parts into a new list object directly. It will require a bit more setup (and a lot more code), but it should be a relatively fast option that is nicer to the overall memory footprint of the machine.

First stab at the new version of LROT (LROT7 below) is promising:

\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{LROT} & 0.0259 & 0.0339 & 0.1006 & 0.1820 & 50 \\
\textbf{LROT7} & 0.0262 & 0.0299 & 0.0592 & 0.0945 & 50 \\
\hline
\end{array}

Timings are comparable to the original for smaller lists, but it scales nicely as the list sizes grow. And it's much nicer with regards to the memory footprint, in that it doesn't explode the list and rebuild it. Completed the 1000-element "stress test" (1000 loops with DUP/HEAD/etc.) in about 125 seconds.
06-14-2017, 08:04 AM (This post was last modified: 06-14-2017 08:06 AM by pier4r.)
Post: #152
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Nice. and 125 seconds vs 4800 is quite an improvement. Because, at least from my pov, I do believe that the average use case of rotating a list is not rotating it once, but multiple times.

Wikis are great, Contribute :)
06-14-2017, 08:57 AM (This post was last modified: 06-14-2017 12:08 PM by pier4r.)
Post: #153
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
RE: Programming puzzles: processing lists!
@DavidM: another request if I may ask.

POS , as far as I know, returns the first matching position in a list.

What if I want to know all the positions that matches the element? I did, for one of the challenges, an helper routine. Do you find reasonable to develop one for your library?

Small argument by me: whether a routine it is good already in userRPL, it does not mean that it ready available for a user (which has to find it or develop it), that is the reason to have a "useful" library.

request:
Code:
 returnAllPosHelp "input: The built in POS, as far as I know, returns only the first match. L2: input list L1: element to search output L1: list of position where elment appears in list "      returnAllPos   \<<     { } @resultList     \->     @input     inputList     elementV     @local     resultList          \<<       inputList       \<<         \->         value         \<<           IF             value elementV ==           THEN             'resultList' NSUB STO+           END         \>>       \>>       DOSUBS       resultList     \>>   \>>

edit. another request, list contains
Code:
 listContainsHelp "input: 2: list L1  1: list L2 output: 1: { list of elements in L2 present in L1} remarks: - duplicates not checked. todo: - handle duplicates. If the same element occurs in L2 N times and it appears in L1 K times, with K <= N . Then the element will appear in the result K times, not N. "           listContains     @it seems to work     \<<       {} "resList" DROP              \->       @input       inL1       inL2              @var       resList              \<<         {} @handle empty result                inL2         1         \<<           \->           @input           element                      \<<             inL1 element POS 0 \=/             element             IFT           \>>           \>>         DOSUBS                  IF           DUP SIZE 0 >         THEN           @non empty result           @clear the list before           +         END       \>>     \>>

request: does your library complement goferlist or not? (I would say: until you find faster and/more flexibile code, yes) Because otherwise diff/intersect may be useful.

edit. Also #36

Code:
 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       \>>     \>>

edit: check goferlist from time to time, I have to say that the documentation of the single commands is, well, too "twitter like". Sometimes really cryptic. Whatever the product, a proper documentation is part of its value.

Wikis are great, Contribute :)
06-14-2017, 11:49 AM
Post: #154
 Werner Senior Member Posts: 514 Joined: Dec 2013
RE: Programming puzzles: processing lists!
ALLPOS

Code:
\<<   \-> o   \<<     1.     \<< o == NSUB IFT \>>     DOSUBS   \>> \>>

or, when no match returns an empty resultlist:

Code:
\<<   \-> o   \<<     {} SWAP     1.     \<< o == NSUB IFT \>>     DOSUBS   \>>   IF DUP SIZE THEN + END \>>

Cheers, Werner
06-14-2017, 02:34 PM
Post: #155
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-14-2017 08:04 AM)pier4r Wrote:  Nice. and 125 seconds vs 4800 is quite an improvement. Because, at least from my pov, I do believe that the average use case of rotating a list is not rotating it once, but multiple times.

I agree with you about the multiple rotations, which is part of the reason I went ahead and did this.

To be fair, this is (for a 50g) a fairly extreme situation due to the list size. Exploding a list and then rebuilding it leaves behind unreferenced objects; the number of discards will be (at a minimum) equal to the number of objects in the list + the original list. When you do that rapidly in succession, the "garbage" builds up quickly. It's inevitable that a GC will take place, and when it does, it has to locate/flag-objects-for-disposal/re-compress all of the space they were inhabiting.

The changes I made still leave a large block of memory disposed, but it's contiguous and easily "skippable". When watching a loop make 1000 calls to LROT (v7) operating on a list of 1000 elements, you can barely discern when the GCs occur. The previous version left 1000 disposable objects behind every iteration, so the GCs would lock up the system for a painful period every time they happened.

I should note that this phenomenon is not unique to my library; any activity (whether built-in or user-programmed) that explodes/implodes large lists will be vulnerable to this issue.
06-14-2017, 03:27 PM
Post: #156
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-14-2017 08:57 AM)pier4r Wrote:  @DavidM: another request if I may ask.
...
request: does your library complement goferlist or not? (I would say: until you find faster and/more flexibile code, yes) Because otherwise diff/intersect may be useful.
...
edit: check goferlist from time to time, I have to say that the documentation of the single commands is, well, too "twitter like". Sometimes really cryptic. Whatever the product, a proper documentation is part of its value.

I think of this "working project" as a collaborative effort, and I'm happy to consider all suggestions for additional functions/commands. It continues to be a good exercise for me to consider the application of list processing in solving problems as opposed to my more "iterative" inclinations.

I've been somewhat concerned that showing my earlier timing comparisons with GoferList functions would be perceived as my wanting to replace it (or even "compete" with it). That definitely wasn't/isn't my intent. It seemed like a good benchmark for comparison with similar functions that I'd already created, so I thought it would make sense to show the data that way.

GoferList appears to have been originally created with the idea that it would replicate known list functions from the Haskell language, so I'm guessing that the original developers were less concerned about documenting the commands and only felt the need to provide the minimum needed to use the commands in an RPL context. They probably figured that it's main appeal would be to people who already knew what the functions did, or would seek the meaning in other ways.

I definitely see my library as a complement to GoferList, even though there is a small amount of overlap. If I'm to implement more functions, I'd prefer to focus on those things that aren't already available in GoferList (or trivial to implement). As an example, many of the GoferList commands are designed to apply a user-defined function to a process. I have no desire to replicate that sort of functionality, as I don't think I could really add anything useful to those commands. Gilles' suggestion of a DOPERM command would represent new functionality that definitely would add value (and isn't trivial), so it's high on my list to investigate. So that's more the type of thing that interests me at present.

I'll add your recent suggestions to my list of things to ponder, as I can see where those functions would be useful in a variety of contexts.
06-14-2017, 03:38 PM
Post: #157
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-14-2017 11:49 AM)Werner Wrote:  ...
Code:
...   { } SWAP ...   IF DUP SIZE THEN + END

Nice, Werner. That's a great way to deal with the "no list returned" issue!
06-14-2017, 06:02 PM (This post was last modified: 06-14-2017 06:04 PM by pier4r.)
Post: #158
 pier4r Senior Member Posts: 2,056 Joined: Nov 2014
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 :)
06-15-2017, 06:21 PM
Post: #159
 DavidM Senior Member Posts: 778 Joined: Dec 2013
RE: Programming puzzles: processing lists!
I thought that it might be worth a few more bytes to have two more special-purpose commands that could be wrapped around the same core that's at the heart of LROT: LRLL (List Roll) and LRLLD (List Rolldown). These are functionally equivalent to 1 LROT and -1 LROT, but faster since the amount of rotation doesn't have to be computed from an argument. It also seemed to me that a rotation of 1 or -1 would be common enough to warrant a separate command for those purposes.

The names were chosen to coincide with similar RPL stack-based functionality. LRLL does the same thing as
Code:
\<<    LIST\-> \-> 'lsize'    \<<       lsize ROLL lsize \->LIST    \>> \>>

LRLLD is the same, just replace ROLL with ROLLD.
06-15-2017, 06:30 PM
Post: #160
 Johnny Knoxville Junior Member Posts: 2 Joined: Jun 2017
RE: Programming puzzles: processing lists!
Reading the replies of all experts is just fascinating.
 « Next Oldest | Next Newest »

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