Programming puzzles: processing lists!

[DavidM]

(08-19-2017 09:59 PM)pdo Wrote:  I couldn't resist. It hooked me in again, so here's my RPL translation of the Lisp program I posted. It's not particularly pretty, but I thought I'd post it anyway.
...

I didn't try anything longer for fear of running out of memory and/or battery power! (I am using a 49g+ so can't run it off USB power.)

Taking your output and sorting it in a similar way to several previous attempts seems to show a match, so it appears to me that you've got a good solution here, Paul. It's compact, and it works, so what's not pretty about it?

Regarding the memory situation, I did attempt a 12-team run with your code on a near-empty (emulated) 50g, and it resulted in an "Insufficient Memory" error and left 946 entries on the stack. I turned off the "Last Stack" mode setting and tried again to see if not saving stack configurations would allow it to get further. Same error, same number of stack entries. MEM reports 183294.5 bytes available at that point, which makes me wonder if the "wall" that's being hit is actually the internal RPL return stack running out of space.

Whatever the issue, it appears that 10 is probably the max number of teams that can be processed this way on a 50g. That seems like a reasonable maximum since 12 teams would result in a list of 10395 entries, and even doing something simple on a 50g with a list of lists that size would be problematic.

Very nice work!

[pier4r]

So I am attempting another revision of the hash function (still gawk for the moment. Pentium M 1.73ghz, 1gb ram, win xp sp3, cygwin 2.5.2).

4 teams, 3 match days
6 teams, 15 MD
8 team, 105 MD
10 teams, 945 MD (13 seconds)
12 teams, 10395 MD, (51 min ).

I am impressed that the formula from pdo to determine the number of match days seems that simple. I mean I do not have problems with the formula, but with "how can I be sure that I avoid that possible duplicates gets counted?". I couldn't see it in the formula, I thought more constraints were needed.

So with the formula the possible match days with 12 teams should be 10k and counting, with 14 teams 135k, with 16 teams 2millions and counting. Therefore unless I polish the data structures and the procedure, 14 and 16 teams seems out of range for me.

This makes the next challenge limited.

The next challenge in theory should be "find all the possible calendars. That is: collections of match days were every team meet all the others only once" but I guess it has to be limited to 8 teams for the hp50g.




All this was a by product of an open problem that I am trying to solve, how to evaluate the swiss tournament format.

The problem with the swiss tournament is that - given the teams with certain scores after a certain number of match days - ideally the teams should be paired in a way that the sum of the distances between scores of opposing teams is minimized. All this while avoiding that a team plays against a team already met.

So my idea was "ok I collect all the possible match days, then I compute the sum of distances (see above) for all those, then I pick the first compliant match day with the lowest sum".

It does not seem so feasible with such amount of match days. Maybe I should approach in a more heuristic way.

PS: of course I bet that the problem of generating valid swiss tournaments schedules is long solved as well.

edit: I forgot to share the hash function. Damn me (I like when people share and then I do not follow the preachment)
- Given a match day with paitings t1-t2 t3-t4 .... tN-1 tN
- for each pairing compute the value V: (t1+t2)*|t1-t2|
- then save V in a list in the positions related to t1 and t2. So for example if t1 is in 3rd position and t2 is in 7th, it would be { - - V - - - V - ... - } . The other positions will be filled with the V-values of the other pairings related to other teams.
- Given the list of values filled as shown above, concatenate those values in a string.
- this is the hash

So for example the match day 1-2 3-4 5-6 creates the list of values { 3 3 7 7 11 11 } and therefore the hash 33771111 .
Note that in this way changing the order within a pair or between pairs, won't change the hash. So 2-1 6-5 3-4 would produce the same hash.

I think there is a lot of space for improvements (for example in the recurring search whether an hash already exists or not) but first one has to reach a correct result, then optimizations can be applied. (sure, pdo shown that some people are faster than others)

[pdo]

