Programming puzzles: processing lists!
01-28-2019, 10:25 PM
Post: #261
 John Keith Senior Member Posts: 399 Joined: Dec 2013
RE: Programming puzzles: processing lists!
BTW, your program reminds me of another useful little program which transforms a list into overlapping sublists:

Code:
 \<< \-> n    \<< n       \<< n \->LIST       \>> DOSUBS    \>> \>>

For example, with the list { 1 2 3 4 5 } on level 2 and 2 on level 1, result is
{{ 1 2 }{ 2 3 }{ 3 4 }{ 4 5 }}
01-28-2019, 11:19 PM
Post: #262
 Thomas Klemm Senior Member Posts: 1,449 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(01-28-2019 10:25 PM)John Keith Wrote:  your program reminds me of another useful little program which transforms a list into overlapping sublists

That's partition with step 1 in Clojure:
Code:
user=> (partition 2 1 [1 2 3 4 5]) ((1 2) (2 3) (3 4) (4 5))

Code:
user=> (doc partition) ------------------------- clojure.core/partition ([n coll] [n step coll] [n step pad coll])   Returns a lazy sequence of lists of n items each, at offsets step   apart. If step is not supplied, defaults to n, i.e. the partitions   do not overlap. If a pad collection is supplied, use its elements as   necessary to complete last partition upto n items. In case there are   not enough padding elements, return a partition with less than n items. nil

Cheers
Thomas
01-28-2019, 11:27 PM
Post: #263
 Thomas Klemm Senior Member Posts: 1,449 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(01-28-2019 10:16 PM)John Keith Wrote:  Shouldn't the result be {{ 1 3 } { 2 4 }{ 3 5 }} ?

Yes, of course. I meant:

{ { 1 2 3 } { 4 5 6 } }

{ { 1 4 } { 2 5 } { 3 6 } }
01-29-2019, 06:04 PM
Post: #264
 John Keith Senior Member Posts: 399 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(01-28-2019 11:19 PM)Thomas Klemm Wrote:  That's partition with step 1 in Clojure:
Code:
user=> (partition 2 1 [1 2 3 4 5]) ((1 2) (2 3) (3 4) (4 5))

Also Partition in Mathematica with the third argument being 1.
02-12-2019, 10:52 AM
Post: #265
 pier4r Senior Member Posts: 1,975 Joined: Nov 2014
RE: Programming puzzles: processing lists!

Wikis are great, Contribute :)
02-12-2019, 04:01 PM (This post was last modified: 02-12-2019 04:10 PM by John Keith.)
Post: #266
 John Keith Senior Member Posts: 399 Joined: Dec 2013
RE: Programming puzzles: processing lists!
A couple of questions / suggestions for #44:

To make #44 more generally useful I would suggest making the value of a win start with 1 rather than the arbitrary value of 7. One can then add an offset to the result list if needed, in your case 6 ADD.

For #44.1, should the streaks be only 1's or any non-zero value?
In either case, the solution is very simple:

Code:
 Spoiler alert: Using the ListExt Library, if the non-zero values are all the same, \<< LRPCT EVAL IFT LMAX \>> If the non-zero values are different, the above code can be preceded with [b]NOT NOT[/b].
02-12-2019, 06:12 PM (This post was last modified: 02-12-2019 06:16 PM by pier4r.)
Post: #267
 pier4r Senior Member Posts: 1,975 Joined: Nov 2014
RE: Programming puzzles: processing lists!

For the #44 I didn't want to use any loop or dosubs going through all the elements keeping track of the last value.

Ideally I wanted to do it with operations applied to lists (like you mentioned, 6 ADD) and if dosubs and co are used, they contain very little commands, ideally one command.

I found something with stream although I tested it on paper and not with the 50g

Code:
 spoiler we have an input list, say I = {1 0 1 1 0 1 0 1 1 1 0 1 0 1} we duplicate it: I 'I2' STO then we add one leading zero to I, making a temp list T = {0 1 0 1 1 0 1 0 1 1 1 0 1 0 1} Then with 2 \<< AND \>> DOSUBS on the list we have the result T1 {0 1 0 1 1 0 1 0 1 1 1 0 1 0 1} T   {0 0 0 1 0 0 0 0 1 1 0 0 0 0} T1 after the AND between adjacent elements we check that T1 has at least one 1, with T1 1 POS. If no 1 is there, we are done. If there is a 1, do I2 T1 ADD 'I2' STO. Thus {1 0 1 1 0 1 0 1 1 1 0 1 0 1} I2 {0 0 0 1 0 0 0 0 1 1 0 0 0 0} T1 {1 0 1 2 0 1 0 1 2 2 0 1 0 1} new I2 Then repeat with a leading zero to make a new T and again with the and between adjacent elements to get a new T1 {0 0 0 0 1 0 0 0 0 1 1 0 0 0 0} new T   {0 0 0 0 0 0 0 0 0 1 0 0 0 0} new T1 again T1 1 POS -> yes I2 T1 ADD 'I2' STO {1 0 1 2 0 1 0 1 2 2 0 1 0 1} I2 {0 0 0 0 0 0 0 0 0 1 0 0 0 0} T1 {1 0 1 2 0 1 0 1 2 3 0 1 0 1} new I2 at the next iteration T1 will be only zeroes, so the attempts are ended. It is extremely slow compared to one pass with DOSUBS or a FOR loop, but I find it neat.

