Programming puzzles: processing lists!
06-15-2017, 09:12 PM
Post: #161
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Nice, the performance is the one of lrot7?

Wikis are great, Contribute :)
06-15-2017, 10:59 PM
Post: #162
 DavidM Senior Member Posts: 790 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-15-2017 09:12 PM)pier4r Wrote:  Nice, the performance is the one of lrot7?

There's not as much time savings as I had originally hoped with the LRLL/LRLLD commands. Probably means that the bulk of the time is spent in the copying. That's not a big surprise, but when you consider that on a 50g the copying is done by a routine that runs at ARM level (instead of Saturn), I was hoping that the initial split point computation was a bigger part of the overall time spent. Here's how the timings look for the new LROT/LRLL/LRLLD:

\begin{array}{|lrrrrc|}
\hline
\textbf{Command} & \textbf{50} & \textbf{100} & \textbf{500} & \textbf{1000} & \textbf{Cycles} \\
\hline
\textbf{LRLL} & 0.0246 & 0.0281 & 0.0586 & 0.0959 & 100 \\
\textbf{1 LROT} & 0.0274 & 0.0308 & 0.0602 & 0.0957 & 100 \\
\hline
\textbf{LRLLD} & 0.0241 & 0.0275 & 0.0541 & 0.0867 & 100 \\
\textbf{-1 LROT} & 0.0278 & 0.0309 & 0.0567 & 0.0876 & 100 \\
\hline
\end{array}
06-15-2017, 11:01 PM (This post was last modified: 06-15-2017 11:02 PM by pier4r.)
Post: #163
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
And doing 1000 single rotations instead? (since the gc should activate itself)

In other words how does it compare against for + get to iterate over a list?

Wikis are great, Contribute :)
06-16-2017, 04:23 AM
Post: #164
 DavidM Senior Member Posts: 790 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-15-2017 11:01 PM)pier4r Wrote:  In other words how does it compare against for + get to iterate over a list?

I did a short run (1 iteration) of several of the tests, with the newest commands added in:

"for get" { 43.1793 }
"start tail head" { 42.0251 }
"start lrot" { 122.0122 }
"start LHDTL" { 29.552 }
"start LRLLD" { 120.5847 }

So LRLLD is slightly faster than the updated LROT. Not anywhere near as fast as the FOR/GET loop, but you have to remember that it's actually doing more than simply getting 1 list element. It literally moves all 1000 of the list elements every time through the loop. So I don't feel too bad about the performance.

I also tested the new command LHDTL, which performed nicely. Not as fast as DOLIST or DOSUBS, but better than FOR/GET and DUP TAIL SWAP HEAD.
06-16-2017, 08:02 AM (This post was last modified: 06-16-2017 08:04 AM by pier4r.)
Post: #165
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
(06-16-2017 04:23 AM)DavidM Wrote:  I also tested the new command LHDTL, which performed nicely. Not as fast as DOLIST or DOSUBS, but better than FOR/GET and DUP TAIL SWAP HEAD.

Yay! What I imagined!

Anyway impressive that the general LROT is so good. Well, even if only for easy of use a command that does a "common action" it is ok i guess. It is like "INCR" instead of 'var' 1 STO+

Wikis are great, Contribute :)
06-18-2017, 02:28 PM
Post: #166
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
@DavidM: is there any repository where one can download a "pre-release" of your library or one has to wait until you upload it here?

Wikis are great, Contribute :)
06-18-2017, 03:23 PM
Post: #167
 DavidM Senior Member Posts: 790 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-18-2017 02:28 PM)pier4r Wrote:  @DavidM: is there any repository where one can download a "pre-release" of your library or one has to wait until you upload it here?

I've attached the latest version. It wasn't until recently that I realized I was inadvertently spamming your challenge thread with these library diversions. The library was a direct result of working on the challenges, but in retrospect it seems off-topic enough to warrant a separate thread. Apologies to everyone!

The release notes and command summaries are included below. Full command descriptions are included in the attached zip.

Teaser:

I've completed several of the pieces needed for DOPERM and DOCOMB commands, and the results so far seem to support continuing that effort. As an example, a test that generates all 5040 permutations of a 7-element list completes in about 125 seconds on a 50g. That's about 40 permutations/second just being dumped on the stack, which seems fast enough to consider using these methods to "feed" combinations/permutations to a user-supplied program. It's likely that any user-supplied program will be the most significant contributor to the overall performance, of course. But at least the underpinnings seem to be working well.

