Post Reply 
Programming puzzles: processing lists!
08-12-2017, 08:03 AM (This post was last modified: 08-12-2017 08:09 AM by pier4r.)
Post: #176
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?


      @ 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
      @local var
        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
          @test: so far it works,
        \<< \GSLIST \>>
          @we should have the list of sums of each pairing.
          @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+
          baseMatchDays SIZE 0 >
            @as long as there are elements to process
          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
            firstIterationList SIZE 0 >
            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
              secondIterationList SIZE 0 >
              @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
                basePosSwapTeam1 basePosSwapTeam2 \=/
                  @if the two teams are not directly paired
                @get the pairings and swap teams
                newMatchDayList basePosSwapTeam1 GET
                  @get the pairings with team1
                DUP swapTeam1 POS
                  @get position of team1
                swapTeam2 1 \->LIST
                  @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.
                \<< \GSLIST \>>
                  @we should have the list of sums of each pairing.
                  @we have the product.
                'tempHashValue' STO
                  listValidMatchDaysHash tempHashValue POS 0 ==
                    @if no design errors were made, the new matchday is valid and
                    @not previously found
                  '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
        "list relative hashes"

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 

Messages In This Thread
RE: Programming puzzles: processing lists! - pier4r - 08-12-2017 08:03 AM

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