/*
 ************************************************************************
 *           Allocate players in a Swiss system chess tournament
 *
 * Environment and requirements
 *      1. In one round of the tournament, two parties are played. Thus
 *         a player can score 4/2, 3/2, 2/2, 1/2, and 0/2 points
 *         (that is, from 2 victories to 2 defeats)
 *      2. Any two players may have at most _one_ meeting at a chess
 *         board through the entire tournament
 *      3. The problem is to schedule the next round of the tournament,
 *         given the results of the previous rounds.
 *         That is, the program should tell who is to play with who,
 *         matching partners with as close accumulated scores as possible
 *         (while satisfying requirement 2)
 *
 * The code can save the following data
 *      N_players, Has_played matrix, Scores array
 * into a temporary file, thus allowing restart of the program
 * from a saved history.
 *
 * Call the program
 *      tour                    - "cold" start
 *      tour work_file_name     - resuming the interrupted work
 *
 * $Id$
 *
 ************************************************************************
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

/*
 *=======================================================================
 *        Some screen control routines for a VT-100-type terminal
 */

static void
clear_screen (void)
{
  fprintf (stderr, "\033[H\033[J");
}

static void
cursor (const int row, const int col)
{
  fprintf (stderr, "\033[%0d;%0dH", row, col);
}

static void
message (const char *mess)
{
  cursor (18, 20);
  fprintf (stderr, "%s\n\n\tPress CR to continue...", mess);
  getchar ();
  cursor (18, 0);
  fprintf (stderr, "\033[J");   /* Clear to end-of-screen       */
}


/*
 *=======================================================================
 *                          Global parameters
 */

#define Max_players 512
int N_players;                  /* No of players, should be an even no  */
char Has_played[Max_players + 1][Max_players + 1];
                                /* Has_played[i,j]=1 when i,j have had a */
                                /* game                                 */
int Scores[Max_players + 1];    /* Scores[i] is the i-th player score   */
                                /* times two                            */
                                /* Note, indexing begins at 1 rather    */
                                /* than 0 !!!                           */
int Sorted_indices[Max_players + 1];
                                /* After 'sort()' was called, the follo- */
                                /* ing assertion holds:                 */
                                /* for all i>j within 1..N_players      */
                                /* Scores[Sorted_indices[i]] >=         */
                                /* Scores[Sorted_indices[j]]            */
char Work_file_name[50];


/*
 *=======================================================================
 *                  Entering scores for a finished round
 */
static void
input (void)
{
  register int i;
  int met[Max_players + 1];     /* met[i] is a player participant #i   */
  /* has met in this round               */

  clear_screen ();
  fprintf (stderr, "\n\n\n\t\t\t\033[4mEnter Scores for a round\033[m");
  cursor (16, 0);
  fprintf (stderr, "\tEnter the number of points gained by the player #1\n");
  fprintf (stderr, "\t   i.e. one of the following: 2, 15, 1, 05, 0");

  cursor (7, 0);
  fprintf (stderr, "Player#1");
  for (i = 1; i <= N_players; ++i)
    fprintf (stderr, "%3d", i);
  fprintf (stderr, "\nPlayer#2\nScore");
  memset (met, 0, sizeof (met));

  for (i = 1; i <= N_players; i++)
    {
      int j;                    /* another player's index      */

      if ((j = met[i]) == 0)    /* Player #i met with nobody yet */
        {
          for (;;)              /* Enter a player the i-th      */
            {                   /* player has just had a game with */
              cursor (8, 3 * i + 8);
              scanf ("%d", &j);
              getchar ();
              if (j <= N_players && met[j] == 0 && !Has_played[i][j])
                break;
              message ("These players already had a game with each other!");
            }
          for (;;)              /* Enter the no. of points gained */
            {                   /* by the i-th in the game i-j  */
              char res[4];
              static const struct ScoreDistrib
                {
                  const char *symbol;
                  int player_1_score, player_2_score;
                }
              score_distribution[] =
              {
                {
                  "2\n", 4, 0
                }
                ,               /* Player #1 has won both games */
                {
                  "15\n", 3, 1
                }
                ,               /* One victory and one tie      */
                {
                  "1\n", 2, 2
                }
                ,
                {
                  "05\n", 1, 3
                }
                ,
                {
                  "0\n", 0, 4
                }
                ,
                {
                  0, 0, 0
                }
              };
              register const struct ScoreDistrib *sp;
              cursor (9, 3 * i + 7);
              fprintf (stderr, "   \b\b\b");
              fgets (res, sizeof (res), stdin);
              for (sp = score_distribution; sp->symbol != (char *) 0; sp++)
                if (strcmp (sp->symbol, res) == 0)
                  {
                    Scores[i] += sp->player_1_score;
                    Scores[j] += sp->player_2_score;
                    break;
                  }
              if (sp->symbol != (char *) 0)
                break;
              message ("Illegal specification, use '2','15','1','05','0'");
            }
          Has_played[i][j] = 1;
          Has_played[j][i] = 1;
          met[i] = j;
          met[j] = i;
        }
      cursor (8, 3 * i + 8);
      fprintf (stderr, "%-2d", j);
    }
  message ("");
}