Version 0.8.0d
2017-06-18

- Added new commands:
LHDTL, LRLL, LRLLD, LSEQ, LSEQR

- Changed LSPLT error condition: a sublist size argument that is greater than the actual list size no longer generates an error. In that situation, the full list will be returned as the first sublist.

COMMAND SUMMARY

LCLLT - collates a list of sublists
LCNT - counts objects in a list
LDDUP - removes duplicates from a list
LDST - distributes list items into sublists (reciprocal of LCLLT)
LEQ - checks list items to see if any do not match
LGRP - replaces repeated elements with a single instance
LHDTL - retrieves the first element in a list while leaving the rest on the stack
LMRPT - repeats list contents as indicated by count
LNDUP - creates a list by repeating an object as indicated by count
LREPL - replaces list elements with a substitute object as indicated
LRLL - rolls the list (equivalent to 1 LROT)
LRLLD - "roll down" for the list (equivalent to -1 LROT)
LROT - rotates list elements left or right as indicated by count
LRPCT - list with LGRP elements and another list of the count of each element
LSDIV - subdivides a list into <count> sublists
LSEQ - creates a list of <count> integers
LSEQR - creates a list of integers for the range specified
LSHF - shuffles the contents of a list
LSPLT - splits a list as indicated into two sublists
LSUM - ΣLIST that also handles lists with 0 or 1 element
LSWP - swaps the position of two list elements
LXIL - explodes inner sublists into individual elements (non-recursive)
LXILR - recursive version of LXIL
S→NL - converts a string to a list of numbers
NL→S - converts a list of numbers to a string
S→SL - converts a string to a list of characters
SL→S - converts a list of characters to a string
06-18-2017, 09:07 PM
Post: #168
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Nice!

(06-18-2017 03:23 PM)DavidM Wrote:  I've attached the latest version. It wasn't until recently that I realized I was inadvertently spamming your challenge thread with these library diversions. The library was a direct result of working on the challenges, but in retrospect it seems off-topic enough to warrant a separate thread. Apologies to everyone!

As I said already, I don't mind because it is a library for list processing in a thread of list processing (I mean, rarely the off topic is so close to the topic). Anyway even if you want to make a new thread, start it, otherwise every question that I have will end up here because it is the closest related thread.

Wikis are great, Contribute :)
06-19-2017, 05:47 AM (This post was last modified: 06-19-2017 05:49 AM by Werner.)
Post: #169
 Werner Senior Member Posts: 606 Joined: Dec 2013
RE: Programming puzzles: processing lists!
DOCOMB
In: 3: List
2: n
1: ob
Out: result_list. <ob> is evaluated for every combination of n elements taken from the list. The results are wrapped up in result_list.

Code:
\<<   ROT 0   \-> ob L DoC   \<<     DEPTH DEPTH ROLLD     L SIZE     {}     { 3 PICK 1 -       \-> t n       \<<         IF n         THEN FOR s n s 1 - L s GET 1 \->LIST t + DoC EVAL NEXT          ELSE FOR s L s GET t LIST\-> DROP ob EVAL NEXT         END       \>>     } DUP 'DoC' STO EVAL     DEPTH DEPTH ROLL -     IF DUP 0 > THEN \->LIST ELSE DROP END   \>> \>>

eg.

3: { 1 2 3 4 }
2: 3
1: \<< 3 \->LIST \>>
DOCOMB

will result in

{{ 1 2 3 } { 1 2 4 } { 1 3 4 } { 2 3 4 }}

Cheers, Werner
06-20-2017, 03:32 AM
Post: #170
 DavidM Senior Member Posts: 790 Joined: Dec 2013
RE: Programming puzzles: processing lists!
I learn a new technique every time I see your code, Werner. It will probably take a while for me to decipher everything that it's doing, but that should be expected for an embedded recursive routine inside of list that is EVAL'd. Very creative!
06-20-2017, 05:56 AM
Post: #171
 Werner Senior Member Posts: 606 Joined: Dec 2013
RE: Programming puzzles: processing lists!
I made that a couple of years ago and it's version 9 ;-)
I have DOPERM routines as well, even 2 flavours, as explained in the Vietnamese puzzle post, one to simply go over all permutations (like DOCOMB), and one that will allow you to skip branches at a certain 'level'.