(08-21-2017 07:30 PM)pier4r Wrote:  So with the formula the possible match days with 12 teams should be 10k and counting, with 14 teams 135k, with 16 teams 2millions and counting. Therefore unless I polish the data structures and the procedure, 14 and 16 teams seems out of range for me.

This makes the next challenge limited.

The next challenge in theory should be "find all the possible calendars. That is: collections of match days were every team meet all the others only once" but I guess it has to be limited to 8 teams for the hp50g.

Just an idea, but perhaps the challenge could be tweaked slightly to make it more amenable to calculator implementations. So instead of finding all possible solutions in a big list, you would write a program that is capable of generating any arbitrary solution when supplied with suitable arguments. e.g. for the match-days problem, supplying integers N and M, there M is treated modulo (N-1)(N-3)(N-5)...1, to generate any specific solution. Then the fun would be in proving that any and all solutions are found by some suitably restricted range of input arguments -- ideally a one-to-one mapping from that range to solutions.

Tournament calendars sound interesting -- I haven't really thought about any of this stuff before. As you say, part of the enjoyment comes from just playing around with the problems before you look elsewhere for existing methods.

Paul

[pier4r]

nice idea, I'll add this as variant.

[pier4r]

added #37c and #38

[pier4r]

Added the #39 , it is super easy to solve but I'd like to know if there are quick/elegant ways to solve it.

For example I can write

inputlist
@the the current value
DUP
position
GET

@update it and put it back in the list
increment +
position SWAP
PUT

but that is pretty verbose. In the thread of the listExt of DavidM I thought that one could do

{ 1 2 3 4 5 } { 0 0 3 0 0 } ADD
but building the second list is not less verbose than the process written above. At least for my knowledge.

Does someone know a quick way to build a list with only one non zero value in a specified position?

[DavidM]

(10-17-2017 05:00 PM)pier4r Wrote:  Added the #39 , it is super easy to solve but I'd like to know if there are quick/elegant ways to solve it.

Not sure how elegant this is, but given the arguments in the order specified in your first post (list, position, offset):

Code:

\<<
   PICK3 PICK3
   GET + PUT
\>>

...would seem to work.

(10-17-2017 05:00 PM)pier4r Wrote:  I thought that one could do

{ 1 2 3 4 5 } { 0 0 3 0 0 } ADD
but building the second list is not less verbose than the process written above. At least for my knowledge.

Does someone know a quick way to build a list with only one non zero value in a specified position?

That will work, of course, but you'd end up doing a lot of unnecessary additions for a large list. I haven't tested it, but I can't imagine that those additions would be faster than a simple GET/ADD/PUT combination.

If you still want to play around with that, though, the following can be used to generate a list of 0s with a single constant in a specified position.

Stack setup
3: constant
2: position
1: list size

Code:

\<<
   0 SWAP
   NDUPN →LIST
   SWAP ROT PUT
\>>

[pier4r]

(10-17-2017 07:20 PM)DavidM Wrote:  -cut-

Thanks for your input. The pick3 command is nifty, I am not used to use them (because I prefer to put stack objects in variables).


I also added the code in the collection of userRPL code in the hp calc torrent. If you have code to suggest to add (or threads where to look for code), feel free to tell me.

[DavidM]

(10-17-2017 08:58 PM)pier4r Wrote:  The pick3 command is nifty, I am not used to use them (because I prefer to put stack objects in variables).

When operations involve juggling just 2-3 items on the stack, I don't typically go to the trouble to create variables. Especially as in cases like this, where the operations involved are just a few steps.

(10-17-2017 08:58 PM)pier4r Wrote:  I also added the code in the collection of userRPL code in the hp calc torrent. If you have code to suggest to add (or threads where to look for code), feel free to tell me.

I suppose sequences such as the above seem too isolated and specific to be considered "general purpose programs" to me. I would never think of putting something like that in a library/collection, because it seems more like a code fragment that just comes to mind naturally after one becomes familiar with the language syntax and constructs.

