/*
* Copyright (C) 2006 Paul Pogonyshev.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
* 3. The name of the author may not be used to endorse or promote
* products derived from this software without specific prior
* written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
* OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
* GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
template
const type
abs (const type& x)
{
return type () < x ? x : -x;
}
template
const type
sqr (const type& x)
{
return x * x;
}
class Player
{
string name;
int rating;
public:
static const Player NO_ONE;
Player ()
: name (),
rating (0)
{ }
Player (string name, int rating)
: name (name),
rating (rating)
{ }
Player (const Player& other_player)
: name (other_player.name),
rating (other_player.rating)
{ }
Player&
operator= (const Player& other_player)
{
name = other_player.name;
rating = other_player.rating;
return *this;
}
string
get_name () const
{
return name;
}
int
get_rating () const
{
return rating;
}
struct compare_ratings
{
bool
operator() (const Player& player1, const Player& player2)
{
return player1.rating > player2.rating;
}
};
};
bool
operator== (const Player& player1, const Player& player2)
{
return player1.get_name () == player2.get_name ();
}
bool
operator!= (const Player& player1, const Player& player2)
{
return !(player1 == player2);
}
bool
operator< (const Player& player1, const Player& player2)
{
return player1.get_name () < player2.get_name ();
}
class Players
{
vector players;
mutable vector rating_ranks;
public:
template
Players (Input_iterator begin, Input_iterator end)
: players (begin, end)
{
stable_sort (players.begin (), players.end ());
if (adjacent_find (players.begin (), players.end ()) != players.end ()){
// Omar added the following line; throwing runtime_error was causing core dump
cout << "there are players with duplicate names" << endl; exit(0);
throw runtime_error ("there are players with duplicate names");
}
}
size_t
size () const
{
return players.size ();
}
const Player&
get (string player_name) const
{
vector ::const_iterator player = lower_bound (players.begin (), players.end (),
Player (player_name, 0));
if (player->get_name () == player_name)
return *player;
else{
// Omar added the following line
cout << "no such player " << player_name << endl; exit(0);
throw runtime_error ("no such player " + player_name);
}
}
int get_player_rating_rank (const Player& player) const;
const Player&
operator[] (int index) const
{
return players[index];
}
};
const Player Player::NO_ONE;
int
Players::get_player_rating_rank (const Player& player) const
{
if (rating_ranks.empty ())
{
vector players_copy (players);
stable_sort (players_copy.begin (), players_copy.end (), Player::compare_ratings ());
rating_ranks.resize (players.size ());
for (int k = 0, rank = 0; k < players_copy.size (); k++)
{
if (k > 0 && players_copy[k].get_rating () < players_copy[k - 1].get_rating ())
rank++;
rating_ranks[&get (players_copy[k].get_name ()) - &players[0]] = rank;
}
}
return rating_ranks[&get (player.get_name ()) - &players[0]];
}
class Game
{
Player player1;
Player player2;
Player winner;
public:
Game (const Player& player1, const Player& player2, const Player& winner = Player::NO_ONE)
: player1 (player1),
player2 (player2),
winner (winner)
{
if (winner != Player::NO_ONE && winner != player1 && winner != player2){
// Omar added the following line
cout << "a winner not participating in the game, weird" << endl; exit(0);
throw runtime_error ("a winner not participating in the game, weird");
}
}
Game (const Game& other_game)
: player1 (other_game.player1),
player2 (other_game.player2),
winner (other_game.winner)
{ }
Game&
operator= (const Game& other_game)
{
player1 = other_game.player1;
player2 = other_game.player2;
winner = other_game.winner;
return *this;
}
const Player&
get_first_player () const
{
return player1;
}
const Player&
get_second_player () const
{
return player2;
}
const Player&
get_winner () const
{
return winner;
}
const Player& get_opponent (const Player& player) const;
string
to_string () const
{
return player1.get_name () + " vs. " + player2.get_name ();
}
};
const Player&
Game::get_opponent (const Player& player) const
{
if (player == player1)
return player2;
if (player == player2)
return player1;
// Omar added the following line
cout << "player " << player.get_name () << " doesn't participate in game " << endl; exit(0);
throw runtime_error ("player " + player.get_name () + " doesn't participate in game "
+ to_string ());
}
class Tournament
{
public:
class Round
{
vector games;
Player bye_player;
public:
template
Round (Input_iterator games_begin, Input_iterator games_end,
const Player& bye_player = Player::NO_ONE)
: games (games_begin, games_end),
bye_player (bye_player)
{ }
Round (const Round& other_round)
: games (other_round.games),
bye_player (other_round.bye_player)
{ }
Round&
operator= (const Round& other_round)
{
games = other_round.games;
bye_player = other_round.bye_player;
return *this;
}
size_t
size () const
{
return games.size ();
}
const Game&
operator[] (int index) const
{
return games[index];
}
const Player&
get_bye_player () const
{
return bye_player;
}
const Game* get_player_game (const Player& player) const;
};
private:
vector players_vector;
vector rounds_vector;
public:
static Tournament* read_tournament (istream& input);
virtual Players
get_next_round_players (const vector & all_players, const vector & rounds) const
{
// No elimination by default.
return Players (all_players.begin (), all_players.end ());
}
Round
build_next_round () const
{
return build_next_round (get_next_round_players (players_vector, rounds_vector),
rounds_vector);
}
template
Round
build_next_round (Input_iterator rounds_begin, Input_iterator rounds_end) const
{
vector previous_rounds (rounds_begin, rounds_end);
return build_next_round (get_next_round_players (players_vector, previous_rounds),
previous_rounds);
}
private:
Round
build_next_round (const Players& round_players, const vector & previous_rounds) const
{
if (round_players.size () < 2){
// Omar added next 2 lines
cout << "winner " << round_players[0].get_name() << endl; exit(0);
throw new runtime_error ("the tournament is over");
}
if (round_players.size () == 2)
{
const Game only_game (round_players[0], round_players[1]);
return Round (&only_game, &only_game + 1);
}
return do_build_next_round (round_players, previous_rounds);
}
virtual Round do_build_next_round (const Players& round_players,
const vector & previous_rounds) const = 0;
void read_players (istream& input);
void read_rounds (istream& input);
protected:
template
static int
count_games (const Player& player1, const Player& player2,
Input_iterator rounds_begin, Input_iterator rounds_end)
{
int num_games = 0;
for (; rounds_begin != rounds_end; ++rounds_begin)
{
const Game* player1_game = rounds_begin->get_player_game (player1);
if (!player1_game)
continue;
if (player1_game->get_opponent (player1) == player2)
num_games++;
}
return num_games;
}
template
static int
count_losses (const Player& player, Input_iterator rounds_begin, Input_iterator rounds_end)
{
int num_losses = 0;
for (; rounds_begin != rounds_end; ++rounds_begin)
{
const Game* player_game = rounds_begin->get_player_game (player);
if (!player_game)
continue;
if (player_game->get_winner () == player_game->get_opponent (player))
num_losses++;
}
return num_losses;
}
template
static int
count_byes (const Player& player, Input_iterator rounds_begin, Input_iterator rounds_end)
{
int num_byes = 0;
for (; rounds_begin != rounds_end; ++rounds_begin)
{
if (rounds_begin->get_bye_player () == player)
num_byes++;
}
return num_byes;
}
};
class Globally_best_pairing_tournament : public Tournament
{
virtual Round do_build_next_round (const Players& round_players,
const vector & previous_rounds) const;
virtual unsigned int get_game_penalty (const Game& game, const Players& all_players,
const vector & previous_rounds) const = 0;
virtual unsigned int get_bye_penalty (const Player& player, const Players& all_players,
const vector & previous_rounds) const = 0;
struct Tree_node
{
const Tree_node* parent;
int player1_index;
int player2_index;
unsigned int penalty;
struct compare_penalties
{
bool
operator() (const Tree_node* node1, const Tree_node* node2)
{
return node1->penalty > node2->penalty;
}
};
};
class Tree_node_pool
{
static const int NUM_CHUNK_NODES = 0x1000;
vector full_chunks;
Tree_node* current_chunk;
int num_current_chunk_allocated_nodes;
public:
Tree_node_pool ()
: current_chunk (new Tree_node[NUM_CHUNK_NODES]),
num_current_chunk_allocated_nodes (0)
{ }
~Tree_node_pool ()
{
delete[] current_chunk;
for (int k = 0; k < full_chunks.size (); k++)
delete[] full_chunks[k];
}
Tree_node*
allocate_node (const Tree_node* parent)
{
if (num_current_chunk_allocated_nodes == NUM_CHUNK_NODES)
{
full_chunks.push_back (current_chunk);
current_chunk = new Tree_node[NUM_CHUNK_NODES];
num_current_chunk_allocated_nodes = 0;
}
Tree_node* const node = current_chunk + num_current_chunk_allocated_nodes++;
node->parent = parent;
return node;
}
};
class Best_node_collection
{
unsigned int best_penalty;
// NOTE: These have to be lists, since vector reallocation can
// break our pointers.
list under_best_nodes;
list best_nodes;
public:
Best_node_collection ()
: best_penalty (static_cast (-1))
{ }
unsigned int
get_best_penalty () const
{
return best_penalty;
}
void evaluate (const Tree_node* parent,
int player1_index, int player2_index, unsigned int node_penalty);
void evaluate (const Tree_node* parent,
int node1_player1_index, int node1_player2_index, unsigned int node1_penalty,
int node2_player1_index, int node2_player2_index, unsigned int node2_penalty);
const Tree_node*
pick () const
{
// Omar commented out the following line and added the line below
// so that the program will be deterministic and produce the
// same output for the same input.
// unsigned node_index = rand () % best_nodes.size ();
unsigned node_index = best_nodes.size () -1;
list ::const_iterator node = best_nodes.begin ();
for (int k = 0; k < node_index; k++)
node++;
return &*node;
}
};
};
class Elimination : public Globally_best_pairing_tournament
{
int num_losses_to_eliminate;
public:
explicit
Elimination (int num_losses_to_eliminate)
: num_losses_to_eliminate (num_losses_to_eliminate)
{
if (num_losses_to_eliminate < 1){
// Omar added the following line
cout << "number of losses to eliminate must be positive" << endl; exit(0);
throw runtime_error ("number of losses to eliminate must be positive");
}
}
virtual Players
get_next_round_players (const vector & all_players, const vector & rounds) const;
virtual unsigned int get_game_penalty (const Game& game, const Players& all_players,
const vector & previous_rounds) const;
virtual unsigned int get_bye_penalty (const Player& player, const Players& all_players,
const vector & previous_rounds) const;
};
const Game*
Tournament::Round::get_player_game (const Player& player) const
{
for (int k = 0; k < games.size (); k++)
{
if (player == games[k].get_first_player ()
|| player == games[k].get_second_player ())
return &games[k];
}
return 0;
}
Tournament*
Tournament::read_tournament (istream& input)
{
Tournament* tournament;
string scheme;
input >> scheme;
if (scheme == "elimination")
{
int num_losses_to_eliminate;
input >> num_losses_to_eliminate;
tournament = new Elimination (num_losses_to_eliminate);
}
else{
// Omar added the following line
cout << "unknown tournament scheme: " << scheme << endl; exit(0);
throw new runtime_error ("unknown tournament scheme: " + scheme);
}
tournament->read_players (input);
tournament->read_rounds (input);
return tournament;
}
void
Tournament::read_players (istream& input)
{
int num_players;
input >> num_players;
for (int k = 0; k < num_players; k++)
{
string player_name;
int player_rating;
input >> player_name >> player_rating;
players_vector.push_back (Player (player_name, player_rating));
}
}
void
Tournament::read_rounds (istream& input)
{
int num_rounds;
input >> num_rounds;
for (int k = 0; k < num_rounds; k++)
{
Players round_players (get_next_round_players (players_vector, rounds_vector));
Player bye_player;
if (round_players.size () % 2 == 1)
{
string bye_player_name;
input >> bye_player_name;
bye_player = round_players.get (bye_player_name);
}
vector games;
for (int i = 0; i < round_players.size () / 2; i++)
{
string player1_name;
string player2_name;
string winner_name;
input >> player1_name >> player2_name >> winner_name;
games.push_back (Game (round_players.get (player1_name),
round_players.get (player2_name),
round_players.get (winner_name)));
}
rounds_vector.push_back (Round (games.begin (), games.end (), bye_player));
}
}
Tournament::Round
Globally_best_pairing_tournament::do_build_next_round (const Players& round_players,
const vector & previous_rounds) const
{
int num_players = round_players.size ();
unsigned int game_penalties[num_players][num_players];
unsigned int smallest_game_penalties[2] = { static_cast (-1),
static_cast (-1) };
for (int k = 0; k < num_players; k++)
{
game_penalties[k][k] = 0;
for (int i = 0; i < k; i++)
{
unsigned int penalty = get_game_penalty (Game (round_players[i], round_players[k]),
round_players, previous_rounds);
game_penalties[i][k] = penalty;
game_penalties[k][i] = penalty;
if (penalty < smallest_game_penalties[1])
{
if (penalty < smallest_game_penalties[0])
{
smallest_game_penalties[1] = smallest_game_penalties[0];
smallest_game_penalties[0] = penalty;
}
else
smallest_game_penalties[1] = penalty;
}
}
}
Tree_node_pool node_pool;
priority_queue , Tree_node::compare_penalties>
node_queue;
if (num_players % 2 == 1)
{
for (int k = 0; k < num_players; k++)
{
Tree_node* bye_node = node_pool.allocate_node (0);
bye_node->player1_index = k;
bye_node->player2_index = k;
bye_node->penalty = get_bye_penalty (round_players[k], round_players,
previous_rounds);
node_queue.push (bye_node);
}
}
else
{
for (int k = 1; k < num_players; k++)
{
Tree_node* first_game_node = node_pool.allocate_node (0);
first_game_node->player1_index = 0;
first_game_node->player2_index = k;
first_game_node->penalty = game_penalties[0][k];
node_queue.push (first_game_node);
}
}
Best_node_collection best_nodes;
if (num_players < 5)
{
// Much simpler case with no splitting. It can be merged into
// the next case, but we prefer to keep the next one simler at
// the cost of some code duplication.
while (!node_queue.empty ())
{
const Tree_node* lowest_penalty_node = node_queue.top ();
node_queue.pop ();
if (lowest_penalty_node->penalty
> best_nodes.get_best_penalty () - smallest_game_penalties[0])
break;
bool fixed_players[num_players];
fill (fixed_players, fixed_players + num_players, false);
int level = 0;
for (const Tree_node* node = lowest_penalty_node; node; node = node->parent, level++)
{
fixed_players[node->player1_index] = true;
fixed_players[node->player2_index] = true;
}
int player1_index = 0;
while (fixed_players[player1_index])
player1_index++;
int player2_index = player1_index + 1;
while (fixed_players[player2_index])
player2_index++;
best_nodes.evaluate (lowest_penalty_node,
player1_index, player2_index,
game_penalties[player1_index][player2_index]);
}
}
else
{
// Below this limit we split into subsets of more than one
// element; at this limit we have 4 players left, which gives 3
// subsets of one element each.
int depth_limit = (num_players - 3) / 2;
while (!node_queue.empty ())
{
const Tree_node* lowest_penalty_node = node_queue.top ();
node_queue.pop ();
// Since there are at least 4 players left, we have to
// account for at least 2 more penalties.
if (lowest_penalty_node->penalty
> (best_nodes.get_best_penalty ()
- (smallest_game_penalties[0] + smallest_game_penalties[1])))
break;
bool fixed_players[num_players];
fill (fixed_players, fixed_players + num_players, false);
int level = 0;
for (const Tree_node* node = lowest_penalty_node; node; node = node->parent, level++)
{
fixed_players[node->player1_index] = true;
fixed_players[node->player2_index] = true;
}
int player1_index = 0;
while (fixed_players[player1_index])
player1_index++;
if (level < depth_limit)
{
for (int player2_index = player1_index + 1; player2_index < num_players;
player2_index++)
{
if (!fixed_players[player2_index])
{
Tree_node* game_node = node_pool.allocate_node (lowest_penalty_node);
game_node->player1_index = player1_index;
game_node->player2_index = player2_index;
game_node->penalty = (lowest_penalty_node->penalty
+ game_penalties[player1_index][player2_index]);
node_queue.push (game_node);
}
}
}
else
{
int player2_index = player1_index + 1;
while (fixed_players[player2_index])
player2_index++;
int player3_index = player2_index + 1;
while (fixed_players[player3_index])
player3_index++;
int player4_index = player3_index + 1;
while (fixed_players[player4_index])
player4_index++;
best_nodes.evaluate (lowest_penalty_node,
player1_index, player2_index,
game_penalties[player1_index][player2_index],
player3_index, player4_index,
game_penalties[player3_index][player4_index]);
best_nodes.evaluate (lowest_penalty_node,
player1_index, player3_index,
game_penalties[player1_index][player3_index],
player2_index, player4_index,
game_penalties[player2_index][player4_index]);
best_nodes.evaluate (lowest_penalty_node,
player1_index, player4_index,
game_penalties[player1_index][player4_index],
player2_index, player3_index,
game_penalties[player2_index][player3_index]);
}
}
}
vector games;
Player bye_player;
for (const Tree_node* node = best_nodes.pick (); node; node = node->parent)
{
if (node->player1_index != node->player2_index)
{
games.insert (games.begin (), Game (round_players[node->player1_index],
round_players[node->player2_index]));
}
else
bye_player = round_players[node->player1_index];
}
return Round (games.begin (), games.end (), bye_player);
}
void
Globally_best_pairing_tournament::Best_node_collection::
evaluate (const Tree_node* parent, int player1_index, int player2_index, unsigned int node_penalty)
{
unsigned int penalty = parent->penalty + node_penalty;
if (penalty > best_penalty)
return;
if (penalty < best_penalty)
{
best_penalty = penalty;
under_best_nodes.clear ();
best_nodes.clear ();
}
best_nodes.push_back (Tree_node ());
best_nodes.back ().parent = parent;
best_nodes.back ().player1_index = player1_index;
best_nodes.back ().player2_index = player2_index;
}
void
Globally_best_pairing_tournament::Best_node_collection::
evaluate (const Tree_node* parent,
int node1_player1_index, int node1_player2_index, unsigned int node1_penalty,
int node2_player1_index, int node2_player2_index, unsigned int node2_penalty)
{
unsigned int penalty = parent->penalty + node1_penalty + node2_penalty;
if (penalty > best_penalty)
return;
if (penalty < best_penalty)
{
best_penalty = penalty;
under_best_nodes.clear ();
best_nodes.clear ();
}
under_best_nodes.push_back (Tree_node ());
under_best_nodes.back ().parent = parent;
under_best_nodes.back ().player1_index = node1_player1_index;
under_best_nodes.back ().player2_index = node1_player2_index;
best_nodes.push_back (Tree_node ());
best_nodes.back ().parent = &under_best_nodes.back ();
best_nodes.back ().player1_index = node2_player1_index;
best_nodes.back ().player2_index = node2_player2_index;
}
Players
Elimination::get_next_round_players (const vector & all_players,
const vector & rounds) const
{
vector next_round_players;
for (int k = 0; k < all_players.size (); k++)
{
if (count_losses (all_players[k], rounds.begin (), rounds.end ()) < num_losses_to_eliminate)
next_round_players.push_back (all_players[k]);
}
return Players (next_round_players.begin (), next_round_players.end ());
}
unsigned int
Elimination::get_game_penalty (const Game& game, const Players& all_players,
const vector & previous_rounds) const
{
const Player player1 (game.get_first_player ());
const Player player2 (game.get_second_player ());
int num_games = count_games (player1, player2,
previous_rounds.begin (),
previous_rounds.end ());
int num_player1_losses = count_losses (player1,
previous_rounds.begin (),
previous_rounds.end ());
int num_player2_losses = count_losses (player2,
previous_rounds.begin (),
previous_rounds.end ());
int player1_rating_rank = all_players.get_player_rating_rank (player1);
int player2_rating_rank = all_players.get_player_rating_rank (player2);
// Note: the factors are chosen so that number of repeating games is
// always more important than the difference in the number of
// losses, which is more important than the difference in ratings.
/* Omar commented this out to add diffferent code below
return (((num_games * num_losses_to_eliminate + abs (num_player1_losses - num_player2_losses))
* sqr (all_players.size ()))
+ ((sqr (all_players.size ()) - 1)
- sqr (abs (player1_rating_rank - player2_rating_rank))));
*/
// Omar added the following based on input from Karl Jhunke
// see: http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;num=1155933823;start=45#47
int kj1 = sqr (all_players.size() - 1) - sqr (abs (player1_rating_rank - player2_rating_rank));
int kj2 = sqr( abs (num_player1_losses - num_player2_losses)) * sqr (all_players.size ());
int kj5 = sqr(num_games) * sqr(num_losses_to_eliminate) * num_losses_to_eliminate * sqr (all_players.size ()) * all_players.size ();
return (kj1 + kj2 + kj5);
}
unsigned int
Elimination::get_bye_penalty (const Player& player, const Players& all_players,
const vector & previous_rounds) const
{
int num_byes = count_byes (player, previous_rounds.begin (), previous_rounds.end ());
int num_losses = count_losses (player, previous_rounds.begin (), previous_rounds.end ());
int rating_rank = all_players.get_player_rating_rank (player);
// Note: the factors are chosen so that number of already received
// byes is always more important than the number of losses, which is
// more important than the rating.
//
// The final set of factors ensures that the bye penalty is always
// more important than the sum of all game penalties.
/* Omar commented this out to add diffferent code below
return (((num_byes * (1 + previous_rounds.size ()) + num_losses)
* num_losses_to_eliminate + rating_rank)
* ((1 + previous_rounds.size ())
* num_losses_to_eliminate
* sqr (all_players.size ())
* all_players.size ()));
*/
// Omar added the following based on input from Karl Jhunke
// see: http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;num=1155933823;start=45#47
int kj3 = rating_rank * sqr(num_losses_to_eliminate) * sqr (all_players.size ());
int kj4 = num_losses * sqr(num_losses_to_eliminate) * sqr (all_players.size ()) * all_players.size ();
int kj6 = num_byes * sqr(previous_rounds.size ()) * sqr(num_losses_to_eliminate) * num_losses_to_eliminate * sqr(sqr(all_players.size ()));
return(kj3 + kj4 + kj6);
}
int
main ()
{
srand (time (0));
try
{
Tournament* tournament = Tournament::read_tournament (cin);
Tournament::Round next_round = tournament->build_next_round ();
if (next_round.get_bye_player () != Player::NO_ONE)
cout << "Player " << next_round.get_bye_player ().get_name () << " gets a bye" << endl;
for (int k = 0; k < next_round.size (); k++)
cout << next_round[k].to_string () << endl;
delete tournament;
}
catch (exception& exception)
{
cerr << "exception: " << exception.what () << endl;
}
return 0;
}