Cheers, Werner
06-25-2017, 11:50 AM (This post was last modified: 06-25-2017 11:53 AM by pier4r.)
Post: #172
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
Going through the algorithm for #34 . The idea is to feed one value at time (without arranging optimally the list in input beforehand, also, shuffle it a bit to be sure it is messy) and perform insertions in a balanced search binary tree (that has to keep the balancing).

As usual in this cases, I go first through the problem on my own. If I struggle too much without progress, I check what was done by the others or I ask in internet communities. Otherwise I appreciate/learn less.

Those cases remember me that before having shiny frameworks that helps you, one first has to understand the procedure by himself.

Wikis are great, Contribute :)
06-28-2017, 04:35 AM
Post: #173
 DavidM Senior Member Posts: 790 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(06-25-2017 11:50 AM)pier4r Wrote:  Going through the algorithm for #34 . The idea is to feed one value at time (without arranging optimally the list in input beforehand, also, shuffle it a bit to be sure it is messy) and perform insertions in a balanced search binary tree (that has to keep the balancing).

Pier, you are an artist as well as a calculator enthusiast! You're also way ahead of me in the challenges as I have fallen behind while, uhm, working on other things.

Here's a couple submissions for #14 and #15, which I opted to do with only the built-in commands. I assumed (perhaps wrongly) that the list wouldn't begin or end with the sentinel (0). They're almost identical, but I suppose that's to be expected:
Code:
Ch14 \<<   0 DUP   \-> list base num   \<<     @ determine the maximum digit in the list     list \<< MAX \>> STREAM     @ add 1 for the selected base     1 + 'base' STO     @ convert the list digits to integers in base 10     list     1     \<<       IF DUP THEN       @ if the current digit isn't 0, then...         num base * +    @ multiply current num by base and add new digit       ELSE              @ else the digit is the separator (0)         num SWAP        @ place current num on stack and reset running total to 0       END       'num' STO         @ save the updated num     \>>     DOSUBS              @ process the list     @ subtract the second number from the first     EVAL num -     @ obtain the sign and ABS of the difference     DUP SIGN SWAP ABS     @ digit counter, for later grouping into final list     0     @ put the difference in SL1     SWAP     @ convert number to digits     WHILE             @ do while the running result > 0       DUP     REPEAT       10 IDIV2        @ determine quotient (SL2) and remainder (SL1)       ROT 1 + ROT     @ update digit counter and move current digit into place     END     DROP              @ drop the remaining quotient (0)     \->LIST REVLIST   @ put resulting digits into a list and reverse them     *                 @ apply sign   \>> \>> Ch15 \<<   0 DUP   \-> list base num   \<<     @ determine the maximum digit in the list     list \<< MAX \>> STREAM     @ add 1 for the selected base     1 + 'base' STO     @ convert the digits to integers in base 10     list     1     \<<       IF DUP THEN       @ if the current digit isn't 0, then...         num base * +    @ multiply current num by base and add new digit       ELSE              @ else the digit is the separator (0)         num SWAP        @ place current num on stack and reset running total to 0       END       'num' STO         @ save the updated num     \>>     DOSUBS              @ process the list     @ add the second number to the first     EVAL num +     @ obtain the sign and ABS of the difference     DUP SIGN SWAP ABS     @ digit counter, for later grouping into final list     0     @ put the difference in SL1     SWAP     @ convert number to digits     WHILE             @ do while the running result > 0       DUP     REPEAT       base IDIV2      @ determine quotient (SL2) and remainder (SL1)       ROT 1 + ROT     @ update digit counter and move current digit into place     END     DROP              @ drop the remaining quotient (0)     \->LIST REVLIST   @ put resulting digits into a list and reverse them     *                 @ apply sign   \>> \>>

You may already be aware of this, and I couldn't remember if this has already been mentioned: the first example for #15 appears to have an incorrect result. Shouldn't it be 201 (base 4) instead of 111?

