git.sesse.net Git - wloh/blob - mcwordfeud.cpp

   1 #include <stdio.h>
   2 #include <math.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5
   6 #include <map>
   7 #include <vector>
   8 #include <string>
   9 #include <algorithm>
  10
  11 #include "ziggurat.hpp"
  12
  13 using namespace std;
  14
  15 #define MAX_PLAYERS 16
  16
  17 struct player {
  18         int player_index;
  19         int points, margin;
  20 };
  21 struct highest_ranking {
  22 public:
  23         bool operator() (const player &a, const player &b) const {
  24                 if (a.points != b.points) {
  25                         return a.points > b.points;
  26                 }
  27                 return a.margin > b.margin;
  28         }
  29 };
  30
  31 #if 0
  32 float draw_unit()
  33 {
  34         return rand() * (1.0f / RAND_MAX);
  35 }
  36
  37 // FIXME: replace rejection method with a better method! this one can only ever go to [-5z, +5z]
  38 // and is very slow.
  39 float draw_gaussian(float stddev)
  40 {
  41         for ( ;; ) {
  42                 float z = draw_unit() * 10.0f - 5.0f;
  43                 float y = draw_unit();
  44                 if (y < exp(-z*z)) {
  45                         return z * stddev;
  46                 }
  47         }
  48 }
  49 #else
  50 float draw_gaussian(float mu, float stddev)
  51 {
  52         static bool inited = false;
  53         static long unsigned seed = 123456789;
  54         int kn[128];
  55         float fn[128], wn[128];
  56         if (!inited) {
  57                 r4_nor_setup(kn, fn, wn);
  58                 inited = true;
  59         }
  60
  61         return r4_nor(&seed, kn, fn, wn) * stddev + mu;
  62 }
  63 #endif
  64
  65 int main(int argc, char **argv)
  66 {
  67         int trials = atoi(argv[1]);
  68
  69         int num_players;
  70         if (scanf("%d", &num_players) != 1) {
  71                 fprintf(stderr, "Could't read number of players\n");
  72                 exit(1);
  73         }
  74
  75         if (num_players > MAX_PLAYERS) {
  76                 fprintf(stderr, "Max %d players supported\n");
  77                 exit(1);
  78         }
  79
  80         vector<string> players;
  81         map<string, int> player_map;
  82         float ratings[MAX_PLAYERS];
  83         bool has_scores[MAX_PLAYERS][MAX_PLAYERS];
  84         for (int pl1 = 0; pl1 < num_players; ++pl1) {
  85                 for (int pl2 = 0; pl2 < num_players; ++pl2) {
  86                         has_scores[pl1][pl2] = false;
  87                 }
  88         }
  89
  90         int scores[MAX_PLAYERS][MAX_PLAYERS];
  91         for (int i = 0; i < num_players; ++i) {
  92                 char buf[256];
  93                 float rating;
  94                 int ret = scanf("%s %f", buf, &rating);
  95                 if (ret < 1) {
  96                         fprintf(stderr, "Couldn't read player %d\n", i);
  97                         exit(1);
  98                 }
  99                 if (ret != 2) {
 100                         rating = 1500.0f;
 101                 }
 102
 103                 players.push_back(buf);
 104                 player_map[buf] = i;
 105                 ratings[i] = rating;
 106         }
 107
 108         for ( ;; ) {
 109                 char pl1[256], pl2[256];
 110                 int score1, score2;
 111
 112                 if (scanf("%s %s %d %d", pl1, pl2, &score1, &score2) != 4) {
 113                         break;
 114                 }
 115
 116                 if (player_map.count(pl1) == 0) {
 117                         fprintf(stderr, "Unknown player '%s'\n", pl1);
 118                         exit(1);
 119                 }
 120                 if (player_map.count(pl2) == 0) {
 121                         fprintf(stderr, "Unknown player '%s'\n", pl2);
 122                         exit(1);
 123                 }
 124
 125                 scores[player_map[pl1]][player_map[pl2]] = score1;
 126                 scores[player_map[pl2]][player_map[pl1]] = score2;
 127                 has_scores[player_map[pl1]][player_map[pl2]] = true;
 128                 has_scores[player_map[pl2]][player_map[pl1]] = true;
 129         }
 130
 131         int placements[MAX_PLAYERS][MAX_PLAYERS];
 132         for (int i = 0; i < num_players; ++i) {
 133                 for (int j = 0; j < num_players; ++j) {
 134                         placements[i][j] = 0;
 135                 }
 136         }
 137
 138         for (int i = 0; i < trials; ++i) {
 139                 // draw the missing matches
 140                 for (int pl1 = 0; pl1 < num_players; ++pl1) {
 141                         for (int pl2 = pl1 + 1; pl2 < num_players; ++pl2) {
 142                                 if (has_scores[pl1][pl2]) {
 143                                         continue;
 144                                 }
 145
 146                                 float mu = ratings[pl1] - ratings[pl2];
 147
 148                                 int score = lrintf(draw_gaussian(mu, 82.9f));
 149                                 scores[pl1][pl2] = score;
 150                                 scores[pl2][pl1] = -score;
 151                         }
 152                 }
 153
 154                 // sum up the points and margin for each player
 155                 player stats[MAX_PLAYERS];
 156                 for (int pl1 = 0; pl1 < num_players; ++pl1) {
 157                         stats[pl1].player_index = pl1;
 158                         stats[pl1].points = 0;
 159                         stats[pl1].margin = 0;
 160                         for (int pl2 = 0; pl2 < num_players; ++pl2) {
 161                                 if (pl1 == pl2) {
 162                                         continue;
 163                                 }
 164                                 stats[pl1].margin += scores[pl1][pl2];
 165                                 stats[pl1].margin -= scores[pl2][pl1];
 166                                 if (scores[pl1][pl2] > scores[pl2][pl1]) {
 167                                         stats[pl1].points += 2;
 168                                 } else if (scores[pl1][pl2] == scores[pl2][pl1]) {
 169                                         stats[pl1].points++;
 170                                 }
 171                         }
 172                 }
 173
 174                 // order by points and then margin
 175                 sort(stats, stats + num_players, highest_ranking());
 176                 for (int j = 0; j < num_players; ++j) {
 177                         ++placements[stats[j].player_index][j];
 178                 }
 179         }
 180
 181         for (int i = 0; i < num_players; ++i) {
 182                 printf("%-15s", players[i].c_str());
 183                 for (int j = 0; j < num_players; ++j) {
 184                         printf(" %5d", placements[i][j]);
 185                 }
 186                 printf("\n");
 187         }
 188 }