/*
 *=======================================================================
 *                         Sorting scores
 */
                        /* Comparison function for sorting 'Scores'    */
                        /* in descending order                          */
static int
compar (const int *i, const int *j)
{
  return Scores[*j] - Scores[*i];
}


static void
sort (void)                     /* Sorting Scores arranging the indices to     */
{                               /* sorted scores in 'Sorted_indices'           */
  register int i;
  for (i = 1; i <= N_players; i++)      /* Unsorted set of indices      */
    Sorted_indices[i] = i;
  qsort (&(Sorted_indices[1]), N_players, sizeof (Sorted_indices[1]), compar);
}

/*
 *=======================================================================
 *                Perform an allocation for the next game
 */

                        /* Find out how good an allocation allo is      */
                        /* allo[i] is a party for player #i             */
static int
find_measure (const int allo[])
{
  register int i;               /* The closer scores of the parties,    */
  register int measure = 0;     /* the less is the measure, the         */
  for (i = 1; i <= N_players; ++i)      /* better is allocation                 */
    measure += abs (Scores[i] - Scores[allo[i]]);
  return measure;
}

                         /* Try some allocation and select the best      */
static void
try_allocate (int best_allo[])
{
  int level;                    /* Level of search 1..N_players/2 */
  int si[Max_players / 2 + 1];  /* For stack simulation         */
  int sj[Max_players / 2 + 1];
  int allo[Max_players + 1];    /* i-th player will have a game */
  /* with the allo[i]-th player   */
  int best_measure = 32767;     /* Measure for the best allo    */

  int i, j=0;
  int status;                   /* Automaton status             */

#define N_retries 5             /* No of attempts to find best alloc */
  int retry_no;

  memset (allo, 0, sizeof (allo));
  /* Build a list of N_players/2 pairs    */
  /* using several trials if necessary    */
  /* level counts the number of games     */
  /* arranged so far: level=N_players/2   */
  /* means the complete round             */
  /* At each level, we pick up            */
  /* players Sorted_indices[i]            */
  /* and Sorted_indices[j]                */
  /* and check to see if they have already */
  /* played with each other.              */
  /* For backtracking, we save i, and j in */
  /* si[level],sj[level]                  */
  for (i = 0, level = 1, status = 0, retry_no = 0; retry_no < N_retries;)
    {
      register int ti=0, tj=0;
      switch (status)
        {
        case 0:         /* Find a candidate for level-th game */
          i++;
          status = (i > N_players ? 4 :
                    (ti = Sorted_indices[i], allo[ti] == 0 ? 1 : 0));
          continue;

        case 1:         /* Begin to search for the      */
          j = i;                /* party for the ti-th player   */
          status = 2;

        case 2:         /* Find and test the party      */
          if (++j > N_players)
            {                   /* Search failed for ti-th party */
              status = 0;       /* Pick another ti              */
              continue;
            }                   /* tj-th player has just been   */
          tj = Sorted_indices[j];
          if (allo[tj] || Has_played[ti][tj])   /* allocated      */
            continue;           /* or ti-tj game took place     */
          status = 3;

        case 3:         /* ti-tj game is arranged       */
          allo[ti] = tj;
          allo[tj] = ti;
          si[level] = i;
          sj[level] = j;
          if (++level > N_players / 2)  /* All games in a tour has been */
            {                   /* allocated                    */
              register int measure = find_measure (allo);
              if (measure < best_measure)
                {               /* Save the best allocation     */
                  best_measure = measure;       /* found beforehand             */
                  memcpy (best_allo, allo, sizeof (allo));
                }
              ++retry_no;
              status = 4;       /* Find another alloc if possible */
            }
          else
            status = 0;
          continue;

        case 4:         /* back tracking to the prev.   */
          level--;              /* level                        */
          if (level < 1)
            break;              /* no more alternatives         */
          i = si[level];        /* Restore values for the prev  */
          j = sj[level];        /* level                        */
          ti = Sorted_indices[i];
          tj = Sorted_indices[j];
          allo[ti]  = 0;
          allo[tj] = 0;
          status = 2;
          continue;
        }
      break;
    }

  if (retry_no == 0)
    message ("Allocation failed!");
}

static void
print_allocation (const int allo[])
{
  FILE *pr = fopen ("prn", "w");
  register int i;

  assert (pr != (FILE *) 0);
  fprintf (pr, "player #1");
  for (i = 1; i <= N_players; ++i)
    fprintf (pr, "%3d", i);
  fprintf (pr, "\nplayer #2");
  for (i = 1; i <= N_players; ++i)
    fprintf (pr, "%3d", allo[i]);
  fprintf (pr, "\n\f");
  fclose (pr);
}


                        /* Root scheduling module               */