#16 has three parts, and I wasn't about to skip using my newfangled DOPERM command for these:
Code:
C1601 \<<   @ given list defined in problem description   { 0 8 8 2 }   @ convert to list of characters   48 ADD CHR   @ size of list (needed by DOPERM)   DUP SIZE   @ execute for each permutation   \<<     @ convert character list to string, then convert string to number     SL\->S STR\->     @ determine if it is a multiple of 117     DUP 117 MOD     @ drop the result if it is not a multiple of 117     NOT NOT DROPN   \>>   DOPERM   @ remove duplicates   LDDUP \>> C1602 \<<   @ given list defined in problem description   { 1 3 4 }   @ convert to list of characters   48 ADD CHR   @ size of list (needed by DOPERM)   DUP SIZE   @ execute for each permutation   \<<     @ convert character list to string, then convert string to number     SL\->S STR\->     @ is the current number a prime?     DUP ISPRIME?     @ if not, drop it     NOT DROPN   \>>   DOPERM   @ remove duplicates (not strictly needed for the given argument, but good to have)   LDDUP \>> C1603 \<<   @ given list defined in problem description   { 6 4 0 9 }   @ convert to list of characters   48 ADD CHR   @ size of list (needed by DOPERM)   DUP SIZE   @ execute for each permutation   \<<     @ convert character list to string, then convert string to number     SL\->S STR\->     @ find cube root of the current number     DUP 3 XROOT \->NUM     @ if the cube root is an integer, then...     IF DUP FP 0 == THEN       @ convert it to an exact number and place in a list with the permutation       R\->I 2 \->LIST     ELSE       @ not an integer, drop both the permutation and the cube root       DROP DROP     END   \>>   DOPERM \>>

#17 is very straightforward with DOPERM. It appears that my 50g is OK with up to 7 digits for this particular exercise. 8 digits gives a result of (8!-1) entries (40319), which well exceeds the memory available for the stack. Here's the submission:
Code:
Ch17 \<<   @ convert to list of characters   48 ADD CHR   @ size of list (needed by DOPERM)   DUP SIZE   @ execute for each permutation   \<<     @ output the permutation as a number     SL\->S STR\->   \>>   DOPERM   @ explode final list and drop the first permutation   LIST\-> ROLL DROP \>>
06-28-2017, 05:33 AM
Post: #174
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
No I'm not ahead of you at all (thanks for the compliment but I have to be honest) . It is the forum giving the wrong impression due to my amount of posts. I just collect challenges that I think could be interesting to help learning list processing in rpl, but I didn't solve all of them, I always pick the next one that inspires me.

For example I thought that the #14 and #15 were harder than your relatively compact code so I put them down in the todo list. (and yes I need to check the problem statement, thanks for the feedback)
I may have a look at them after #34.

Furthermore you started to make an interesting library so just to use it (or to see if some commands are missing) I'm trying to coming up with new challenges - once I solve the one I'm on - since I'd like to use your effort instead of letting it be semi hidden in the forum.

Actually it seems to me that using lists to process trees is a good direction, plus I refresh some algorithm and data structures (but little math is involved , my other thread has to wait)

One side note: woah all the permutations of a list with 7 elements!

Wikis are great, Contribute :)
08-11-2017, 10:17 AM
Post: #175
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
added #37 and #37b.

Wikis are great, Contribute :)
08-12-2017, 08:03 AM (This post was last modified: 08-12-2017 08:09 AM by pier4r.)
Post: #176
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
So for the #37 I have the solution below (that heavily uses commands of the library of DavidM to keep speed and debugging ability). Surely it can be polished to be speedy, but first and foremost comes readability/maintainability then maybe speed (I guess I'll have to try newRPL on this one), especially for not so straightforward code.

I call for help because I am not sure about the results reported.

The #37 requires to create, given a list of N teams (N: even), all the valid match days ignoring home/away . So {1 2} and {2 1} are considered the same.
A match day contains all the teams in pairings, and a team appears only once.

Fist idea to solve this: backtracking. I am not really fan of the idea, because it searches through every possible combination and it is a bit clumsy.

Moreover, unless I am mistaken, with 4 teams I have 6 possible pairs ( 4 over 2). With those 6 pairs I can create an upper bound of 15 match days (6 over 2) (the valid ones are less though). With 8 teams I have 28 possible pairs (8 over 2) and an upper bound of 20475 match days ( 28 over 4).
So a backtracking approach would take a bit.