I made like 300 words errors, I am tired tonight.

Wikis are great, Contribute :)
02-13-2019, 12:49 PM
Post: #268
 DavidM Senior Member Posts: 725 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(02-12-2019 06:12 PM)pier4r Wrote:  Ok adapted the #44
...

Taking advantage of the fact that 1+2+3+...n is equivalent to $$\frac{n(n+1)}{2}$$, the following could be used for #44 (uses ListExt):
Code:
Spoiler... \<<    @ get counts of repeated wins/losses    LRPCT    @ separate above results, add 2 to stack    LIST\->    @ swap W/L and count list positions    ROT SWAP    @ perform for each pair (count[n] and W/L)    \<<       IF THEN          DUPDUP * + 2 /    @ W: sum(1..n) = n(n+1)/2       ELSE          DROP              @ L: drop the count       END    \>>    DOLIST    @ sum the result list    LSUM \>>

Adapting the above to accommodate the original (7+8+9...) scoring simply requires a slight adjustment.
02-13-2019, 01:30 PM
Post: #269
 pier4r Senior Member Posts: 1,975 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Nice!

----

Time ago, in this thread or the ListExt thread (or in the little explorations thread) we talked about how slow the expansion of lists is in RPL.

Then I asked "ok, what about we go modifying preallocated lists" and DavidM from his huge experience said that there wouldn't be much of a difference, as list have still to be exploded, copied and so on.

Today I finally decided to test the question (as with computers we are often fortunate that we can test assertions if we have enough time).

This because a recent program on mine based on long lists (1000+ elements) is pretty slow even on the emulator (as the real 50g is already busy). So the question arose again "should I avoid expanding lists?".

Here the results saved also in http://www.wiki4hp.com/doku.php?id=rpl:start

Code:
   @##########################################################################​###   @#   @#   @#   @ some expanding data structures speed test   @ as expanding lists is costly      gpListExp   \<< @on an emu48 emulator on a pentium M 1.73ghz , 741 seconds. Woah.     \<< @always expand a list       {}       1 1000       FOR lvK         lvK +       NEXT     \>>     TEVAL     "listExp"   \>>      gpListRepl   \<< @on an emu48 emulator on a pentium M 1.73ghz , 917 seconds. Woah.     \<< @preallocate list and replace elements       0 1000 NDUPN \->LIST       1 1000       FOR lvK         lvK lvK PUT       NEXT     \>>     TEVAL     "listRepl"   \>>      gpVectRepl   \<< @on an emu48 emulator on a pentium M 1.73ghz , 11.43 seconds. that's fast     \<< @preallocate list and replace elements       0 1000 NDUPN \->ARRY       1 1000       FOR lvK         lvK lvK PUT       NEXT     \>>     TEVAL     "vectRepl"   \>>

I cannot believe the speed on pre allocated arrays (I didn't find a way to expand them without exploding them).

I know that they are less flexible than lists, but from 740 seconds to 11 seconds, woah. I contemplated the journey of exploring what I can do using vectors (and matrices?) but I pushed it aside as with lists there are so many commands.

Likely now I have to go searching or devising functions that works on vectors especially if I use mostly numerical values. Then I can still employ list of vectors.

Wikis are great, Contribute :)
02-13-2019, 09:03 PM (This post was last modified: 02-13-2019 09:05 PM by John Keith.)
Post: #270
 John Keith Senior Member Posts: 399 Joined: Dec 2013
RE: Programming puzzles: processing lists!
My solution to #44, somewhat similar to David's.

Code:
 Spoilers... \<< LRPCT OBJ\->    \<< IF OVER        THEN NIP R\->I LSEQ        ELSE LMRPT        END    \>> DOLIST \>> If real numbers are desired, eliminate the R\->I. To add an offset to the result, put 6 ADD after LSEQ.
