Post Reply 
Programming puzzles: processing lists!
08-21-2017, 07:30 PM (This post was last modified: 08-22-2017 06:51 AM by pier4r.)
Post: #202
RE: Programming puzzles: processing lists!
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)

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-21-2017 07:30 PM

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