Therefore my plan was/is the following (feel free to produce better approaches!):
- start with a valid match day (the basic one, that pairs consecutive teams in the list)
- then swap two teams (unless they face each other)
- I should have another valid match day
- the problem is that the new valid match day may be equal to an existing one, just with pairs swapped or teams swapped in the same pair. To solve this I need an hash function to compare match days, because if I go with comparing the structure of a match day (a list of lists) it is too costly.
- After a bit of trials it seems that if I consider the sum of the elements in a pair (teams are unique positive integer numbers) and I multiply those sums in a match day, I get an unique number. So if I have (1,2);(3,4) I get 3*7=21 ; if I have (2,1);(3,4) I get the same; if I have (2,3);(1,4) I get 25 and so on.
The problem is that I did not prove it. I have the feeling it works because I was not able to build a counterexample after some trials, but, well, no real proof.
- then when I end all the possible swaps between teams, I consider the current match day "exhausted" as generator for further match days. So I consider the next valid match day - not yet used as generator for new ones - that I found with the method above.
- It ends when no valid match days are left that may generate new ones using the method above.

Due to how I build the match days and my hash function, I am not really sure I get all the valid match days or if I get duplicates (given the constraints).

With 8 teams, for example, I get 67 valid match days and for the sample checks done (I checked like 20 of them), they are all different.

Any suggestion for a better approach? Or any suggestion to prove that the approach is valid?