.
02-14-2019, 04:10 AM
Post: #271
 DavidM Senior Member Posts: 725 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(02-13-2019 09:03 PM)John Keith Wrote:  ...

Nice, John! I had originally tried something similar to that (but using LSEQR instead when the scores started with 7). When you talked Pier into changing the scoring rules, I suddenly remembered that there was an equation for the sum of 1..n and decided to use that instead.

@Pier (and anyone else): is the progressive points on successive wins a common scenario? I obviously don't play anything enough to recognize that type of scoring. Just curious.
02-14-2019, 10:33 AM (This post was last modified: 02-14-2019 10:34 AM by pier4r.)
Post: #272
 pier4r Senior Member Posts: 1,975 Joined: Nov 2014
RE: Programming puzzles: processing lists!
(02-14-2019 04:10 AM)DavidM Wrote:  Nice, John! I had originally tried something similar to that (but using LSEQR instead when the scores started with 7). When you talked Pier into changing the scoring rules, I suddenly remembered that there was an equation for the sum of 1..n and decided to use that instead.

@Pier (and anyone else): is the progressive points on successive wins a common scenario? I obviously don't play anything enough to recognize that type of scoring. Just curious.

Yes indeed I wanted to start with an offset to "mask" the 1+..+n ; often known via the story of Gauss https://www.nctm.org/Publications/Teachi...-of-Gauss/ .

But then I said "well, people will recognize it in any case, let's make it simple. The offset can be always added". And I modified it according to John's request.

I am still waiting comments from those with better knowledge of RPL that tells me why vectors are so faster than list when modified (see post #269). I should have tested it before! Incoming "processign vectors!" thread.

About the scoring time for digression: I like to organize tournaments (or ratings between players), so every now and then I when I see a new tournament organization I try to analyze it. In the vast majority of cases you have those elements:
- normal round robin (or double round robin).
- 3-1-0 scoring system https://en.wikipedia.org/wiki/Three_points_for_a_win
- like in chess 2-1-0 scoring system.
- knockout format. This allows many upsets the less legs in a match there are. In the US they do right allowing bo5 or bo7 (basket or football playoffs), lowering the chances that one team lucks out a win. See also http://pier4r.wikidot.com/pierworks:arti...formatcomp
- swiss system. That requires less pairings than the round robin but it is better than the knockout format to identify range of players as those ends up being grouped by the same amount of points. Although upset may happen too. I personally love it. There is a lot of interesting little math investigations for the tiebreaks of the swiss system.
https://en.wikipedia.org/wiki/Tie-breaki...ournaments (and much more is there that is not listed)
- match up according to elo ratings or their variants (they result in quite balanced matches): https://en.wikipedia.org/wiki/Elo_rating_system
- I hope I didn't forget anything common.

The last year I noticed the scoring of the lichess titled arenas. In short it is 2-1-0 as normal in chess, but if your last game was a win, the next game has its outcome doubled. It is not bad as it rewards activity but with good play.
I never saw this applied elsewhere so far (surely someone else did but it was outside my sight).

Then from few months I noticed the tournament format in RTS game (art of war 3. Not a bad game ) and I like it a lot. It is exactly the #44 and I find it even better than the lichess arena because it has a cap on the amount of games that can be played (otherwise one would just play a lot hoping in streaks).

The nice part of identifying the score rules in tournaments is the reverse engineering part as the tournament organizer often forget to explain how the scoring works, even if the scoring is uncommon. So one has to crack the scoreboard trying to identify how such scores are possible.

Wikis are great, Contribute :)
02-14-2019, 05:01 PM
Post: #273
 John Keith Senior Member Posts: 399 Joined: Dec 2013
RE: Programming puzzles: processing lists!
On the subject of slow up list operations, there are a couple of ways of speeding up programs where items are appended to an existing list.

One is to store the list in a global (not local) variable. This prevents the system having to save a copy of the original list after every operation.

The best way is to not append items to an existing list in the first place. If there is a way to accumulate the items on the stack and then assemble them into a list using \->LIST that is the fastest way. For example, to create a list of 1000 RANDs:

Slow program:

Code:
 \<< { }  1. 1000.    START RAND +    NEXT \>>

Fast program:

Code:
 \<< 1. 1000.    START RAND    NEXT 1000. \->LIST \>>

Of course there are programs where the items must be in a list because intermediate list processing operations need to be performed. Unfortunately using arrays instead of lists will usually not be helpful in these cases.
02-14-2019, 05:27 PM
Post: #274
 DavidM Senior Member Posts: 725 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(02-13-2019 01:30 PM)pier4r Wrote:  So the question arose again "should I avoid expanding lists?".

