Programming puzzles: processing lists!

[pier4r]

Nice, the performance is the one of lrot7?

[DavidM]

(06-15-2017 09:12 PM)pier4r Wrote:  Nice, the performance is the one of lrot7?

Short answer: yes.

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}

[pier4r]

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?

[DavidM]

(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.

[pier4r]

(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+

[pier4r]

@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?

[DavidM]

(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

[pier4r]

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.

[Werner]

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

[DavidM]

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!

[Werner]

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

[pier4r]

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.

[DavidM]

(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
\>>

[pier4r]

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!

[pier4r]

added #37 and #37b.

[pier4r]

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

[DavidM]

#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?

[pier4r]

All three. (This will build up in further challenges)

[pier4r]

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.

[DavidM]

(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