#37
Code:
 \<<       @ Plan:       @ I could go via backtracking but I do not really like the technique.       @ I may employ something different that is even worse but at least       @ it is more appealing to me.       @ So the idea is the following:       @ - generate one match day (one it is easy)       @ - then go through all the possible pairings of the teams and swap the teams.       @   So if the matchday is ( 1 vs 2 ; 3 vs 4 ; 5 vs 6) one may swap 2 and 3       @   getting the new matchday ( 1 vs 3 ; 2 vs 4 ; 5 vs 6) . Of course does       @   not make sense to swap teams if those are already matching each other       @   (home and away not important).       @ - verify that the new match day, that is valid by construction, is not already       @   collected, if it is not, collect it.              @ note 22:26 11.08.2017: since I am lazy, I do not really like the idea of comparing every       @ matchday valid until now, ignoring the order of matches but considering only       @ pairings. So what could I do? I am not sure but a sort of hash function       @ would help. Hash function that should ignore the order of the pairings.       @ So I thought about using the absolute differences between paired teams and then summing them       @ or multiplying them. But it does not work. For example (1,2);(3,4);(5,7);(6,8) and (1,3);(2,4);(5,6);(7,8)       @ then an idea is to multiply the sum of the pairings.       @ I am not sure it works though, I did not prove it. For the moment I do not       @ see counterexamples so I use it.              { 1 2 3 4 } "teamList" DROP       0 "sizeTeamsList" DROP       {} "currentMatchDayList" DROP       {} "listValidMatchDays" DROP       {} "listValidMatchDaysHash" DROP       {} "baseMatchDays" DROP       {} "baseHashValues" DROP       {} "firstIterationList" DROP       {} "secondIterationList" DROP       0 "swapTeam1" DROP       0 "swapTeam2" DROP       0 "basePosSwapTeam1" DROP       0 "basePosSwapTeam2" DROP       {} "modifiedPairing" DROP       {} "listValidMatchDaysTesting" DROP       1 "tempHashValue" DROP       1 "currentHashValue" DROP       {} "newMatchDayList" DROP              \->       @input       teamsList       @local var       sizeTeamsList       currentMatchDayList       listValidMatchDays       listValidMatchDaysHash       baseMatchDays       baseHashValues       firstIterationList       secondIterationList       swapTeam1       swapTeam2       basePosSwapTeam1       basePosSwapTeam2       modifiedPairing       listValidMatchDaysTesting       tempHashValue       currentHashValue       newMatchDayList              \<<         teamsList SIZE 'sizeTeamsList' STO                  @create a first simple matchday (pair all the teams one after another)         1 sizeTeamsList         FOR index           @ extract a pair, add it to the list.           teamsList index index 1 + SUB           @ make a sublist           1 \->LIST           'currentMatchDayList' SWAP STO+         2 STEP                  @currentMatchDayList           @test: so far it works,                  currentMatchDayList                 \<< \GSLIST \>>         DOSUBS           @we should have the list of sums of each pairing.         \PILIST           @we have the product.         'tempHashValue' STO                  @ we save the current matchday as valid matchday         @ and as base matchday . A base matchday can be used to generate new ones         'listValidMatchDays' currentMatchDayList 1 \->LIST STO+         'baseMatchDays' currentMatchDayList 1 \->LIST STO+                  'listValidMatchDaysHash' tempHashValue STO+         'baseHashValues' tempHashValue STO+                  WHILE           baseMatchDays SIZE 0 >             @as long as there are elements to process         REPEAT           1 'tempHashValue' STO                    @get the next match day           baseMatchDays LHDTL 'currentMatchDayList' STO           'baseMatchDays' STO             @save the rest list                        @baseHashValues LHDTL 'currentHashValue' STO             @this can be used to speed up the computation of the new valid matchday             @once I get to work everything else           @'baseHashValues' STO                      @now consider to swap every possible pair of teams and see if           @something new and valid is generated                      teamsList 'firstIterationList' STO           WHILE             firstIterationList SIZE 0 >           REPEAT             currentMatchDayList 'newMatchDayList' STO                        firstIterationList LHDTL 'swapTeam1' STO             DUP 'firstIterationList' STO             'secondIterationList' STO               @we store the rest list               @for the next first iteration and next second iteration.                          @we will use this later             newMatchDayList swapTeam1 LPOSL 'basePosSwapTeam1' STO                          WHILE               secondIterationList SIZE 0 >             REPEAT               @reset otherwise we lose track of the current match day structure.               currentMatchDayList 'newMatchDayList' STO                            secondIterationList LHDTL 'swapTeam2' STO               'secondIterationList' STO                              @ now we need to swap the position in the pairings between team1 and team2               @ by construction those teams should be in some pairings                newMatchDayList swapTeam2 LPOSL 'basePosSwapTeam2' STO                              IF                 basePosSwapTeam1 basePosSwapTeam2 \=/                   @if the two teams are not directly paired               THEN                 @get the pairings and swap teams                 newMatchDayList basePosSwapTeam1 GET                   @get the pairings with team1                 DUP swapTeam1 POS                   @get position of team1                 swapTeam2 1 \->LIST                 REPL                   @replace with team2                 1 \->LIST                   @for having a sublist for later                 'modifiedPairing' STO                                    newMatchDayList basePosSwapTeam1 HEAD                  modifiedPairing  REPL                 'newMatchDayList' STO                                    newMatchDayList basePosSwapTeam2 GET                 DUP swapTeam2 POS                 swapTeam1 1 \->LIST                 REPL 1 \->LIST                 'modifiedPairing' STO                                  newMatchDayList basePosSwapTeam2 HEAD                  modifiedPairing REPL                 'newMatchDayList' STO                                  @now by construction the match day so generated is valid                 @(since we just swapped two teams that were not challenging each other)                 @we need to see if we do not have it already.                 newMatchDayList                 \<< \GSLIST \>>                 DOSUBS                   @we should have the list of sums of each pairing.                 \PILIST                   @we have the product.                 'tempHashValue' STO                                  IF                    listValidMatchDaysHash tempHashValue POS 0 ==                     @if no design errors were made, the new matchday is valid and                     @not previously found                 THEN                                     'listValidMatchDays' newMatchDayList 1 \->LIST STO+                   'baseMatchDays' newMatchDayList 1 \->LIST STO+                                      'listValidMatchDaysHash' tempHashValue STO+                   'baseHashValues' tempHashValue STO+                 END @if add new matchday               END @ If teams are not in the same pairing.             END @while second team           END @while firsTteam         END @while for baseMatchDays                  "listMatchDays"         listValidMatchDays         "list relative hashes"         listValidMatchDaysHash       \>>     \>>

Wikis are great, Contribute :)
08-13-2017, 10:18 PM
Post: #177
 DavidM Senior Member Posts: 790 Joined: Dec 2013
RE: Programming puzzles: processing lists!
#37 may be more complicated than it first appears. While the 4-team example is fairly straightforward, I need some clarification on the problem for larger team counts.

Let's say you have 6 teams. One possible set of pairings is:

1-2 3-4 5-6

Unlike the case of a 4-team scenario, however, there's the possibility of multiple match-days that still share a common match. Using the above example, here's three potential match-days that all have a 5-6 match:

1-2 3-4 5-6
1-3 2-4 5-6
2-3 1-4 5-6

My question is: should the output include all three of these as match-days? If not, which is the "correct" one, and what makes it so?
08-13-2017, 10:31 PM
Post: #178
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
All three. (This will build up in further challenges)