I was going to add a note here about building/editing elements on the stack within your program being the usual best performer, but John beat me to punch. Fortunately I saw his response before I hit "Post Reply" on this one. So instead I'll say "yeah, what he said!" There's also an opportunity here to highlight a specific issue, though, so I'll address a distinction about the array/vector that you're creating in your example.

The performance of your third program (the vector/PUT one) is indeed much better, and I believe the main reason is more subtle than simply using a vector instead of a list as the targeted object type. The performance you are seeing implies that the program is creating a type 3 array object, which in turn implies that the emulated calculator was likely set to approximate mode before the program was loaded. Try adding one simple step to that program and watch what happens.

Change:
Code:
0 1000 NDUPN \->ARRY
to
Code:
0 R\->I 1000 NDUPN \->ARRY
(ie. simply add "R\->I" after the first "0")

I believe you'll find that the performance advantage disappears after making that change.

If the calculator is set to exact mode prior to entering/editing the program, the R\->I isn't even required (since the 0 is compiled as an exact integer in that case). If the values going into the array are symbolic (exact integers are considered symbolic for this purpose), the resulting array is created as a type 29 object. It's still an array, but its internal structure is more like a list since the individual elements can be of varying size. This means that it inherits the same inefficiencies of list manipulation.

When you created a type 3 array in your earlier test, you gained an efficiency inherent to that type of object: each element takes up the exact same amount of space, so the offsets to individual elements can be computed in advance and located without having to analyze/traverse all of the preceding elements. That's the main reason that version is faster. It's still making a copy of the original list before making the change, but PUT is far more efficient with a type 3 array object because of how quickly it can locate the target destination within that new copy.

That said, it's still more efficient and usually faster to manipulate items on the stack and then implode into your desired object (list or array) as a last step.
02-14-2019, 06:21 PM (This post was last modified: 02-14-2019 08:03 PM by pier4r.)
Post: #275
 pier4r Senior Member Posts: 1,975 Joined: Nov 2014
RE: Programming puzzles: processing lists!
(02-14-2019 05:27 PM)DavidM Wrote:  When you created a type 3 array in your earlier test, you gained an efficiency inherent to that type of object: each element takes up the exact same amount of space, so the offsets to individual elements can be computed in advance and located without having to analyze/traverse all of the preceding elements. That's the main reason that version is faster. It's still making a copy of the original list before making the change, but PUT is far more efficient with a type 3 array object because of how quickly it can locate the target destination within that new copy.

So it is as I guessed. And I normally don't use exact integers, so the type 3 would be the array in my case.

Yes we already discussed "the fastest data structure is the stack" but stackrobatics may be difficult to handle or maintain when there is some operation done in the middle of the procedure. One ideally likes to save the content somewhere, do the operation, then retrieve the content.
Otherwise, at least in theory, everything could be just stack based, but the effort to maintain such programs for me would be too high.
For those that like stackrobatics surely it would be pleasant.

Therefore knowing that other available built in data structures, in this case type 3 array or - I guess - arrays or matrices of elements of a specific maximum memory footprint (reals), are faster to manipulate can be an advantage at times. I say built in as the multistopwatch uses a type of data structure I never saw before that I think it is not user RPL accessible.

For me it was a semi shock as I asked such question in 2013 or the like and the consensus was "between lists and arrays there is not much difference in speed". Having the lists plenty of functions more (thanks to DavidM too), the lists were the way to go until yesterday.

But when A takes ~ 100 time less the speed of B, according to certain programming styles at least, then A becomes attractive to explore. This unless replicating for A the library available for B is too much effort intensive.

heavily edited: why are the first versions of my messages unreadable even by me?

Wikis are great, Contribute :)
02-14-2019, 09:13 PM
Post: #276
 DavidM Senior Member Posts: 725 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(02-14-2019 06:21 PM)pier4r Wrote:  For those that like stackrobatics surely it would be pleasant.

This made me LOL (seriously). Is there truly anyone who enjoys manipulating large groups of items on the stack? I think the only enjoyment I ever get from it is when I actually finalize some RPL-stack-modifying implementation that succeeds in doing what I actually meant for it do in the first place. There's a feeling like you're blindfolded and you just (successfully) taught someone how to juggle spinning chainsaws. At some point you ask "why do I put myself through this?", but inevitably there are those moments when you realize that something magic just happened in your calculator that you taught it to do. I suppose that's what keeps me dabbling with it. For what it's worth, I see the same issues with RPN vs. RPL code in this regard. It's just that RPL allows you to have much more on the stack, so the complexity can be greater.

