config int minPlayers = 6;
config real defaultWeighting = 50;

int levelRecMin;
int levelRecMax;

Game game;

real meanBotWeight;

// By 'pawn', I mean real player or bot.  This array is
// indexed by the game's own bot/player number, which I'm
// calling a 'pawn' number.  If there is no such number,
// this needs a rethink.
real pawnWeight[32];

// This is a list of real players who have been assigned a team
// based on our decisions.  New players are added at the end.  A
// player is removed by replacing it with the player at the end.
// It is essential that there are no gaps in the array, so this is
// indexed by the mutator's own internal numbering, which excludes
// bots.
int playerNumber[32];
int placedPlayers = 0;

// Place a player (specified by pawn number) into our array.  If
// it's already there, return false.  Update the player's weight
// in either case.
function bool placePlayer(int num, real weight) {
  pawnWeight[num] = weight;
  for (int index = 0; index < placedPlayers; index++) {
    if (playerNumber[index] != num) continue;
    return false;
  }
  playerNumber[placedPlayers] = num;
  placedPlayers++;
  return true;
}

function void removePlayer(int num) {
  for (int index = 0; index < placedPlayers; index++) {
    if (playerNumber[index] != num) continue;
    placedPlayers--;
    playerNumber[index] = playerNumber[placedPlayers];
  }
}

event newGame(Game game) {
  this.game = game;

  // No players are placed yet.
  placedPlayers = 0;

  // Get ideal player range for this level.
  parseRange(game.level.recommendedPlayers,
             levelRecMin, levelRecMax);

  send game type to server;
  send list of mutators to server;
  request mean bot weight from server;
}

event newManualPlayer(int num) {
  PlayerId id = game.players[num];
  request weight of player id from server;
}

event newAutomaticPlayer(int num) {
  string name = game.players[num].name;
  request weight of bot called 'name' from server;
}

event manualPlayerRemoved(int num) {
  removePlayer(num);
  updateBots();
  updateBalancer();
}

event automaticPlayerRemoved() {
  updateBots(); // Should be a no-op, so it won't loop.
  updateBalancer();
}

function void updateBots() {
  if (game.type.isTeamGame()) {
    int teamSize[] = { 0, 0 };
    for (int i = 0; i < placedPlayers; i++)
      teamSize[player[playerNumber[i]].team]++;
    largestTeamSize = max(teamSize[0..3]);
    teamCount = 2;
  } else {
    // Every player is on his own team.
    largestTeamSize = 1;
    teamCount = game.playerCount;
  }
  int clamped = clamp(minPlayers, leveRecMin, levelRecMax);
  clamped = roundUp(clamped, teamCount);
  game.setMinPlayers(max(clamped, largestTeamSize * teamCount));
}

// This deals with late changes and the unpredictability of bot
// weights, by working out the relative weights of all team
// players, including bots, and delegating the action to take,
// e.g. varying firing rates, altering initial health.
function void updateBalancer() {
  real teamWeight[4] = { 0, ... };
  for (Pawn p : game.pawns)
    teamWeight[p.teamNumber] += pawnWeight[p.num];

  // This is a black box, and needs further thought.
  game.applyBalance(teamWeight);
}

event newMeanBotWeight(real weight) {
  meanBotWeight = weight;
  updateBalancer();
}

event newManualWeight(PlayerId id, real weight) {
  if (weight < 0)
    weight = defaultWeighting;
  int num = findPlayer(id);
  if (num < 0) return;

  if (placePlayer(num, weight)) {
    if (game.hasStarted()) {
      choose a side for #num;
      move #num to that side;
      updateBots();
    }
  } else if (game.hasStarted()) {
    updateBalancer();
  }
}

event newAutomaticWeight(string name, real weight) {
  if (weight < 0)
    weight = meanBotWeight;
  int num = findBot(name);
  pawnWeight[num] = weight;

  if (game.hasStarted())
    updateBalancer();
}

function int roundUp(int input, int period) {
  return (input + period - 1) / period * period;
}