Wikis are great, Contribute :)
08-14-2017, 12:12 PM (This post was last modified: 08-15-2017 07:31 AM by pier4r.)
Post: #179
 pier4r Senior Member Posts: 2,067 Joined: Nov 2014
RE: Programming puzzles: processing lists!
So, after having done the #37 in userRPL (as reported above, I am not 100% sure that all the possible match days are found, nor duplicates are excluded), I realized that my algorithm is not that fast (and no I am not fan of "full stack no variables").

So I started to search another platform that is as quick, for development, as userRPL. really RPL is amazing.

I tried newRPL since it has the new integration for text files. Unfortunately it does not run in my winXP machine (machine for the 50g). It has to wait until I setup the win10 system.

I tried RPL/2, since it is a great project that deserved to be used too, but the last version of the 4.0.x release does not compile easily in cygwin 2.5.2 , I spent some hours on it but nothing. I'll try another time.

I completely forgot about the HP prime on android (those are the moment I need to use that beast), damn me, and so the closest small and quick language that I know that could do the task is awk (although it lacks of many array manipulation functions or central repositories for libraries, well I do them myself, even if poorly. Python with no curly braces or blocks defined not only by empty lines is not really liked by me)

awk 4.1.4 on cygwin 2.5.2, pentium M 1.73 Ghz.

the following is wrong, see the edits.
4 team: 3 matchdays, 2 seconds.
8 teams: 67 matchdays, 2 seconds.
10 teams: 5002 matchdays, 1min 40 seconds.

Would be helpful if someone else can match the 8 teams matchdays. If there are more or less.

PS: of course this will lead to the next challenge. Given the list of all matchdays, find all the possible valid schedules. That is, with N teams, find N-1 matchdays where every team is paired with any other team. But I will have to clarify it better in the first post.

edit: I found failures in the hash function that I devised. With 6 teams
1-6 2-4 3-5 : value 336
1-5 2-6 3-4 : value 336
1-6 2-3 4-5 : value 315
1-4 2-5 3-6 : value 315

So likely my program does not found all valid match days, but still I did not find duplicates. I need to redesign my hash function.

Edit2: second quick approach. Still not foolproof, just working on intuition and missing counterexamples.
A pair is composed by two different numbers that won't appear in other pairs (given a match day).
So while the sum may match for two different pairings, it is unlikely (I would say impossible, but I did not formalized this), that the sum and the absolute difference between two numbers will match.

Nevertheless having x+y=s and |x-y|=d should describe the two numbers better than the only sum. Then to "combine" this information I use the multiplication, since a number can be determined by its factors uniquely.

So now I do not have only the products of the sum of the teams in each pair, but the product of the sum and the absolute difference between the teams in each pair.

1-6 2-4 3-5 : 7*5 * 6*2 * 8*2 : 6720
1-5 2-6 3-4 : 6*4 * 8*4 * 7*1 : 5376
1-6 2-3 4-5 : 7*5 * 5*1 * 9*1 : 1575
1-4 2-5 3-6 : 5*3 * 7*3 * 9*3 : 8505

Plus found also a mistake in swapping teams.

edit3:
Ok the new hash function seems to be more robust (although not proven).
4 teams, 3 match days
6 teams, 15 match days
8 teams, 100 match days
10 teams, 870 match days

all those pretty quick (I had also to fix some helper functions, gawk is surprisingly empty, ready for new libraries)

Now running 16 teams, is taking a while.

Wikis are great, Contribute :)
08-15-2017, 02:50 PM
Post: #180
 DavidM Senior Member Posts: 790 Joined: Dec 2013
RE: Programming puzzles: processing lists!
(08-14-2017 12:12 PM)pier4r Wrote:  edit3:
Ok the new hash function seems to be more robust (although not proven).
4 teams, 3 match days
6 teams, 15 match days
8 teams, 100 match days
10 teams, 870 match days

I've got a work-in-progress version of a routine that attempts to do this on a 50g, but it's still got some major issues. I keep seeing "reflected" match days in the results as the team size grows, and it slows down intolerably at >6 teams.

