path: root/scheduling/scheduling.cc

#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::vector<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));
      }
    }
  }
  std::shuffle(possible_matches.begin(), possible_matches.end(),
               generator);

  vector<std::tuple<string, string>> result;
  for (const auto&m : possible_matches) {
    Player* p1 = &players[std::get<0>(m)];
    Player* p2 = &players[std::get<1>(m)];
    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";
  }
}