real bestRat[5];
uint32_t bestComb[5];

function void resetCombinations() {
  for (int i = 0; i < 5; i++) {
    bestRat[i] = 0;
    bestComb[i] = 0;
  }
}

function void recordCombination(uint32_t comb, real ratio) {
  // Keep track of the best 5 ratios and the
  // combinations that generated them.
  for (int i = 0; i < 5; i++) {
    if (ratio < bestRat[i]) continue;
    for (int j = i + 1; j < 5; j++) {
      bestRat[j] = bestRat[j - 1];
      bestComb[j] = bestComb[j - 1];
    }
    bestRat[i] = ratio;
    bestComb[i] = comb;
    break;
  }
}

event gameStarts() {
  if (!game.type.isTeamGame()) {
    updateBots();
    break;
  }

  // Create a cache of player weights.
  real weight[placedPlayers] = { 0... };
  for (int p = 0; p < placedPlayers; p++)
    weight[p] = pawnWeight[playerNumber[p]];

  // The bit-shifting and masking only works with 2 teams.
  const int teamCount = 2;

  // Go through all combinations of placed players, looking
  // for the best 5 combinations.

  if (placedPlayers > 20) {
    // An alternative algorithm might be better when
    // the number of players is high.
  } else {
    const int limit = teamCount ** (placedPlayers - 1);
    for (uint32_t comb = 0; comb < limit; comb++) {
      // The weight of each team
      real sum[teamCount] = { 0, 0 };

      // The number of manual players in each time
      int count[teamCount] = { 0, 0 };
  
      // Work out the weight of manual players in each team.
      for (int p = 0; p < placedPlayers; p++) {
        int team = (comb >> p) & 1;
        sum[team] += weight[p];
        count[team]++;
      }
  
      // Add in the weight of any extra bots, assuming the
      // mean bot weight.
      int maxTeam = max(count);
      int clamped = clamp(minPlayers, leveRecMin, levelRecMax);
      clamped = roundUp(clamped, teamCount);
      int size =
        max(clamped, largestTeamSize * teamCount) / teamCount;
      for (int i = 0; i < teamCount; i++)
        sum[i] += meanBotWeight * (size - count[i]);
  
      // Work out how balanced this combination is.
      real ratio = min(sum) / max(sum);

      recordCombination(comb, ratio);  
    }
  }

  // Pick one of the best combinations, and
  // move players into the correct teams.
  int i = random(0, 4); // inclusive
  uint32_t comb = bestComb[i];
  for (int p = 0; p < placedPlayers; p++)
    game.pawn[playerNumber[p]] = (comb >> p) & 1;

  updateBots();
  updateBalancer();
}

#include <stdio.h>
#include <inttypes.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <stdbool.h>
#include <math.h>
#include <ctype.h>
#include <string.h>

typedef uint_least32_t comb_t;
#define COMB_C(V) UINT32_C(V)

struct cand {
  double ratio;
  comb_t comb;
};

static void reset_cands(struct cand *cands, size_t lim)
{
  for (size_t i = 0; i < lim; i++)
    cands[i].ratio = 0.0;
}

static void merge_cand(struct cand *cands, size_t lim,
                       comb_t comb, double ratio)
{
  for (size_t i = 0; i < lim; i++) {
    if (ratio < cands[i].ratio) continue;
    for (size_t j = lim - 1; j > i; j--)
      cands[j] = cands[j - 1];
    cands[i].ratio = ratio;
    cands[i].comb = comb;
    return;
  }
}

static const struct cand *select_cand(struct cand *cands, size_t lim)
{
  double power = 1.0;
  double sum = 0.0;
  for (size_t i = 0; i < lim; i++)
    sum += pow(cands[i].ratio, power);
  for (size_t i = 0; i < lim; i++) {
    double val = pow(cands[i].ratio, power);
#if 0
    printf("Option %zu: %g = %g%% %08" PRIxLEAST32 "\n",
           i + 1, val, 100.0 * val / sum, cands[i].comb);
#endif
  }
  double chosen = rand() / (double) RAND_MAX * sum;
#if 0
  printf("Chosen %g/%g\n", chosen, sum);
#endif
  for (size_t i = 0; i < lim; i++) {
    chosen -= pow(cands[i].ratio, power);
    if (chosen < 0.0)
      return &cands[i];
  }
  assert(false);
}

