/************************************************************************
**
** NAME:        partners.c
**
** DESCRIPTION: This code solves the 2-person partnering problem, which is:
**             
**              Assume you have n students. You would like to have lab
**              sections in which these students choose partners
**              to work together. Over the course of the semester, you'd
**              like to have every student work with every other student
**              exactly once. As there are n students, this can be done in
**              n-1 days optimally. How is it done? (e.g. show how to pair
**              20 students up)
**
** AUTHOR:      Dan Garcia  -  University of California at Berkeley
**              Copyright (C) Dan Garcia, 1998. All rights reserved.
**
** DATE:        1998-09-23
**
** TO COMPILE:  unix% cc -o partners partners.c
**
** TO RUN:      unix% ./partners
**
** EXAMPLE:     unix% ./partners
**              unix% ./partners v1.0 by Dan Garcia <ddgarcia@cs.berkeley.edu>
**              Enter the number of students to be paired up (must be even): 4
**              
**              Partner Table (people on rows and columns, 
**              matrix contains day they meet)
**              
**                  2  3  4
**                +---------
**               1| 1  2  3
**               2|    3  2
**               3|       1
**              
**              Parsing the table into a useful form:
**              
**              Day  1:[1-2][3-4]
**              Day  2:[1-3][2-4]
**              Day  3:[1-4][2-3]
**              
** UPDATE HIST: v1.0 - Release
**
**************************************************************************/

#include <stdio.h>
#define VERSION "v1.0"
#define AUTHOR  "Dan Garcia <ddgarcia@cs.berkeley.edu>"

/************************************************************************
**
** NAME:        main
**
** DESCRIPTION: The starting point to the code. PrintHelloGetStudents
**              gets the number of students, returns it to PrintPartners
**              which prints the pairings.
** 
************************************************************************/

main(argc,argv)
int argc;
char **argv;
{
  PrintPartners(PrintHelloGetStudents(argv));
}

/************************************************************************
**
** NAME:        PrintHelloGetStudents
**
** DESCRIPTION: Print Hello, then get the number of partners and return it.
** 
************************************************************************/

PrintHelloGetStudents(argv)
char **argv;
{
  int p;
  printf("%s %s by %s\n",argv[0],VERSION,AUTHOR);
  printf("Enter the number of students to be paired up (must be even): ");
  scanf("%d",&p);
  if ((2 * (p / 2)) != p) { /* Not even */
    printf("Sorry, p was not even...exiting.\n");
    exit(1);
  }
  return(p);
}

/************************************************************************
**
** NAME:        PrintPartners
**
** DESCRIPTION: Print the way people should partner up so that everyone
**              meets everyone else optimally.
** 
************************************************************************/

PrintPartners(p)
int p;
{
  int p1,p2,r,c,day;
  int i,j;
  int *index, **m;
  
  /* Storage for the post-processing matrix */

  index = (int *) malloc ((p-1) * sizeof(int));
  m = (int **) malloc ((p-1) * sizeof (int *));
  for(i=0;i<p-1;i++) {
    index[i]=0;
    m[i] = (int *) malloc ((p) * sizeof(int));
  }

  /* Print the table, save rows into the matrix */

  p1 = p - 1;
  p2 = p - 2;
  printf("\nPartner Table (people on rows and columns, matrix contains day they meet)\n\n   ");
  for(c = 0; c <= p2; c++)
    printf("%2d ",c+2);
  printf("\n  +");
  for(c = 0; c <= p2; c++)
    printf("---",c+2);
  for(r = 0; r <= p2; r++) {
    printf("\n%2d|",r+1);
    for(c = 0; c <= (r-1); c++)
      printf("   ");
    for(c = r; c <= p2; c++) {
      day = (((c == p2) ? (p2 + 2*r) : (r+c)) % p1) + 1;
      /*printf("[%d,%d,%d]\n",c,r,day);*/
      *(m[day-1] + index[day-1]+0) = r+1;
      *(m[day-1] + index[day-1]+1) = c+2;
      index[day-1]+=2;
      printf("%2d ", day);
    }
  }

  /* Print the matrix */

  printf("\n\nParsing the table into a useful form:\n\n");

  for(i = 0;i < p-1; i++) {
    printf("Day %2d:",i+1);
    for(j=0;j<p;j+=2) {
      printf("[%d-%d]",*(m[i]+j),*(m[i]+j+1));
    }
    printf("\n");
  }
}