If I sort and de-dup the results, it appears to come up with reasonable-looking pairings. I haven't validated them beyond checking for duplicates and just visually scanning for "gross and obvious" failures, so I'm not claiming this to be complete or accurate. I had to leave it running for a while on an emulated 50g (I didn't time it but I think it was >1 hour), so the current approach isn't really viable. I'm attaching my 8-team result so that you might be able to compare the match-days with yours. My current test found 105 possible pairings:

Code:
1-2 3-4 5-6 7-8 1-2 3-4 5-7 6-8 1-2 3-4 5-8 6-7 1-2 3-5 4-6 7-8 1-2 3-5 4-7 6-8 1-2 3-5 4-8 6-7 1-2 3-6 4-5 7-8 1-2 3-6 4-7 5-8 1-2 3-6 4-8 5-7 1-2 3-7 4-5 6-8 1-2 3-7 4-6 5-8 1-2 3-7 4-8 5-6 1-2 3-8 4-5 6-7 1-2 3-8 4-6 5-7 1-2 3-8 4-7 5-6 1-3 2-4 5-6 7-8 1-3 2-4 5-7 6-8 1-3 2-4 5-8 6-7 1-3 2-5 4-6 7-8 1-3 2-5 4-7 6-8 1-3 2-5 4-8 6-7 1-3 2-6 4-5 7-8 1-3 2-6 4-7 5-8 1-3 2-6 4-8 5-7 1-3 2-7 4-5 6-8 1-3 2-7 4-6 5-8 1-3 2-7 4-8 5-6 1-3 2-8 4-5 6-7 1-3 2-8 4-6 5-7 1-3 2-8 4-7 5-6 1-4 2-3 5-6 7-8 1-4 2-3 5-7 6-8 1-4 2-3 5-8 6-7 1-4 2-5 3-6 7-8 1-4 2-5 3-7 6-8 1-4 2-5 3-8 6-7 1-4 2-6 3-5 7-8 1-4 2-6 3-7 5-8 1-4 2-6 3-8 5-7 1-4 2-7 3-5 6-8 1-4 2-7 3-6 5-8 1-4 2-7 3-8 5-6 1-4 2-8 3-5 6-7 1-4 2-8 3-6 5-7 1-4 2-8 3-7 5-6 1-5 2-3 4-6 7-8 1-5 2-3 4-7 6-8 1-5 2-3 4-8 6-7 1-5 2-4 3-6 7-8 1-5 2-4 3-7 6-8 1-5 2-4 3-8 6-7 1-5 2-6 3-4 7-8 1-5 2-6 3-7 4-8 1-5 2-6 3-8 4-7 1-5 2-7 3-4 6-8 1-5 2-7 3-6 4-8 1-5 2-7 3-8 4-6 1-5 2-8 3-4 6-7 1-5 2-8 3-6 4-7 1-5 2-8 3-7 4-6 1-6 2-3 4-5 7-8 1-6 2-3 4-7 5-8 1-6 2-3 4-8 5-7 1-6 2-4 3-5 7-8 1-6 2-4 3-7 5-8 1-6 2-4 3-8 5-7 1-6 2-5 3-4 7-8 1-6 2-5 3-7 4-8 1-6 2-5 3-8 4-7 1-6 2-7 3-4 5-8 1-6 2-7 3-5 4-8 1-6 2-7 3-8 4-5 1-6 2-8 3-4 5-7 1-6 2-8 3-5 4-7 1-6 2-8 3-7 4-5 1-7 2-3 4-5 6-8 1-7 2-3 4-6 5-8 1-7 2-3 4-8 5-6 1-7 2-4 3-5 6-8 1-7 2-4 3-6 5-8 1-7 2-4 3-8 5-6 1-7 2-5 3-4 6-8 1-7 2-5 3-6 4-8 1-7 2-5 3-8 4-6 1-7 2-6 3-4 5-8 1-7 2-6 3-5 4-8 1-7 2-6 3-8 4-5 1-7 2-8 3-4 5-6 1-7 2-8 3-5 4-6 1-7 2-8 3-6 4-5 1-8 2-3 4-5 6-7 1-8 2-3 4-6 5-7 1-8 2-3 4-7 5-6 1-8 2-4 3-5 6-7 1-8 2-4 3-6 5-7 1-8 2-4 3-7 5-6 1-8 2-5 3-4 6-7 1-8 2-5 3-6 4-7 1-8 2-5 3-7 4-6 1-8 2-6 3-4 5-7 1-8 2-6 3-5 4-7 1-8 2-6 3-7 4-5 1-8 2-7 3-4 5-6 1-8 2-7 3-5 4-6 1-8 2-7 3-6 4-5
 « Next Oldest | Next Newest »

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