simu

simu.c (12514B)

---

 /*
  * Input:
  *  <number of teams>
  *  Team1
  *  Team2
  *
  *  <number of played games>
  *  <index of home team> <index of away team> <home score> <away score> <OT/SO>
  *
  *  <number of remaining games>
  *  <index of home team> <index of away team>
  *
  * Output:
  *  Team1 <current games> <current points> <elo rating> <total games> <expected points> <probab finish 1st> <probab finish 2nd> ...
  *  Team2 <current games> <current points> <elo rating> <total games> <expected points> <probab finish 1st> <probab finish 2nd> ...
  */
 #define _POSIX_C_SOURCE 200811L
 #include <limits.h>
 #include <math.h>
 #include <pthread.h>
 #include <stdbool.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
 
 #if defined(USE_LEHMER)
 #define R_MAX UINT32_MAX
 struct rand_t {
 	__uint128_t state;
 };
 
 static void getseed(struct rand_t *r)
 {
 	struct timespec s;
 	clock_gettime(CLOCK_MONOTONIC, &s);
 	r->state = s.tv_nsec;
 	r->state <<= 64;
 	r->state |= s.tv_sec | 1;
 }
 
 static inline uint32_t getrand(struct rand_t *r)
 {
 	r->state *= 0xda942042e4dd58b5;
 	return r->state >> 64;
 }
 
 #elif defined(USE_URANDOM)
 #define R_MAX UINT32_MAX
 struct rand_t {
 	int fd;
 	uint32_t rbuf[4096];
 	uint32_t *r;
 };
 
 static void getseed(struct rand_t *r)
 {
 	r->fd = open("/dev/urandom", O_RDONLY);
 	r->r = 1[&r->rbuf];
 }
 
 static inline uint32_t getrand(struct rand_t *r)
 {
 	if (r->r == 1[&r->rbuf]) {
 		read(r->fd, r->rbuf, sizeof(r->rbuf));
 		r->r = r->rbuf;
 	}
 	return *r->r++;
 }
 #else
 struct rand_t {
 	unsigned int seed;
 };
 #define R_MAX RAND_MAX
 static void getseed(struct rand_t *r)
 {
 	struct timespec s;
 	clock_gettime(CLOCK_MONOTONIC, &s);
 	r->seed = s.tv_sec ^ s.tv_nsec;
 }
 
 static inline uint32_t getrand(struct rand_t *r)
 {
 	return rand_r(&r->seed);
 }
 #endif
 
 static inline void urand(uint32_t limit, bool rv[static 2], struct rand_t *r)
 {
 	uint32_t v = getrand(r);
 	rv[0] = (uint32_t)v < limit;
 	rv[1] = (uint32_t)R_MAX - v < limit;
 }
 
 struct team {
 	size_t id;
 	char name[128];
 	unsigned points;
 	unsigned games;
 	unsigned wins;
 	double elo;
 	double elo0;
 	long long unsigned pointsum;
 	long long unsigned gamessum;
 	size_t *poscounts;
 };
 
 struct game {
 	size_t t[2];
 	uint32_t expected;
 };
 
 struct standing {
 	size_t ti;
 	unsigned points;
 	unsigned wins;
 	unsigned games;
 	unsigned random;
 };
 
 int pointscmp(const void *a, const void *b)
 {
 	int r;
 	const struct standing *at = a;
 	const struct standing *bt = b;
 
 	if ((r = bt->points * at->games - at->points * bt->games))
 		return r;
 	if ((r = bt->wins - at->wins))
 		return r;
 	return bt->random - at->random;
 }
 
 int teampointscmp(const void *a, const void *b)
 {
 	int r;
 	const struct team *at = a;
 	const struct team *bt = b;
 
 	if ((r = bt->points * at->games - at->points * bt->games))
 		return r;
 	if ((r = bt->wins - at->wins))
 		return r;
 	return 0;
 }
 
 int teamcmp(const void *a, const void *b)
 {
 	const struct team *at = a;
 	const struct team *bt = b;
 
 	if (at->pointsum * bt->gamessum > bt->pointsum * at->gamessum)
 		return -1;
 	if (bt->pointsum * at->gamessum > at->pointsum * bt->gamessum)
 		return 1;
 	return 0;
 }
 
 void isort(void *data, size_t n, size_t sz, int (*cmp)(const void *a, const void *b))
 {
 	char (*d)[sz][1] = data;
 	char tmp[sz];
 	size_t i, j;
 
 	for (i = 1; i < n; i++) {
 		if (cmp(d[i], d[i - 1]) >= 0)
 			continue;
 
 		memcpy(tmp, d[i], sizeof(tmp));
 
 		for (j = i - 1; j > 0 && cmp(tmp, d[j - 1]) < 0; j--);
 
 		memmove(d[j + 1], d[j], *d[i] - *d[j]);
 		memcpy(d[j], tmp, sizeof(tmp));
 	}
 }
 
 void simulate(struct team *teams,
 	      size_t n_teams,
 	      const struct game *games,
 	      size_t n_games,
 	      uint32_t otprob,
 	      size_t iterations,
 	      struct rand_t *seedp)
 {
 	struct standing s0[n_teams];
 	struct standing standings[2][n_teams];
 	size_t i;
 
 	for (i = 0; i < n_teams; i++) {
 		s0[i].ti = i;
 		s0[i].points = teams[i].points;
 		s0[i].wins = teams[i].wins;
 		s0[i].games = teams[i].games;
 	}
 
 	for (i = 0; i < iterations / 2; i++) {
 		size_t j;
 		size_t k;
 
 		memcpy(standings[0], s0, sizeof(*standings));
 		memcpy(standings[1], s0, sizeof(*standings));
 
 		for (j = 0; j < n_games; j++) {
 			bool hw[2];
 			bool ot[2];
 
 			urand(games[j].expected, hw, seedp);
 			urand(otprob, ot, seedp);
 
 			for (k = 0; k < 2; k++) {
 				size_t wi = games[j].t[!hw[k]];
 				size_t li = games[j].t[hw[k]];
 
 				standings[k][wi].points += 3 - ot[k];
 				standings[k][li].points += ot[k];
 				standings[k][wi].wins += !ot[k];
 				standings[k][wi].games++;
 				standings[k][li].games++;
 			}
 		}
 
 		for (k = 0; k < 2; k++) {
 			for (j = 0; j < n_teams; j++)
 				standings[k][j].random = getrand(seedp) % (INT_MAX / 2);
 			isort(standings[k], n_teams, sizeof(*standings[k]), pointscmp);
 
 			for (j = 0; j < n_teams; j++) {
 				teams[standings[k][j].ti].pointsum += standings[k][j].points;
 				teams[standings[k][j].ti].gamessum += standings[k][j].games;
 				teams[standings[k][j].ti].poscounts[j]++;
 			}
 		}
 	}
 
 }
 
 void simulate_winall(struct team *teams,
 		     size_t n_teams,
 		     const struct game *games,
 		     size_t n_games,
 		     uint32_t otprob,
 		     size_t iterations,
 		     size_t team_id,
 		     bool win,
 		     struct rand_t *seedp)
 {
 	struct team teams_cpy[n_teams];
 	struct game games_cpy[n_games];
 
 	size_t r;
 	size_t w;
 
 	memcpy(teams_cpy, teams, sizeof(teams_cpy));
 
 	for (w = r = 0; r < n_games; r++) {
 		if (games[r].t[0] == team_id || games[r].t[1] == team_id) {
 			size_t opp = games[r].t[0] + games[r].t[1] - team_id;
 			teams_cpy[team_id].points += win * 3;
 			teams_cpy[team_id].games++;
 			teams_cpy[team_id].wins += win;
 
 			teams_cpy[opp].points += !win * 3;
 			teams_cpy[opp].games++;
 			teams_cpy[opp].wins += !win;
 		} else {
 			games_cpy[w++] = games[r];
 		}
 	}
 
 	simulate(teams_cpy, n_teams, games_cpy, w, otprob, iterations, seedp);
 }
 
 void simulate_winloseall(struct team *teams,
 			 size_t n_teams,
 			 size_t team,
 			 const struct game *games,
 			 size_t n_games,
 			 uint32_t otprob,
 			 size_t iterations,
 			 struct rand_t *seedp)
 {
 	struct team teams_cpy[n_teams];
 	size_t poscounts[n_teams][n_teams];
 	size_t e;
 	size_t i;
 
 	memcpy(teams_cpy, teams, sizeof(teams_cpy));
 	memset(poscounts, 0, sizeof(poscounts));
 
 	for (i = 0; i < n_teams; i++)
 		teams_cpy[i].poscounts = poscounts[i];
 
 	simulate_winall(teams_cpy, n_teams,
 			games, n_games,
 			otprob,
 			iterations,
 			team, true,
 			seedp);
 	simulate_winall(teams_cpy, n_teams,
 			games, n_games,
 			otprob,
 			iterations,
 			team, false,
 			seedp);
 
 	for (i = 0; i < n_teams; i++)
 		if (teams_cpy[team].poscounts[i])
 			break;
 	for (e = n_teams; e > 0; e--)
 		if (teams_cpy[team].poscounts[e - 1])
 			break;
 	for (; i < e; i++)
 		teams[team].poscounts[i] = 1;
 }
 
 struct thread_data {
 	struct team *teams;
 	bool *winloseall;
 	size_t n_teams;
 
 	struct game *games;
 	size_t n_games;
 
 	uint32_t otprob;
 
 	size_t iterations;
 	size_t iterated;
 	pthread_mutex_t mutex;
 };
 
 void *simulate_thread(void *data)
 {
 	struct thread_data *td = data;
 	struct team teams_cpy[td->n_teams];
 	size_t i;
 	size_t iters;
 	size_t poscounts[td->n_teams][td->n_teams];
 	size_t n = 0;
 	struct rand_t seedp;
 
 	getseed(&seedp);
 
 	pthread_mutex_lock(&td->mutex);
 	memcpy(teams_cpy, td->teams, sizeof(teams_cpy));
 	pthread_mutex_unlock(&td->mutex);
 
 	memset(poscounts, 0, sizeof(poscounts));
 
 	for (i = 0; i < td->n_teams; i++) {
 		teams_cpy[i].poscounts = poscounts[i];
 		pthread_mutex_lock(&td->mutex);
 		if (!td->winloseall[i]) {
 			td->winloseall[i] = true;
 			pthread_mutex_unlock(&td->mutex);
 
 			simulate_winloseall(teams_cpy, td->n_teams, i,
 					    td->games, td->n_games,
 					    td->otprob,
 					    td->iterations / td->n_teams / 2,
 					    &seedp);
 		} else {
 			pthread_mutex_unlock(&td->mutex);
 		}
 	}
 
 	for (;;) {
 		pthread_mutex_lock(&td->mutex);
 
 		if (td->iterations - td->iterated > 100000)
 			iters = 100000;
 		else
 			iters = td->iterations - td->iterated;
 
 		td->iterated += iters;
 		pthread_mutex_unlock(&td->mutex);
 
 		if (!iters)
 			break;
 		n += iters;
 
 		simulate(teams_cpy, td->n_teams,
 			 td->games, td->n_games,
 			 td->otprob,
 			 iters, &seedp);
 	}
 
 	pthread_mutex_lock(&td->mutex);
 	for (i = 0; i < td->n_teams; i++) {
 		size_t j;
 		td->teams[i].pointsum += teams_cpy[i].pointsum;
 		td->teams[i].gamessum += teams_cpy[i].gamessum;
 
 		for (j = 0; j < td->n_teams; j++)
 			td->teams[i].poscounts[j] += teams_cpy[i].poscounts[j];
 	}
 	pthread_mutex_unlock(&td->mutex);
 
 	return (void *)n;
 }
 
 const char *ltrim(const char *s)
 {
 	while (*s++ == ' ');
 	return s - 1;
 }
 
 int main(int argc, char **argv)
 {
 	int opt;
 	double homeadv = 58;
 	double elok = 32;
 	uint32_t otprob = 0.23 * R_MAX;
 	size_t n;
 	size_t m;
 	size_t i;
 	size_t j;
 	size_t iterations = 1000000;
 	size_t threads = 1;
 
 	while ((opt = getopt(argc, argv, "i:t:a:o:")) != -1) {
 		switch (opt) {
 		case 'i':
 			iterations = strtoull(optarg, NULL, 10);
 			break;
 
 		case 't':
 			threads = strtoull(optarg, NULL, 10);
 			break;
 
 		case 'a':
 			homeadv = strtod(optarg, NULL);
 			break;
 
 		case 'o':
 			otprob = strtod(optarg, NULL) * R_MAX;
 			break;
 
 		case 'k':
 			elok = strtod(optarg, NULL);
 			break;
 
 		default:
 			exit(1);
 			break;
 		}
 	}
 
 	iterations += iterations & 1;
 
 	if (scanf(" %zu", &n) < 1)
 		return 1;
 
 	struct team teams[n];
 	size_t teammap[n];
 	size_t poscounts[n][n];
 	memset(poscounts, 0, sizeof(poscounts));
 
 	for (i = 0; i < n; i++) {
 		if (scanf(" %127s", teams[i].name) < 1)
 			return 1;
 		teams[i].id = i;
 		teams[i].points = 0;
 		teams[i].games = 0;
 		teams[i].wins = 0;
 		teams[i].pointsum = 0;
 		teams[i].gamessum = 0;
 		teams[i].poscounts = poscounts[i];
 		teams[i].elo = 2000;
 	}
 
 	if (scanf(" %zu", &m) < 1)
 		return 1;
 
 	for (i = 0; i < m; i++) {
 		size_t hi, ai;
 		unsigned hs, as;
 		bool ot = false;
 		char det[16] = "";
 
 		switch (scanf(" %zu %zu %u %u%15[^\n]", &hi, &ai, &hs, &as, det)) {
 		case 5:
 			ot = !strcmp(ltrim(det), "OT") ||
 			     !strcmp(ltrim(det), "SO");
 			break;
 
 		case 4:
 			break;
 
 		default:
 			exit(1);
 		}
 
 		double expected = 1. / (1 + pow(10, (teams[ai].elo - teams[hi].elo - homeadv) / 400.0));
 		double actual;
 
 		teams[hi].games++;
 		teams[ai].games++;
 
 		if (hs > as) {
 			if (!ot) {
 				actual = 1;
 				teams[hi].wins++;
 				teams[hi].points += 3;
 			} else {
 				actual = 2./3;
 				teams[hi].points += 2;
 				teams[ai].points += 1;
 			}
 		} else {
 			if (ot) {
 				actual = 1./3;
 				teams[hi].points += 1;
 				teams[ai].points += 2;
 			} else {
 				teams[ai].points += 3;
 				teams[ai].wins++;
 				actual = 0;
 			}
 		}
 
 		teams[hi].elo += elok * (actual - expected);
 		teams[ai].elo -= elok * (actual - expected);
 	}
 
 	isort(teams, 1[&teams] - teams, sizeof(*teams), teampointscmp);
 
 	for (i = 0; i < n; i++) {
 		teammap[teams[i].id] = i;
 		teams[i].elo0 = teams[i].elo;
 	}
 
 	if (scanf(" %zu", &m) < 1)
 		return 1;
 
 	struct game games[m];
 
 	for (i = 0; i < m; i++) {
 		size_t h, a;
 		if (scanf(" %zu %zu", &h, &a) < 2)
 			return 1;
 		games[i].t[0] = teammap[h];
 		games[i].t[1] = teammap[a];
 		games[i].expected = R_MAX / (1 + pow(10.0, (teams[games[i].t[1]].elo - (teams[games[i].t[0]].elo + homeadv)) / 400.0));
 
 		teams[games[i].t[0]].elo += (2000 - teams[games[i].t[0]].elo) * elok / 200;
 		teams[games[i].t[1]].elo += (2000 - teams[games[i].t[1]].elo) * elok / 200;
 	}
 
 	if (threads > 1) {
 		pthread_t pthrds[threads];
 		bool winloseall[n];
 		memset(winloseall, 0, sizeof(winloseall));
 		struct thread_data td = {
 			teams, winloseall, n,
 			games, m,
 			otprob,
 			iterations, 0,
 			PTHREAD_MUTEX_INITIALIZER
 		};
 		for (i = 0; i < threads; i++)
 			pthread_create(&pthrds[i], NULL, simulate_thread, &td);
 		iterations = 0;
 		for (i = 0; i < threads; i++) {
 			void *a;
 			pthread_join(pthrds[i], &a);
 			iterations += (size_t)a;
 		}
 	} else {
 		struct rand_t seedp;
 		getseed(&seedp);
 
 		for (i = 0; i < n; i++) {
 			simulate_winloseall(teams, n, i,
 					    games, m,
 					    otprob,
 					    iterations / n / 2,
 					    &seedp);
 		}
 
 		simulate(teams, n,
 			 games, m,
 			 otprob,
 			 iterations,
 			 &seedp);
 	}
 
 	isort(teams, n, sizeof(*teams), teamcmp);
 	for (i = 0; i < n; i++) {
 		printf("%s %u %u %llu %.1f %d", teams[i].name,
 		       teams[i].games, teams[i].points,
 		       teams[i].gamessum / iterations,
 		       (double)teams[i].pointsum / iterations,
 		       (int)round(teams[i].elo0));
 		for (j = 0; j < n; j++) {
 			if (teams[i].poscounts[j] == iterations + 1)
 				printf(" +");
 			else if (teams[i].poscounts[j])
 				printf(" %e", (teams[i].poscounts[j] - 1) * 100.0 / iterations);
 			else
 				printf(" -");
 		}
 		printf("\n");
 	}
 
 	return 1;
 }