static size_t max(const size_t *ptr, size_t len)
{
  size_t val = ptr[0];
  for (size_t i = 1; i < len; i++)
    if (ptr[i] > val) val = ptr[i];
  return val;
}

static size_t max2(size_t a, size_t b)
{
  return a > b ? a : b;
}

static size_t min2(size_t a, size_t b)
{
  return a < b ? a : b;
}

static size_t min(const size_t *ptr, size_t len)
{
  size_t val = ptr[0];
  for (size_t i = 1; i < len; i++)
    if (ptr[i] < val) val = ptr[i];
  return val;
}

static double maxd(const double *ptr, size_t len)
{
  double val = ptr[0];
  for (size_t i = 1; i < len; i++)
    if (ptr[i] > val) val = ptr[i];
  return val;
}

static double mind(const double *ptr, size_t len)
{
  double val = ptr[0];
  for (size_t i = 1; i < len; i++)
    if (ptr[i] < val) val = ptr[i];
  return val;
}

static size_t clamp(size_t input, size_t min, size_t max)
{
  if (input < min) return min;
  if (input > max) return max;
  return input;
}

static size_t roundUp(size_t input, size_t factor)
{
  return (input + factor - 1) / factor * factor;
}

struct player {
  char name[32];
  double weight;
};

static int dblcmp(const void *av, const void *bv)
{
  const struct player *a = av;
  const struct player *b = bv;
  if (a->weight > b->weight) return +1;
  if (a->weight < b->weight) return -1;
  return 0;
}

