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
\>>
\>>
Search
Member List
Calendar
Help
/
Programming puzzles: processing lists!