(02-14-2019 06:21 PM)pier4r Wrote:  I say built in as the multistopwatch uses a type of data structure I never saw before that I think it is not user RPL accessible.

That data object has a formal type: Library Data, which is a generic RPL object type defined by the O/S. It's essentially an encapsulation of binary data formatted in whatever way the programmer wanted (there is no defined structure within a Library Data object). In that particular case, I did provide a way to export the data into... you guessed it... a list that can be interrogated, analyzed, and manipulated in whatever way you wish. (Technically, it's a multi-layered list, and some of the elements of sublists are actually arrays ).

(02-14-2019 06:21 PM)pier4r Wrote:  For me it was a semi shock as I asked such question in 2013 or the like and the consensus was "between lists and arrays there is not much difference in speed". Having the lists plenty of functions more (thanks to DavidM too), the lists were the way to go until yesterday.

Yes, there are some things which type 3 arrays may make easier/faster. But the more customization you need, the less likely the case that arrays will be significantly better than lists.

(02-14-2019 06:21 PM)pier4r Wrote:  But when A takes ~ 100 time less the speed of B, according to certain programming styles at least, then A becomes attractive to explore.

Absolutely. And I would suggest that RPL is rich enough that there are many different paths to this kind of discovery. Despite many years of tinkering with these systems, I keep seeing people come up with new and interesting ways of solving problems that never cease to amaze.
02-14-2019, 09:23 PM (This post was last modified: 02-14-2019 09:24 PM by pier4r.)
Post: #277
 pier4r Senior Member Posts: 1,975 Joined: Nov 2014
RE: Programming puzzles: processing lists!
(02-14-2019 09:13 PM)DavidM Wrote:  Absolutely. And I would suggest that RPL is rich enough that there are many different paths to this kind of discovery. Despite many years of tinkering with these systems, I keep seeing people come up with new and interesting ways of solving problems that never cease to amaze.

Indeed. It is impressive that RPL even being stable since a while in terms of built in functions, still is a world - at least for me - to explore. I also believe that this is due to contributions scattered around that are difficult to be found and therefore will be rediscovered again.

Of course having many RPL capable devices and craving to use them helps. (I use the emulator only in case of emergency or extreme laziness although I know it is a great work together with debug4x)

Somewhen then I have also the newRPL to explore, that is still growing.

Wikis are great, Contribute :)
02-14-2019, 09:40 PM
Post: #278
 rprosperi Senior Member Posts: 3,309 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(02-14-2019 09:13 PM)DavidM Wrote:  This made me LOL (seriously). Is there truly anyone who enjoys manipulating large groups of items on the stack? I think the only enjoyment I ever get from it is when I actually finalize some RPL-stack-modifying implementation that succeeds in doing what I actually meant for it do in the first place. There's a feeling like you're blindfolded and you just (successfully) taught someone how to juggle spinning chainsaws. At some point you ask "why do I put myself through this?", but inevitably there are those moments when you realize that something magic just happened in your calculator that you taught it to do.

I get this! The first time I got an RPL program like this (exploding a large list onto the stack) to work, I was happy/exhausted/shocked but most of all relieved that my own design worked, despite the many failed attempts prior to that sweet victory.

It's a lot like playing pool - we always take great care for every shot, lining-up all the angles, considering all the obstacles, possibilities, etc. and while most shots go horribly wrong, every now and then a complex shot goes exactly as you planned. The key difference I suppose is when things go horribly wrong in RPL, there is rarely an audience waiting to use the Calculator when you're done.

(02-14-2019 09:13 PM)DavidM Wrote:  And I would suggest that RPL is rich enough that there are many different paths to this kind of discovery. Despite many years of tinkering with these systems, I keep seeing people come up with new and interesting ways of solving problems that never cease to amaze.

This too! Often, long, long after I've thought I had read and/or explored all that could be said about how to use a certain feature or command, some brilliant person here show's up with a new twist, approach or solution revealing some new discovery or insight for that technique, thereby resetting expectations on that topic. It's the best reason of all for coming back and reading posts even on topics that are currently 'not of interest'. Using lists on a 50g is a great example of one of those, so you John and Pier4r can take credit too. Thanks for that!

--Bob Prosperi
03-22-2019, 09:46 PM
Post: #279
 pier4r Senior Member Posts: 1,975 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Added #45 (I checked the other entries and it doesn't seem a duplicate)

Wikis are great, Contribute :)
 « Next Oldest | Next Newest »

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