int main(int argc, const char *const *argv)
{
  const size_t teams = 2;
  double meanBotWeight = 20.0;
  size_t targetPlayers = 8;
  size_t minRecPlayers = 6;
  size_t maxRecPlayers = 12;

  for (int argi = 1; argi < argc; argi++) {
    if (!strcmp(argv[argi], "-min")) {
      minRecPlayers = atoi(argv[++argi]);
    } else if (!strcmp(argv[argi], "-max")) {
      maxRecPlayers = atoi(argv[++argi]);
    } else if (!strcmp(argv[argi], "-target")) {
      targetPlayers = atoi(argv[++argi]);
    } else if (!strcmp(argv[argi], "-bot")) {
      meanBotWeight = atof(argv[++argi]);
    } else {
      fprintf(stderr, "%s: Unknown argument: %s\n", argv[0], argv[argi]);
      exit(EXIT_FAILURE);
    }
  }

  /* Load in player weightings from standard input. */
  struct player weightings[32];
  size_t players = 0;
  char line[100];
  while (players < sizeof weightings / sizeof weightings[0] &&
         fgets(line, sizeof line, stdin)) {
    line[strlen(line) - 1] = '\0';
    char *end;
    weightings[players].weight = strtod(line, &end);
    while (*end && isspace(*end))
      end++;
    strncpy(weightings[players].name, end, sizeof weightings[players].name);
    weightings[players].name[sizeof weightings[players].name] = '\0';
    players++;
  }

  srand(time(NULL));

  /* Try all combinations and record the best few. */
  struct cand cands[20];
  reset_cands(cands, sizeof cands / sizeof cands[0]);
  comb_t lim, preset;

  const size_t player_threshold = 16;

  if (players > player_threshold) {
    /* Fix the positions of the top N players.  First, sort the
       players by increasing weight. */
    qsort(weightings, players, sizeof weightings[0], dblcmp);
    preset = 0x99999999u >> (32 - players);
    preset &= -1 << player_threshold;
    lim = COMB_C(1) << player_threshold;
  } else {
    /* Just go through every possible combination. */
    lim = COMB_C(1) << (players - 1);
    preset = 0;
  }

  printf("Range %08" PRIxLEAST32 "-%08" PRIxLEAST32
         " preset %08" PRIxLEAST32 "\n", (comb_t) 0, lim - 1u, preset);

  for (comb_t index = 0; index < lim; index++) {
    comb_t comb = index | preset;

    /* Prepare to weigh up the teams for this combination. */
    double score[teams];
    size_t count[teams];
    for (size_t i = 0; i < teams; i++) {
      score[i] = 0.0;
      count[i] = 0;
    }

    /* Add the weights of each player on each team. */
    bool exceeded = false;
    size_t excess = min2(32 / teams, 18 * players / 32);
    for (size_t p = 0; p < players; p++) {
      size_t team = (comb >> p) & 1u;
      score[team] += weightings[p].weight;
      count[team]++;
      if (count[team] > excess) {
        exceeded = true;
        break;
      }
    }
    if (exceeded) continue;

    /* Add the weights of bots on each team. */
    const size_t largestTeamSize = max(count, teams);
    const size_t minPlayers =
      max2(roundUp(clamp(targetPlayers,
                         minRecPlayers,
                         maxRecPlayers), teams),
           largestTeamSize * teams);
    assert(minPlayers % teams == 0);
    const size_t playersPerTeam = minPlayers / teams;
    for (size_t t = 0; t < teams; t++)
      score[t] += meanBotWeight * (playersPerTeam - count[t]);

    /* Work out the quality of this combination, and record it. */
    double ratio = mind(score, teams) / maxd(score, teams);
    merge_cand(cands, sizeof cands / sizeof cands[0], comb, ratio);

#if 0
    for (size_t t = 0; t < teams; t++)
      printf("%zu ", count[t]);
    printf("= %g\n", ratio);
#endif
  }

  /* Choose from the best combinations, and apply it. */
  const struct cand *chosen =
    select_cand(cands, sizeof cands / sizeof cands[0]);
  size_t team_list[teams][players];
  size_t team_count[teams];
  size_t playersPerTeam;
  {
    for (size_t t = 0; t < teams; t++)
      team_count[t] = 0;
    for (size_t p = 0; p < players; p++) {
      size_t team = (chosen->comb >> p) & 1u;
      team_list[team][team_count[team]] = p;
      team_count[team]++;
    }

    const size_t largestTeamSize = max(team_count, teams);
    const size_t minPlayers =
      max2(roundUp(clamp(targetPlayers,
                         minRecPlayers,
                         maxRecPlayers), teams),
           largestTeamSize * teams);
    assert(minPlayers % teams == 0);
    playersPerTeam = minPlayers / teams;
  }

  printf("%zu players across %zu teams:\n", players, teams);
  printf("\tMap for %zu-%zu players (target %zu)\n",
         minRecPlayers, maxRecPlayers, targetPlayers);

  for (size_t t = 0; t < teams; t++) {
    size_t bot_count = playersPerTeam - team_count[t];
    printf("\nTeam %zu: (%zu players + %zu bots)\n",
           t + 1, team_count[t], bot_count);
    double sum = 0.0;
    for (size_t i = 0; i < team_count[t]; i++) {
      struct player *player = &weightings[team_list[t][i]];
      double weight = player->weight;
      sum += weight;
      printf("\t%3g %s\n", weight, player->name);
    }
    double bot_weight = bot_count * meanBotWeight;
    printf("\t+ %zu * %g = %g\n", bot_count,
           meanBotWeight, bot_weight);
    sum += bot_weight;
    printf("\t=%g\n", sum);
  }


  return EXIT_SUCCESS;
}

5 Boring John
3 Silly Billy
2 Slartibartfast
7 Chewbacca
23 Ignoramus
92 Riddick
93 Luke Skywalker
95 Darth Vader
27 Peter Griffin
56 Roger
28 Annoying Git
99 Cheat
1 Lame
23 Twonk
83 Foogilicious
41 Flunk Basket
49 Jack O'Neill