Considering the other example from above:

Over time, SWAP ROT has been implanted in my brain as a simple RPL combination to reverse the order of 3 stack elements. It's too short to turn into a separate program, and I've never written it down anywhere. It's just something that I remember after years of occasionally needing that type of construct while manipulating stack contents. Likewise, NDUPN →LIST is a "phrase" that is etched in my memory for building a list of repeated objects. From those simple building blocks, lots of similar functions to your above example could be created.

I suppose it's just a different way of thinking about programming, and one that feels more natural to me than trying to keep up with lists of short code snippets. It's probably just a stylistic difference in approach more than anything else.

[pier4r]

(10-17-2017 10:42 PM)DavidM Wrote:  I suppose sequences such as the above seem too isolated and specific to be considered "general purpose programs" to me. I would never think of putting something like that in a library/collection, because it seems more like a code fragment that just comes to mind naturally after one becomes familiar with the language syntax and constructs.

I understand your point of view. Nonetheless, while I do agree that having something "fresh" in our memory would be the best solution because if something is already well available in our brain then our actions are faster (a poor analogy are CPU registers or CPU cache); it is also true that not everyone has those commands readily available (me for example).
If they can be used more often than not, then I think is good to collect them so people can look them up. This because searching those commands with the modern search engines is still pretty hard.

For example commands solving a particular challenge, maybe are not that needed, but commands to manipulate 2-3 elements on the stack yes, because it is a situation that happens more often. The same for creating a list of equal entries and so on.

Of course all this depends on the perspective, nevertheless I do prefer to add one entry more to a collection (entry that nevertheless works), than one entry less, people can then pick what they need.

So, suggestions are welcomed because for me alone will take quite some time. Especially for stack related operations that are not my strength.

[John Keith]

(10-17-2017 08:58 PM)pier4r Wrote:  

(10-17-2017 07:20 PM)DavidM Wrote:  -cut-

Thanks for your input. The pick3 command is nifty, I am not used to use them (because I prefer to put stack objects in variables).


I also added the code in the collection of userRPL code in the hp calc torrent. If you have code to suggest to add (or threads where to look for code), feel free to tell me.

One great resource is One-minute Marvels which has a table of combined stack operations. I agree with David, though, that an exhaustive listing of code fragments is less useful than a good knowledge of RPL commands.

Another idea might be a collection of "rules of thumb". As an example, which I mentioned in another thread, stack operations that take a numeric argument (DUPN, ROLL, PICK, etc.) take about 7 times as long to execute as simple operations (SWAP, DUP, ROT, etc.).

John

[DavidM]

(10-18-2017 09:54 AM)pier4r Wrote:  I understand your point of view. Nonetheless, while I do agree that having something "fresh" in our memory would be the best solution because if something is already well available in our brain then our actions are faster (a poor analogy are CPU registers or CPU cache); it is also true that not everyone has those commands readily available (me for example).

If they can be used more often than not, then I think is good to collect them so people can look them up. This because searching those commands with the modern search engines is still pretty hard.

My intent was not to be critical of the process, but rather to explain why I don't tend to think about RPL programming in the same way. It reminds me of one of the differences in how I was taught two different languages. In my teens my Spanish classes were more technically specific... word-for-word comparisons and specific grammatical rules. At the university level, I had zwei Semester of German, and the approach used was more focused on paraphrasing and comparative ideas. The grammar and syntax was still important, of course, but less so than with the Spanish instruction.

Unfortunately I didn't stay immersed with either language, so I never gained any level of proficiency with them. I think of programming (computer, calculator, or otherwise) in a similar fashion -- fluency requires practice, and my proficiency increases when I am able to focus more on approach than specific details of individual steps. The freedom to do that increases as I commit more of the "building blocks" to memory. The best way to do that for me may not be the best way for you, of course. That's why I think of it more as a stylistic approach.

