-
Notifications
You must be signed in to change notification settings - Fork 5
/
ffa.js
327 lines (287 loc) · 10 KB
/
ffa.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
var $ = require('interlude')
, group = require('group')
, Tournament = require('tournament');
function Id(r, m) {
this.s = 1;
this.r = r;
this.m = m;
}
Id.prototype.toString = function () {
return 'R' + this.r + ' M' + this.m;
};
var mId = function (r, m) {
return new Id(r, m);
};
//------------------------------------------------------------------
// Initialization helpers
//------------------------------------------------------------------
var unspecify = function (grps) {
return grps.map(function (grp) {
return $.replicate(grp.length, Tournament.NONE);
});
};
var makeMatches = function (np, grs, adv) {
var matches = []; // pushed in sort order
// rounds created iteratively - know configuration valid at this point so just
// repeat the calculation in the validation
for (var i = 0; i < grs.length; i += 1) {
var a = adv[i]
, gs = grs[i]
, numGroups = Math.ceil(np / gs)
, grps = group(np, gs);
if (numGroups !== grps.length) {
throw new Error('internal FFA construction error');
}
if (i > 0) {
// only fill in seeding numbers for round 1, otherwise placeholders
grps = unspecify(grps);
}
// fill in matches
for (var m = 0; m < grps.length; m += 1) {
matches.push({id: mId(i+1, m+1), p: grps[m]}); // matches 1-indexed
}
// reduce players left (for next round - which will exist if a is defined)
np = numGroups*a;
}
return matches;
};
var prepRound = function (currRnd, nxtRnd, adv) {
var top = currRnd.map(function (m) {
return $.zip(m.p, m.m).sort(Tournament.compareZip).slice(0, adv);
});
// now flatten and sort across matches
// this essentially re-seeds players for the next round
top = $.pluck(0, $.flatten(top).sort(Tournament.compareZip));
// re-find group size from maximum length of zeroed player array in next round
var grs = $.maximum($.pluck('length', $.pluck('p', nxtRnd)));
// set all next round players with the fairly grouped set
group(top.length, grs).forEach(function (group, k) {
// replaced nulled out player array with seeds mapped to corr. top placers
nxtRnd[k].p = group.map(function (seed) {
return top[seed-1]; // NB: top is zero indexed
});
});
};
//------------------------------------------------------------------
// Invalid helpers
//------------------------------------------------------------------
var roundInvalid = function (np, grs, adv, numGroups) {
// the group size in here refers to the maximal reduced group size
if (np < 2) {
return 'needs at least 2 players';
}
if (grs < 2) {
return 'group size must be at least 2';
}
if (adv >= grs) {
return 'must advance less than the group size';
}
var isUnfilled = (np % numGroups) > 0;
if (isUnfilled && adv >= grs - 1) {
return 'must advance less than the smallest match size';
}
if (adv <= 0) {
return 'must eliminate players each match';
}
return null;
};
var finalInvalid = function (leftOver, limit, gLast) {
if (leftOver < 2) {
return 'must contain at least 2 players'; // force >4 when using limits
}
var lastNg = Math.ceil(leftOver / gLast);
if (limit > 0) { // using limits
if (limit >= leftOver) {
return 'limit must be less than the remaining number of players';
}
// need limit to be a multiple of numGroups (otherwise tiebreaks necessary)
if (limit % lastNg !== 0) {
return 'number of matches must divide limit';
}
}
return null;
};
var invalid = function (np, grs, adv, limit) {
if (np < 2) {
return 'number of players must be at least 2';
}
if (!grs.length || !grs.every(Tournament.isInteger)) {
return 'sizes must be a non-empty array of integers';
}
if (!adv.every(Tournament.isInteger) || grs.length !== adv.length + 1) {
return 'advancers must be a sizes.length-1 length array of integers';
}
var numGroups = 0;
for (var i = 0; i < adv.length; i += 1) {
// loop over adv as then both a and g exist
var a = adv[i];
var g = grs[i];
// calculate how big the groups are
numGroups = Math.ceil(np / g);
var gActual = group.minimalGroupSize(np, g);
// and ensure with group reduction that eliminationValid for reduced params
var invReason = roundInvalid(np, gActual, a, numGroups);
if (invReason !== null) {
return 'round ' + (i+1) + ' ' + invReason;
}
// return how many players left so that np is updated for next itr
np = numGroups*a;
}
// last round and limit checks
var invFinReason = finalInvalid(np, limit, grs[grs.length-1]);
if (invFinReason !== null) {
return 'final round ' + invFinReason;
}
// nothing found - ok to create
return null;
};
//------------------------------------------------------------------
// Interface
//------------------------------------------------------------------
var FFA = Tournament.sub('FFA', function (opts, initParent) {
this.limit = opts.limit;
this.advs = opts.advancers;
this.sizes = opts.sizes;
initParent(makeMatches(this.numPlayers, this.sizes, this.advs));
});
//------------------------------------------------------------------
// Helpers and constants
//------------------------------------------------------------------
FFA.configure({
defaults: function (np, opts) {
opts.limit = opts.limit | 0;
opts.sizes = Array.isArray(opts.sizes) ? opts.sizes : [np];
opts.advancers = Array.isArray(opts.advancers) ? opts.advancers : [];
return opts;
},
invalid: function (np, opts) {
return invalid(np, opts.sizes, opts.advancers, opts.limit);
}
});
FFA.prototype.limbo = function (playerId) {
// if player reached currentRound, he may be waiting for generation of nextRound
var m = $.firstBy(function (g) {
return g.p.indexOf(playerId) >= 0 && g.m;
}, this.currentRound() || []);
if (m) {
// will he advance to nextRound ?
var adv = this.advs[m.id.r - 1];
if (Tournament.sorted(m).slice(0, adv).indexOf(playerId) >= 0) {
return {s: 1, r: m.id.r + 1}; // TODO: no toString representation for this
}
}
};
// ------------------------------------------------------------------
// Expected methods
// ------------------------------------------------------------------
FFA.prototype._progress = function (match) {
var adv = this.advs[match.id.r - 1] || 0;
var currRnd = this.findMatches({r: match.id.r});
if (currRnd.every($.get('m')) && adv > 0) {
prepRound(currRnd, this.findMatches({r: match.id.r + 1}), adv);
}
};
FFA.prototype._safe = function (match) {
var nextRnd = this.findMatches({ r: match.id.r + 1 });
// safe iff next round has not started
return nextRnd.every(function (m) {
return !Array.isArray(m.m);
});
};
FFA.prototype._verify = function (match, score) {
var adv = this.advs[match.id.r - 1] || 0;
var sortedScore = score.slice().sort($.compare()).reverse();
if (adv > 0 && sortedScore[adv] === sortedScore[adv - 1]) {
return 'scores must unambiguous decide who advances';
}
if (!adv && this.limit > 0) {
// number of groups in last round is the match number of the very last match
// because of the ordering this always works!
var lastNG = this.matches[this.matches.length-1].id.m;
var cutoff = this.limit/lastNG; // NB: lastNG divides limit (from finalInvalid)
if (sortedScore[cutoff] === sortedScore[cutoff - 1]) {
return 'scores must decide who advances in final round with limits';
}
}
return null;
};
FFA.prototype._stats = function (res, m) {
if (m.m) {
var adv = this.advs[m.id.r - 1] || 0;
$.zip(m.p, m.m).sort(Tournament.compareZip).forEach(function (t, j, top) {
var p = Tournament.resultEntry(res, t[0]);
p.for += t[1];
p.against += (top[0][1] - t[1]); // difference with winner
if (j < adv) {
p.wins += 1;
}
});
}
return res;
};
var compareMulti = function (x, y) {
return (x.pos - y.pos) ||
((y.for - y.against) - (x.for - x.against)) ||
(x.seed - y.seed);
};
FFA.prototype._sort = function (res) {
var limit = this.limit;
var advs = this.advs;
var sizes = this.sizes;
var maxround = this.sizes.length;
// gradually improve scores for each player by looking at later and later rounds
this.rounds().forEach(function (rnd, k) {
var rndPs = $.flatten($.pluck('p', rnd)).filter($.gt(Tournament.NONE));
rndPs.forEach(function (p) {
Tournament.resultEntry(res, p).pos = rndPs.length; // tie players that got here
});
var isFinal = (k === maxround - 1);
var adv = advs[k] || 0;
var wlim = (limit > 0 && isFinal) ? limit / rnd.length : adv;
var nonAdvancers = $.replicate(sizes[k] - adv, []); // all in final
// collect non-advancers - and set wins
rnd.filter($.get('m')).forEach(function (m) {
var startIdx = isFinal ? 0 : adv;
var top = $.zip(m.p, m.m).sort(Tournament.compareZip).slice(startIdx);
Tournament.matchTieCompute(top, startIdx, function (p, pos) {
var resEl = Tournament.resultEntry(res, p);
if (pos <= wlim || (pos === 1 && !adv)) {
resEl.wins += 1;
}
if (isFinal) {
resEl.gpos = pos; // for rawPositions
}
nonAdvancers[pos-adv-1].push(resEl);
});
});
// nonAdvancers will be tied between the round based on their mpos
var posctr = adv*rnd.length + 1;
nonAdvancers.forEach(function (xplacers) {
xplacers.forEach(function (r) {
r.pos = posctr;
});
posctr += xplacers.length;
});
});
return res.sort(compareMulti);
};
// helper method to be compatible with TieBreaker
FFA.prototype.rawPositions = function (res) {
if (!this.isDone()) {
throw new Error('cannot tiebreak a FFA tournament until it is finished');
}
var maxround = this.sizes.length;
var finalRound = this.findMatches({ r: maxround });
var posAry = finalRound.map(function (m) {
var seedAry = $.replicate(m.p.length, []);
m.p.forEach(function (p) {
var resEl = Tournament.resultEntry(res, p);
$.insert(seedAry[(resEl.gpos || resEl.pos)-1], p);
});
return seedAry;
});
return posAry;
};
// ------------------------------------------------------------------
FFA.Id = Id;
module.exports = FFA;