New scheduling algorithm in C++.

1 files changed, 265 insertions, 0 deletions

diff --git a/scheduling/scheduling.cc b/scheduling/scheduling.cc
new file mode 100644
index 0000000..bd1f6bb
--- /dev/null
+++ b/scheduling/scheduling.cc
@@ -0,0 +1,265 @@
+#include <algorithm>
+#include <cmath>
+#include <cstdlib>
+#include <iostream>
+#include <limits>
+#include <list>
+#include <map>
+#include <memory>
+#include <random>
+#include <sstream>
+#include <string>
+#include <vector>
+#include <fstream>
+
+using std::string;
+using std::vector;
+using std::map;
+
+int kIterations = 1000000;
+
+vector<string> Split(const string& message, char deliminator) {
+  std::istringstream stream(message);
+  vector<string> result;
+  string tmp;
+  while (std::getline(stream, tmp, deliminator)) {
+    result.emplace_back(tmp);
+  }
+  return result;
+}
+
+struct Player {
+  Player(const string id, const int rank, const int desired_games)
+      : id_(id), rank_(rank), desired_games_(desired_games) {}
+  Player() = default;
+  Player(const Player& other) = default;
+  Player& operator=(const Player& other) = default;
+
+  string id_;
+  int rank_;
+  int desired_games_;
+
+  string DebugString() const {
+    std::ostringstream output;
+    output << "Player(id=" << id_ << ", rank=" << rank_
+           << ", desired_games=" << desired_games_ << ")";
+    return output.str();
+  }
+
+  string ToString() const {
+    std::ostringstream output;
+    output << id_ << " (" << std::abs(rank_) << (rank_ > 0 ? 'd' : 'k')
+           << ")";
+    return output.str();
+  }
+};
+
+std::unique_ptr<Player> ParsePlayer(const vector<string>& data, int round) {
+  const int kPlayerTokens = 7;
+  if (data.size() < kPlayerTokens) {
+    return nullptr;
+  }
+  string id = data[0];
+  std::istringstream rank_stream(data[2]);
+  int rank;
+  rank_stream >> rank;
+  char sign;
+  rank_stream >> sign;
+  if (sign != 'k' && sign != 'd') {
+    return nullptr;
+  }
+  if (sign == 'k') {
+    rank = -rank;
+  }
+  std::istringstream desired_games_stream(data[3 + round]);
+  int desired_games;
+  desired_games_stream >> desired_games;
+  return std::unique_ptr<Player>(new Player(id, rank, desired_games));
+}
+
+int RankDifference(const Player& p1, const Player& p2) {
+  int r1 = p1.rank_; if (r1 < 0) { r1++; }
+  int r2 = p2.rank_; if (r2 < 0) { r2++; }
+  return std::abs(r1 - r2);
+}
+
+bool LegalMatch(const Player& p1, const Player& p2) {
+  return RankDifference(p1, p2) < 10;
+}
+
+template <typename GeneratorT>
+vector<std::tuple<string, string>> GenerateMatches(
+    GeneratorT generator,
+    vector<Player> players) {
+  std::list<std::tuple<int, int>> possible_matches;
+  for (int i = 0; i < players.size(); i++) {
+    for (int j = 0; j < players.size(); j++) {
+      // X vs. y and y vs. x is the same match. Also excludes x vs. x.
+      Player* p1 = &players[i];
+      Player* p2 = &players[j];
+      if (i < j && LegalMatch(*p1, *p2)) {
+        possible_matches.emplace_back(std::tuple<int, int>(i, j));
+      }
+    }
+  }
+
+  vector<std::tuple<string, string>> result;
+  while (!possible_matches.empty()) {
+    std::uniform_int_distribution<int> distribution(
+        0, possible_matches.size() - 1);
+    int i = distribution(generator);
+    auto it = possible_matches.begin();
+    std::advance(it, i);
+    Player* p1 = &players[std::get<0>(*it)];
+    Player* p2 = &players[std::get<1>(*it)];
+    possible_matches.erase(it);
+
+    if (p1->desired_games_ && p2->desired_games_) {
+      result.push_back(std::tuple<string, string>(p1->id_, p2->id_));
+      p1->desired_games_--;
+      p2->desired_games_--;
+    }
+  }
+  return result;
+}
+
+double Score(const map<string, Player>& players,
+             const vector<std::tuple<string, string>> matches) {
+  double score = 0.0;
+  for (const auto& match : matches) {
+    const Player& p1 = players.at(std::get<0>(match));
+    const Player& p2 = players.at(std::get<1>(match));
+    double rankScore = 500 - 10 * pow(RankDifference(p1, p2), 1.5);
+    score += rankScore;
+  }
+  return score;
+}
+
+struct Match {
+  Player white_;
+  Player black_;
+  double komi_;
+  int handicap_;
+
+  string ToString() const {
+    std::ostringstream stream;
+    stream << white_.ToString() << " vs. " << black_.ToString();
+    stream << " (komi: " << komi_;
+    if (handicap_) {
+      stream << "; H" << handicap_;
+    }
+    stream << ")";
+    return stream.str();
+  }
+
+  string TabSeparated() const {
+    std::ostringstream stream;
+    stream << white_.id_ << "\t";
+    stream << black_.id_ << "\t";
+    if (handicap_) {
+      stream << "H" << handicap_ << "\t";
+    } else {
+      stream << "None\t";
+    }
+    stream << komi_;
+    return stream.str();
+  }
+};
+
+template <typename GeneratorT>
+Match CreateMatch(GeneratorT generator, const Player& p1, const Player& p2) {
+  Player white;
+  Player black;
+  double komi = 0.0;
+  int handicap = 0;
+
+  if (p1.rank_ == p2.rank_) {
+    std::bernoulli_distribution distribution(0.5);
+    komi = 7.5;
+    if (distribution(generator)) {
+      white = p1;
+      black = p2;
+    } else {
+      white = p2;
+      black = p1;
+    }
+  } else {
+    komi = 0.5;
+    if (p1.rank_ > p2.rank_) {
+      white = p1;
+      black = p2;
+    } else {
+      white = p2;
+      black = p1;
+    }
+    if (RankDifference(p1, p2) > 1) {
+      handicap = std::min(9, RankDifference(p1, p2));
+    }
+  }
+  return {white, black, komi, handicap};
+}
+
+int main() {
+  const int kRound = 1;
+  vector<Player> players;
+
+  string line;
+  while (std::getline(std::cin, line)) {
+    std::unique_ptr<Player> player = ParsePlayer(Split(line, '\t'), kRound);
+    printf("%s\n", player->DebugString().c_str());
+    if (player) {
+      players.emplace_back(*player);
+    } else {
+      printf("Failed to parse player: %s\n", line.c_str());
+    }
+  }
+
+  // Needed by Score().
+  map<string, Player> playerMap;
+  for (const Player& player : players) {
+    playerMap[player.id_] = player;
+  }
+
+  // Generate randomized pairings and pick the best one.
+  vector<std::tuple<string, string>> best_matches;
+  double best_score = std::numeric_limits<double>::lowest();
+  for (int i = 0; i < kIterations; i++) {
+    if (i && i % (kIterations / 10) == 0) {
+      printf("%.2f%% done\n", 100.0 * i / kIterations);
+    }
+    std::random_device rd;
+    std::mt19937 generator(rd());
+    auto matches = GenerateMatches(generator, players);
+    double score = Score(playerMap, matches);
+    if (score > best_score) {
+      best_score = score;
+      printf("Iteration(%d): New best score(%.3f)\n", i, score);
+      best_matches = matches;
+    }
+  }
+
+  // Designate colors, handicap, komi, and print a sorted list of matches.
+  vector<Match> finalized_matches;
+  for (auto pair : best_matches) {
+    std::random_device rd;
+    std::mt19937 generator(rd());
+    const Player& p1 = playerMap[std::get<0>(pair)];
+    const Player& p2 = playerMap[std::get<1>(pair)];
+    finalized_matches.emplace_back(CreateMatch(generator, p1, p2));
+  }
+  auto match_comparator = [](const Match& m, const Match& n) -> bool {
+    return (m.white_.rank_ + m.black_.rank_) >
+        (n.white_.rank_ + n.black_.rank_);
+  };
+  std::sort(finalized_matches.begin(), finalized_matches.end(),
+            match_comparator);
+
+  std::ostringstream export_filename;
+  export_filename << "matches_r" << kRound << ".tsv";
+  std::ofstream export_file;
+  export_file.open(export_filename.str());
+  for (const Match& match : finalized_matches) {
+    printf("%s\n", match.ToString().c_str());
+    export_file << match.TabSeparated() << "\n";
+  }
+}