[pier4r]

(10-18-2017 12:51 PM)John Keith Wrote:  One great resource is One-minute Marvels which has a table of combined stack operations. I agree with David, though, that an exhaustive listing of code fragments is less useful than a good knowledge of RPL commands.

Another idea might be a collection of "rules of thumb". As an example, which I mentioned in another thread, stack operations that take a numeric argument (DUPN, ROLL, PICK, etc.) take about 7 times as long to execute as simple operations (SWAP, DUP, ROT, etc.).

John

One minute marvels are already included. The rules of thumb would be useful too, the problem is that are not that common. I insert yours anyway. If you know any source of them, please feel free to point them out.

Another idea would be make tests of them, but it is quite a task.

For code fragments vs knowledge. Once again: brain memory wins hands down. The fragments are useful if one is rusty/new and wants to get things done (at first, improving them later): pick the proper code snippet, use it, then think about it and improve it.


@DavidM: I did not perceive a critic, I just exposed why I think differently.

[pier4r]

Say one has a list with values, of which one appears several times and one wish to remove it.

Fastest way to remove it?
Most compact way?

My quick idea for the moment is something on the line:

- convert the list in a string
- string replace the value
- convert the string back to a list

Since I got impressed by the string operations on the 50g when I am too dumb to think too much and the operation is relatively simple, I put the list in string format for bulk operations.

[DavidM]

(10-31-2017 10:43 AM)pier4r Wrote:  Say one has a list with values, of which one appears several times and one wish to remove it.

Fastest way to remove it?
Most compact way?

Another fairly simple way would be to use MPOS and LRMOV from ListExt. Given a list and an object on the stack, the following should work:

Code:

\<<
   OVER SWAP MPOS LRMOV
\>>

Deleting all of the 5's from 100 repeats of a 1-50 sequence (ie. a 5000-element list with 100 matches) took 3.89s. How does that compare with the string version?

[pier4r]

I need to try, after this program that I am testing if I have time.

Although from feeling I'd say the string approach mentioned by me is slower. I guess it took 5+ seconds for a 1000 entry list.

[DavidM]

The Filter command could also be used from GoferLists.

Using the same scenario that I mentioned above:

Code:

{ 1..50..1..50....50 } « 5 ≠ » Filter

...seems to work, though not exactly a speed demon: 186.6s for the same 5000-element list. Having to execute a UserRPL sequence for each element is probably the bottleneck.

Perhaps there are other combinations of GoferList commands that would be a bit faster.

[Gilles59]

A string version is very very slow with big lists because of the STR-> command at the end.

Code:

Exact mode 
<< -> STR " " + SWAP " " +   SWAP ->STR SWAP " " SREPL DROP STR-> >>

I have no time with the David exemple : it was so slow that I cancelled the program after few minutes

[pier4r]

(10-31-2017 12:40 PM)Gilles59 Wrote:  A string version is very very slow with big lists because of the STR-> command at the end.

Code:

Exact mode 
<< -> STR " " + SWAP " " +   SWAP ->STR SWAP " " SREPL DROP STR-> >>

I have no time with the David exemple : it was so slow that I cancelled the program after few minutes

I do

Code:


\<<
  \->STR
  "1." "" SREPL DROP
  OBJ\->
\>>

it is relatively slow, some 5+ seconds on 1000 terms, not minutes. (I did not test it yet on the 1..50 repeated list. I have another list that has many 1 )

[pier4r]

A way that is still feasible to type on the 50g (therefore no help from a qwerty) but it is also quite quick to generate a list equivalent to the following:

Code:


\<< 12 N 0.1 * +  \>>
1
2118
1
SEQ

@ days that it would take to a folder that is 12 KB and grows every day of 0.1 KB
@ to fill, more or less, 250MB.

SEQ is fast enough, but is there something faster and still manageable to write? ListExt, Goferlist and what not allowed.