static void
allocation (void)
{
  int allo[Max_players + 1];    /* i-th player will have a game */
  /* with the allo[i]-th player   */
  register int i;

  cursor (18, 20);
  fprintf (stderr, "\033[4mT h i n k i n g ...\033[m");
  sort ();                      /* Sort 'Scores' in desc. order */
  try_allocate (allo);

  clear_screen ();
  fprintf (stderr, "\n\n\n\t\t\t\033[4mALLOCATION FOR A NEW TOUR\033[m");

  cursor (7, 0);
  fprintf (stderr, "Player #1");
  for (i = 1; i <= N_players; ++i)
    fprintf (stderr, "%3d", i);
  fprintf (stderr, "\nPlayer #2");
  for (i = 1; i <= N_players; ++i)
    fprintf (stderr, "%3d", allo[i]);
  cursor (18, 20);
  fprintf (stderr, "Print the allocation?");
  if (toupper (getchar ()) == 'Y')
    print_allocation (allo);
  getchar ();
}

/*
 *=======================================================================
 *                    Output the concluding results
 */
static void
concluding_results (void)
{
  register int i;

  sort ();                      /* Sort 'Scores' in descending order   */
  clear_screen ();
  fprintf (stderr, "\n\n\n\t\t\t\033[4mCONCLUDING RESULTS\033[m");

  cursor (7, 0);
  fprintf (stderr, "Player");
  for (i = 1; i <= N_players; ++i)
    fprintf (stderr, "%3d", Sorted_indices[i]);
  fprintf (stderr, "\nScore");
  for (i = 1; i <= N_players; ++i)
    {
      register int res = Scores[Sorted_indices[i]];
      cursor (8, 3 * i + 4);
      fprintf (stderr, "%3d", res / 2);         /* Integral part of result      */
      if (res % 2)              /* Output a half a point        */
        {                       /* if any                       */
          cursor (9, 3 * i + 5);
          fprintf (stderr, "/2");
        }
    }
  message ("");
}

/*
 *=======================================================================
 *                      Save status for recovery
 */

static void
save_status (void)
{
  FILE *fp = fopen (Work_file_name, "wb");
  assert (fp != (FILE *) 0);
  putw (N_players, fp);
  fwrite (Has_played, sizeof (Has_played), 1, fp);
  fwrite (Scores, sizeof (Scores), 1, fp);
  fclose (fp);
  message ("Saved");
}

/*
 *=======================================================================
 *                         Getting started
 */

                        /* Start from scratch                            */
static void
cold_start (void)
{
  int i;

  fprintf (stderr, "\n\nHow many people will take part in the tournament >");
  scanf ("%d", &N_players);
  getchar ();
  if (N_players <= 4 || N_players > Max_players || N_players % 2)
    fprintf (stderr, "\nBad no '%d'", N_players), exit (EXIT_FAILURE);
  fprintf (stderr, "\nWork file name >");
  fgets (Work_file_name, sizeof (Work_file_name), stdin);
  Work_file_name[sizeof (Work_file_name) - 1] = '\n';
  *strchr (Work_file_name, '\n') = '\0';

  for (i = 1; i <= N_players; i++)      /* Each guy has played with himself */
    Has_played[i][i] = 1;
}

                        /* Resume the interrupted execution             */
                        /* using already accumulated history            */
static void
warm_start (const char *file_name)
{
  FILE *fp;

  strncpy (Work_file_name, file_name, sizeof (Work_file_name) - 1);
  fp = fopen (Work_file_name, "rb");
  assert (fp != (FILE *) 0);
  N_players = getw (fp);
  if (N_players <= 4 || N_players > Max_players || N_players % 2)
    fprintf (stderr, "\nBad no '%d'", N_players), exit (EXIT_FAILURE);
  fread (Has_played, sizeof (Has_played), 1, fp);
  fread (Scores, sizeof (Scores), 1, fp);
  fclose (fp);
}

                        /* The Main module                      */
int
main (int argc, const char *argv[])
{
  if (argc > 2)
    fprintf (stderr, "Too many arguments. Only work file name may be specified"),
      exit (EXIT_FAILURE);

  if (argc == 1)
    cold_start ();
  else
    warm_start (argv[1]);

  for (;;)                      /* Main loop    */
    {
      clear_screen ();
      cursor (3, 0);
      fprintf (stderr, "\t\t\t\033[4mM A I N   M E N U\033[m\n\n");
      fprintf (stderr, "\t\t1. Enter scores for a finished round\n");
      fprintf (stderr, "\t\t2. Perform an allocation for the next round\n");
      fprintf (stderr, "\t\t3. Output concluding results\n");
      fprintf (stderr, "\t\t4. Save status to the work file\n");
      for (;;)
        {
          int c;
          cursor (15, 20);
          fprintf (stderr, "Enter your choice \033[1m>\033[m");
          switch ((c = getchar (), getchar (), c))
            {
            case '1':
              input ();
              break;

            case '2':
              allocation ();
              break;

            case '3':
              concluding_results ();
              break;

            case '4':
              save_status ();
              break;

            default:
              continue;
            }
          break;
        }
    }
  return 0;
}