//----------------------------------------------------------------------------
// ypSched.c
//
//----------------------------------------------------------------------------
//  Change history
//
//  28-dec-99 Originally written by J. Henckel
//  7-dec-01  added room numbers & descriptions
//  1-dec-02  allow new input format "name",n,n,n,n
//  6-dec-02  allow prereq and coreq classes

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

//----------------------------------------------------------------------------
//  terminology
//
//  a period is an time spot, like "Wednesday afternoon".  each period has
//  several classes (in parallel).  each class has a topic and a size.  each
//  student is enrolled in exactly one class per period.  each student has
//  preferences based on the topic.  a topic may be offered during several
//  periods.  the num_seat is the total number of seats available for a
//  particular topic.
//
//  NOTE:  do not have more than one class in the same period on the
//  same topic, or else things might not work.  If you do have two classes
//  like that, then just add their size together and call it one big class.
//
//  A word of explanation about prereqs.  Instead of making one topic prereq
//  another, I decided to make one class prereq another.  A class is a
//  topic at a specific period.  It's less flexible, but lots easier for me
//  to implement.  The (prep,prec) pair points from each class to its
//  prereq class.  The (prap,prac) is the backwards pointer for the same
//  relation (it is needed for unenroll to remove dependents of a class).
//  If you wanna make co-requisite classes, you can just make them prereq
//  each other in a circle.

//----------------------------------------------------------------------------
//  types

typedef struct
{
  char *name;
  int *enroll;       // one per period
  int happiness;
  int *pref;        // one per topic
  int *seen;        // one per topic
  int num_enroll;
}
Student;

typedef struct
{
  char *name;
  int num_period;
  int num_seat;
  int sum_pref;
}
Topic;

typedef struct   // all these int* are base-1 arrays.
{
  char *name;       // such as "Wednesday morning"
  int *topic;       // list of topics
  int *size;        // how many seats are available
  int *cap;         // total number of seats
  int *room;        // room number (for output only)
  int *prec;        // prerequisite class (base 1)
  int *prep;        // prerequisite period (if prec nonzero)7
  int *prac;        // post-requisite class (base 1)
  int *prap;        // post-requisite period (if prac nonzero)
}
Period;

//----------------------------------------------------------------------------
//   global data
//
//   note: the arrays in each period are base 1 (zeroth entry not used)
//   because the enroll[] array uses zero to indicate "not enrolled".


int num_student;
Student *student;

int num_topic;
Topic *topic;

int num_period;
Period *period;

int max_class;       // max num classes per period PLUS ONE

double w1 = 5.0;     // weight for flexibility vs demand
int prevent_repeat = 0;  // no hard constraint for non-repeat
int debug = 1;       // medium level output
int swlim = 100;
int quick = 0;        // only binary swaps in optimizer
int evenly = 1;
int export = 0;

int *perm;          // random order of students

//----------------------------------------------------------------------------
//  random number

int Random(int m)
{
  return rand() % m;
}

//----------------------------------------------------------------------------
//   string duplicate

char* StringDup(char* s)
{
  char *t;
  int n;
  if (!s) return NULL;
  n = strlen(s) + 1;
  t = malloc(n);
  memcpy(t,s,n);
  while (n-- && t[n]<=' ')      // remove trailing whitespace
    t[n]=0;
  return t;
}

//----------------------------------------------------------------------------
//   read data file
//
//  FILE FORMAT
//     topics #topic
//     <a list of topics, one line each>
//     periods #period, max#classes per period
//     <a list of period names, one line each, and
//        each followed by max# pairs (topic, class size, room#) >
//     students #students
//     <a list of student names, one line each, and
//        each followed by preference scores, one per topic. >


int ReadFile(char *filename)
{
  int i,j,rc;
  char buf[200];
  FILE *f;

  if (debug>1) printf("open file %s\n",filename);

  f = fopen(filename, "r");

  if (!f || ferror(f))
    return printf("Unable to read from data file\n");

  //-----------------------
  //  topics

  while (fgets(buf, sizeof buf, f) && strncmp(buf,"topics ",7));
  sscanf(buf+7, "%d", &num_topic);
  topic = calloc(num_topic, sizeof *topic);

  if (debug>1) printf("reading %d topics\n",num_topic);

  for (i=0; i< num_topic; ++i)
  {
    fgets(buf, sizeof buf, f);
    topic[i].name = StringDup(buf);

#if 0
    j = topic[i].name[strlen(topic[i].name)-1];
    if (j=='=' || j=='+')
    {
      topic[i].name[strlen(topic[i].name)-1] = 0;
      topic[i].prereq = i - 1;     // pre-requisite
      if (j=='=')                  // co-requisites
      {
        topic[i].prereq = topic[i-1].prereq;
        topic[i-1].prereq = i;
      }
    }
    else topic[i].prereq = i;         // self requisite
#endif

    if (debug>1) printf("topic %d = %s\n",i,topic[i].name);
    topic[i].sum_pref = 0;
  }

  //-----------------------
  //  periods

  while (fgets(buf, sizeof buf, f) && strncmp(buf,"periods ",8));
  sscanf(buf+8, "%d %d", &num_period, &max_class);
  period = calloc(num_period, sizeof *period);
  ++max_class;                 // make room for base-1 arrays

  if (debug>1) printf("reading %d periods\n",num_period);

  for (i=0; i< num_period; ++i)
  {
    fgets(buf, sizeof buf, f);
    period[i].name = StringDup(buf);
    if (debug>1) printf("period %d = %s\n",i,period[i].name);

    period[i].topic = calloc(max_class, sizeof(int));
    period[i].size  = calloc(max_class, sizeof(int));
    period[i].cap   = calloc(max_class, sizeof(int));
    period[i].room  = calloc(max_class, sizeof(int));
    period[i].prec  = calloc(max_class, sizeof(int));
    period[i].prep  = calloc(max_class, sizeof(int));
    period[i].prac  = calloc(max_class, sizeof(int));
    period[i].prap  = calloc(max_class, sizeof(int));

    for (j=1; j<max_class; ++j)
    {
      fscanf(f, "%d %d %d ", &period[i].topic[j], &period[i].size[j], &period[i].room[j]);
      rc = fgetc(f);                // get the comma
      if (rc > 0 && rc != ',')      // if not a comma put it back
        ungetc(rc,f);
      period[i].cap[j] = period[i].size[j];
      if (period[i].size[j] == 0)
        period[i].topic[j] = -1;           // flag a dummy class
    }
  }

  //-----------------------
  //   prereqs

  rc = 0;
  while (fgets(buf, sizeof buf, f))
  {
    int p1,c1,p2,c2;

    if (!strncmp(buf,"students ",9))
      break;
    if (!rc && !strncmp(buf,"prereqs",7))
    {
      rc = 1;
      if (debug>1) printf("reading prereqs\n");
      continue;
    }
    if (4 != sscanf(buf, "%d %d, %d %d", &p1, &c1, &p2, &c2))
    {
      if (strlen(buf) > 4)
        printf("ERROR unable to parse prereq: %s\n",buf);
      continue;
    }
    if (debug>1)
      printf("%s (%d. %.10s) prereq of %s (%d. %.10s)\n",
              period[p1].name, c1, topic[period[p1].topic[c1+1]].name,
              period[p2].name, c2, topic[period[p2].topic[c2+1]].name);

    c1++; c2++;
    if (p1 < 0 || p1 >= num_period ||
        p2 < 0 || p2 >= num_period ||
        c1 < 1 || c1 >= max_class ||
        c2 < 1 || c2 >= max_class)
    {
      printf("ERROR prereq is not correct ==> %s\n",buf);
      continue;
    }
    period[p1].prac[c1] = c2;
    period[p1].prap[c1] = p2;      //  (p1,c1) is prereq of (p2,c2)
    period[p2].prec[c2] = c1;
    period[p2].prep[c2] = p1;
  }

  //-----------------------
  //   students

//  while (fgets(buf, sizeof buf, f) && strncmp(buf,"students ",9));
  sscanf(buf+9, "%d", &num_student);
  student = calloc(num_student, sizeof *student);

  if (debug>1) printf("reading %d students\n",num_student);

  for (i=0; i< num_student; ++i)
  {
    buf[0] = rc = fgetc(f);
    if (rc=='"')      // new format "name",n,n,n,n
      fscanf(f,"%[^\"]\",",buf);
    else
      fgets(buf+1, sizeof buf, f);

    student[i].name = StringDup(buf);
    if (debug>1) printf("student %d = %s\n",i,student[i].name);

    student[i].pref = calloc(num_topic, sizeof(int));
    student[i].seen = calloc(num_topic, sizeof(int));
    student[i].enroll = calloc(num_period, sizeof(int));
    student[i].num_enroll = 0;

    for (j=0; j<num_topic; ++j)
    {
      fscanf(f, "%d%c", &student[i].pref[j],&rc);
      if (debug>1) printf(" %d",student[i].pref[j]);
    }
    if (debug>1) printf("\n");
  }
  rc = ferror(f);

  if (debug>1) printf("closing file %s rc=%d\n",filename,rc);

  fclose(f);
  return rc;
}

//----------------------------------------------------------------------------
//   run this after reading the data file

void FinishInit(void)
{
  int i,j,t,n;

  perm = calloc(num_student, sizeof *student);
  for (i=0; i< num_student; ++i)
    perm[i] = i;

  for (i=0; i< num_student; ++i)
    for (j=0; j< num_topic; ++j)
      topic[j].sum_pref += student[i].pref[j];

  if (debug) printf("\n");
  for (i=0; i< num_period; ++i)
  {
    n = 0;
    for (j=1; j< max_class; ++j)
    {
      if (period[i].cap[j] > 0)
      {
        n += period[i].cap[j];
        t = period[i].topic[j];
        assert(t >= 0 && t < num_topic);
        topic[t].num_period += 1;
        topic[t].num_seat += period[i].cap[j];
      }
    }
    if (debug)
      printf("    %d seats on %s\n", n, period[i].name);
  }
  if (debug)
  {
    printf("\n");
    for (j=0; j< num_topic; ++j)
      printf("    %d seats in %d. %s\n", topic[j].num_seat, j, topic[j].name);
  }
}

//----------------------------------------------------------------------------
//  debug tool to check for prereqs

int checkprereq()
{
  int i, p, c, c2, t=0;
  for (i=0; i<num_student; ++i)
  {
    for (p=0; p<num_period; ++p)
    {
      c = student[i].enroll[p];
      if (c)
      {
        c2 = period[p].prec[c];

        if (c2 && student[i].enroll[period[p].prep[c]] != c2)
          printf("MISSING PREREQ %d %d %d %d\n",i,p,c,c2,++t);
      }
    }
  }
  return t;
}

//----------------------------------------------------------------------------
//   find a class for student s, offering topic t.
//   return 1 if success.

int FindClass(int s, int t, int *p, int *c)
{
  int i,j,y;

  i = Random(num_period);
  for (y=0; y<num_period; ++y, ++i)
  {
    if (i >= num_period) i=0;

    //  Can't go to two classes at once

    if (student[s].enroll[i] > 0)
      continue;

    for (j=1; j<max_class; ++j)

      //  Don't exceed the class size

      if (period[i].size[j] > 0 && period[i].topic[j] == t)
      {
        *p = i;
        *c = j;
        return 1;
      }
  }
  return 0;
}

//----------------------------------------------------------------------------
//   UnEnroll student s in period p, class c.

void UnEnroll(int s, int p, int c, int x)
{
  int t = period[p].topic[c];

  if (debug>2) printf("%.*sunenroll %d %d %d\n",x,"........",s,p,c);

  assert(student[s].enroll[p] == c);
  assert(student[s].num_enroll > 0);
  assert(student[s].seen[t] > 0);

  student[s].enroll[p] = 0;
  student[s].num_enroll -= 1;
  student[s].happiness -= student[s].pref[t];
  student[s].seen[t] -= 1;
  period[p].size[c] += 1;
  topic[t].num_seat += 1;
  topic[t].sum_pref += student[s].pref[t];

  if (period[p].size[c] == 1)
    topic[t].num_period += 1;

  //  test for postreq (a class that prereq's this one)
  t = c;
  c = period[p].prac[t];
  p = period[p].prap[t];
  t = period[p].topic[c];

  if (c && student[s].enroll[p]==c)
      UnEnroll(s, p, c,x+1);
}

//----------------------------------------------------------------------------
//   Enroll student s in period p, class c.
//
//   return 1=success, 0=some prereqs not satisfied.

int Enroll(int s, int p, int c, int x)
{
  int t = period[p].topic[c];

  if (debug>2) printf("%.*senroll   %d %d %d\n",x,"........",s,p,c);

  assert(student[s].enroll[p] == 0);

  student[s].enroll[p] = c;
  student[s].num_enroll += 1;
  student[s].happiness += student[s].pref[t];
  student[s].seen[t] += 1;
  period[p].size[c] -= 1;
  topic[t].num_seat -= 1;
  topic[t].sum_pref -= student[s].pref[t];

  //  if took last seat...
  if (period[p].size[c] == 0)
    topic[t].num_period -= 1;

  //  test for prereq
  t = c;
  c = period[p].prec[t];
  p = period[p].prep[t];
  t = period[p].topic[c];

  if (c && student[s].enroll[p] != c)    // prereq is required
  {
    assert(student[s].enroll[period[p].prap[c]]==period[p].prac[c]);

    if (student[s].enroll[p])
      UnEnroll(s,p,student[s].enroll[p],x+1);

    assert(!student[s].enroll[p]);
    Enroll(s, p, c, x+1);

    assert(student[s].enroll[p]==c);
    assert(student[s].seen[t]);
    assert(student[s].enroll[period[p].prap[c]]==period[p].prac[c]);
  }
  return 1;
}

//----------------------------------------------------------------------------
//   enroll a student in whatever seems best for them in given period.
//   return the class number in the period.  student must be unenrolled.

int EnrollBest(int s, int p)
{
  int c, t, h, bh, bc=0;

  if (debug>2) printf("enrollbest %d %d \n",s,p);

  assert(student[s].enroll[p] == 0);

  for (c = 1; c < max_class; ++c)
  {
    t = period[p].topic[c];
    h = -10*student[s].seen[t] + student[s].pref[t];
    if (period[p].size[c] < 1)
      h -= 100*(1 - period[p].size[c]);  // penalize too full classes
    if (h > bh || c==1)
    {
      bh = h;
      bc = c;
    }
  }
  if (bc)
    Enroll(s, p, bc,0);

  return bc;
}

//----------------------------------------------------------------------------
//   pick the topic with least num_period and highest demand, and
//   assign one student to it.  repeat until everyone reaches
//   the enrollment limit.

void Assignment(int limit)
{
  int i,t,s,p,c,y;
  double d, best_d;

  while (1)
  {
    t = -1;

    for (i=0; i<num_topic; ++i)
    {
      if (topic[i].num_seat < 1) continue;

      //  This is the topic heuristic....

      d = w1 / topic[i].num_period + 1.0 * topic[i].sum_pref / topic[i].num_seat;

      if (t < 0 || d > best_d)
      {
        t = i; best_d = d;
      }
    }

    if (t == -1)          // no more seats in any topic
      break;

    s = -1;
    i = Random(num_student);
    for (y=0; y<num_student; ++y, ++i)
    {
      if (i >= num_student) i=0;

      if (student[i].num_enroll >= limit) continue;

      //  This is the student heuristic....

      d = student[i].seen[t] ? -100 : student[i].pref[t];

      if (s < 0 || d > best_d || d == best_d &&
           student[i].happiness < student[s].happiness)
      {
        if (FindClass(i,t,&p,&c))
        {
          s = i;
          best_d = d;
        }
      }
    }

    //  The following makes the "no repeat topic" a hard constraint

    if (best_d == -100 && prevent_repeat)
      s = -1;

    //  test if no more students can take this topic.  This only happens
    //  if the number of seats in some period exceeds the number of students.

    if (s == -1)
      topic[t].num_seat = 0;
    else
      Enroll(s,p,c,0);

    if (debug>2) checkprereq();   // This is for debugging
  }
}

//----------------------------------------------------------------------------
//  This is used to accumulate the effect of a swap, h is the change in
//  happiness, and e is change in square of happiness (which is used as a
//  measure of fairness.

#define DELTA_he(s1,t1,t2) \
        h += student[s1].pref[t2] - student[s1].pref[t1]; \
        e += (student[s1].pref[t2] - student[s1].pref[t1])* \
             (student[s1].pref[t2] + student[s1].pref[t1])

//----------------------------------------------------------------------------
//   this makes one pass over every period and pair of students.
//   the students are swapped if it improves the total happiness.

void SearchAndSwap(void)
{
  int p,h,e, i1, i2, i3;
  int s1, s2, s3, c1, c2, c3, t1, t2, t3;

  for (p=0; p<num_period; ++p)
  {
    for (i1=0; i1<num_student; ++i1)
    {
      s1 = perm[i1];
      c1 = student[s1].enroll[p];

      //  Check for non-enrolled

      if (c1==0)
        c1 = EnrollBest(s1,p);

      //  Check for move to a class that is not full

      for (c2=1; c2<max_class; ++c2)
        if (c1 != c2 && period[p].size[c2] > 0)
        {
          t1 = period[p].topic[c1];
          t2 = period[p].topic[c2];
          h = student[s1].pref[t2] - student[s1].pref[t1];

          if (!student[s1].seen[t2] &&
              (h > 0 ||
                student[s1].seen[t1] > 1 ||
                evenly && h >= 0 &&
                period[p].size[c1]+1 < period[p].size[c2]))
          {
            UnEnroll(s1,p,c1,0);
            Enroll(s1,p,c2,0);
            c1 = c2;
          }
        }

      //  Check for swap with other student

      for (i2=i1 + 1; i2<num_student; ++i2)
      {
        s2 = perm[i2];
        c1 = student[s1].enroll[p];
        c2 = student[s2].enroll[p];
        if (c2==0)
          c2 = EnrollBest(s2,p);
        t1 = period[p].topic[c1];
        t2 = period[p].topic[c2];

        if (t1 == t2)
          continue;

        h = e = 0;
        DELTA_he(s1,t1,t2);
        DELTA_he(s2,t2,t1);

        //  if swapping would improve the total happiness
        //  or make things more equitable
        //  or fix a repeat problem, then do it.
        //  we get fairness by minimizing e, the change in sum-sq happiness.

        if (h > 0 || h==0 && e < 0 ||
            student[s1].seen[t1] > 1 ||
            student[s2].seen[t2] > 1)
        {
          //  If is doesn't cause a conflict, swap 'em

          if (!student[s1].seen[t2] &&
               !student[s2].seen[t1])
          {
            UnEnroll(s1,p,c1,0);
            UnEnroll(s2,p,c2,0);
            Enroll(s1,p,c2,0);
            Enroll(s2,p,c1,0);
            continue;
          }
        }

        if (quick)
          continue;

        //  If the two way swap was not feasable, try a three way swap

        for (i3=i2 + 1; i3<num_student; ++i3)
        {
          s3 = perm[i3];
          c3 = student[s3].enroll[p];
          if (c3==0)
            c3 = EnrollBest(s3,p);
          t3 = period[p].topic[c3];

          if (t1==t3 || t2==t3)
            continue;

          h = e = 0;
          DELTA_he(s1,t1,t2);
          DELTA_he(s2,t2,t3);
          DELTA_he(s3,t3,t1);

          if (h > 0 || h==0 && e < 0 ||
              student[s1].seen[t1] > 1 ||
              student[s2].seen[t2] > 1 ||
              student[s3].seen[t3] > 1)
          {
            //  If is doesn't cause a conflict, swap 'em

            if (!student[s1].seen[t2] &&
                 !student[s2].seen[t3] &&
                 !student[s3].seen[t1])
            {
              UnEnroll(s1,p,c1,0);
              UnEnroll(s2,p,c2,0);
              UnEnroll(s3,p,c3,0);
              Enroll(s1,p,c2,0);
              Enroll(s2,p,c3,0);
              Enroll(s3,p,c1,0);
              break;
            }
          }

          //  Try a reverse 3-way swap

          h = e = 0;
          DELTA_he(s1,t1,t3);
          DELTA_he(s2,t2,t1);
          DELTA_he(s3,t3,t2);

          if (h > 0 || h==0 && e < 0 ||
              student[s1].seen[t1] > 1 ||
              student[s2].seen[t2] > 1 ||
              student[s3].seen[t3] > 1)
          {
            //  If is doesn't cause a conflict, swap 'em

            if (!student[s1].seen[t3] &&
                 !student[s2].seen[t1] &&
                 !student[s3].seen[t2])
            {
              UnEnroll(s1,p,c1,0);
              UnEnroll(s2,p,c2,0);
              UnEnroll(s3,p,c3,0);
              Enroll(s1,p,c3,0);
              Enroll(s2,p,c1,0);
              Enroll(s3,p,c2,0);
              break;
            }
          }

          //  Try a four way swap...  ha ha, just kidding
        }
      }
    }
  }

  //  Kick out people from overfilled classes.

  for (p=0; p<num_period; ++p)
  {
    for (c1=1; c1<max_class; ++c1)
    {
      for (h=period[p].size[c1]; h<0; ++h)   /* h prevents getting stuck */
      {
        //  choose a student to kick out

        for (i1=0; i1<num_student; ++i1)
        {
          s1 = perm[i1];

          // if student is in class c and c is not prereq of anything or
          // student is not taking the thing c is the prereq of, then kick student.
          
          if (student[s1].enroll[p] == c1 &&
              (period[p].prac[c1] == 0 ||
               student[s1].enroll[period[p].prap[c1]] == 0 ||
               student[s1].enroll[period[p].prap[c1]] != period[p].prac[c1]))
          {
            UnEnroll(s1, p, c1, 0);
            break;
          }
        }
      }
    }
  }

  //  Final check that every student is enrolled in something

  e = 1;
  for (h=0; h<5 && e; ++h)
  {
    e = 0;
    for (p=0; p<num_period; ++p)
    {
      for (i1=0; i1<num_student; ++i1)
      {
        s1 = perm[i1];
        c1 = student[s1].enroll[p];
        if (c1==0)
        {
          c1 = EnrollBest(s1,p);
          ++e;
        }
      }
    }
  }
}

//----------------------------------------------------------------------------
//   optimize the schedule by swapping

void Optimizer(void)
{
  int hap=0, rep=0, ans=0;
  int h, nr, i,j, n=0;
  int mh, nh, th, mi, ni, nocl, nopre, p, c, ovful;
  int hd[20];

  for (n=0; 1; ++n)
  {
    nr=th=nopre=nocl=0;
    memset(hd,0,sizeof hd);

    for (i=0; i<num_student; ++i)
    {
      h = student[i].happiness;
      for (j=0; j<num_topic; ++j)
        nr += (student[i].seen[j] > 1);
      th += h;
      if (!i || mh <= h) { mh = h; mi = i; }
      if (!i || nh >= h) { nh = h; ni = i; }
      hd[h<20?h:19]++;

      //  randomize the permutation (ordering) of students

      j = Random(num_student - i) + i;
      h = perm[j]; perm[j] = perm[i]; perm[i] = h;   // swap

      //  check for missing class or missing prereq

      for (p=0; p<num_period; ++p)
      {
        c = student[i].enroll[p];
        if (!c)
          ++nocl;
        else if ((h = period[p].prec[c]) &&
                 student[i].enroll[period[p].prep[c]] != h)
          ++nopre;
      }
    }
    //  check for overfilled classes

    ovful = 0;
    for (p=0; p<num_period; ++p)
      for (c=0; c<max_class; ++c)
        if (period[p].size[c]<0)
          ++ovful;

    if (debug)
    {
      printf("average happiness = %g \n", (double) th / num_student);
      if (debug>1)
      {
        printf("minimum happiness = %d  (%s)\n", nh, student[ni].name);
        printf("maximum happiness = %d  (%s)\n", mh, student[mi].name);
        printf("happiness distrib =");
        for (j=nh;j<=mh&&j<20;++j) printf(" %d",hd[j]);
        printf("\n");
      }
      printf("number of repeats = %d \n", nr);
      printf("number non assign = %d \n", nocl);
      printf("number non prereq = %d \n", nopre);
      printf("number overfilled = %d \n", ovful);
    }

    ++rep;

    if (nr==0 && th >= hap)    // hap is max happiness so far
    {
      if (th==hap) ++ans;
      hap = th;
      if (rep > 4 || ans > 4)
        break;
      rep = 0;
    }

    if (n > swlim)
      break;

    if (debug)
      printf("\nSwapping.... pass %d\n",n);

    SearchAndSwap();
  }
}

//----------------------------------------------------------------------------
//  write the completed schedule

void WriteOutput(char *filename)
{
  int t,c,i,p;
  int nc=0, tc=0;
  int th=0, ov=0, mp=0;
  FILE *f;

  if (!strcmp(filename,"stdout"))
    f = stdout;
  else
    f = fopen(filename, "w");

  if (export)
  {
    for (i=0; i<num_student; ++i)
    {
      printf("\"%s\"",student[i].name);
      for (p=0; p<num_period; ++p)
        printf(" %d",student[i].enroll[p]);
      printf("\n");
    }
    if (strcmp(filename,"stdout"))
      fclose(f);

    return;                                    /*  RETURN -- FINISHED */
  }

  printf("\n======================================\n");
  printf("   STUDENT LIST\n");
  printf("======================================\n\n");

  for (i=0; i<num_student; ++i)
  {
    printf(student[i].name);
    if (debug>1)
      printf("  (%d)  %d", student[i].happiness, student[i].num_enroll);
    printf("\n");

    th += student[i].happiness;

    for (p=0; p<num_period; ++p)
    {
      c = student[i].enroll[p];
      t = period[p].topic[c];

      if (c==0)
        printf("*   NO CLASS\n", ++nc);
      else
      {
        printf((student[i].seen[t] > 1 ||
                period[p].prec[c] && student[i].enroll[period[p].prep[c]]!=
                period[p].prec[c] && ++mp) ? "*\t" : "\t");

        if (debug>1)
          printf("(%d) ", student[i].pref[t]);

        printf("%s", period[p].name);

        printf("\t%s", topic[t].name);

        if (period[p].room[c])
          printf("\t%d", period[p].room[c]);
        printf("\n");
      }
    }
    printf("\n");
  }

  printf("\n======================================\n");
  printf("   CLASSES LIST\n");
  printf("======================================\n\n");

  for (p=0; p<num_period; ++p)
  {
    for (c=1; c<max_class; ++c)
    {
      t = period[p].topic[c];
      if (t != -1)
      {
        printf("%s - ", period[p].name);
        if (period[p].room[c])
          printf("Room %d - ", period[p].room[c]);
        printf(topic[t].name);
        if (debug)
          printf("  (%d of %d filled)", period[p].cap[c]-period[p].size[c], period[p].cap[c]);
        printf("\n");
        if (period[p].size[c] < 0)
          ++ov;

        for (i=0; i<num_student; ++i)
          if (student[i].enroll[p] == c)
          {
            printf(student[i].seen[t] > 1 && ++tc ? "*\t" : "\t");
            if (debug>1)
              printf("(%d) ",student[i].pref[t]);
            printf("%s\n", student[i].name);
          }
        printf("\n");
      }
    }
  }
  if (debug)
  {
    printf("\nNumber of missing assignments: %d\n", nc);
    printf( "Number of repeated topics:     %d\n", (tc + 1)/2);
    printf( "Number of overfilled classes:  %d\n", ov);
    printf( "Number of missed prereqs:      %d\n", mp);
    if (debug>1)
    printf( "Total happiness:               %d\n", th);
    if (debug>1)
    printf( "Average happiness:             %g\n", (double)th/num_student);
  }
  if (strcmp(filename,"stdout"))
    fclose(f);
}

//----------------------------------------------------------------------------

int main(int argc, char* argv[])
{
  int i,r;
  char *fn="ypSched.dat";

  for (i=1; i<argc; ++i)
    if (argv[i][0]!='-')
      fn = argv[i];
    else
      switch (argv[i][1])
      {
      case 'h': case '?':
        printf("Parameters:\n");
        printf("  datafilename (default ypsched.dat)\n");
        printf("  -h    help\n");
        printf("  -r1   set random seed\n");
        printf("  -w5   set flexibility weight\n");
        printf("  -o100 max optimization passes\n");
        printf("  -p    prevent repeat topic\n");
        printf("  -q    quick optimizations only\n");
        printf("  -u    do not try to distribute evenly\n");
        printf("  -d1   debug level 0,1,2,3\n");
        printf("  -x    database output (implies -d0)\n");
        printf("\nFor best results don't use any options at first.\n");
        printf("Use -d0 or -x to produce final clean output.\n");
        return 0;
      case 'w':
        sscanf(argv[i]+2,"%lf",&w1);
        break;
      case 'o':
        sscanf(argv[i]+2,"%d",&swlim);
        break;
      case 'p':
        prevent_repeat = 1;
        break;
      case 'd':
        sscanf(argv[i]+2,"%d",&debug);
        break;
      case 'q':
        quick = 1;
        break;
      case 'u':
        evenly = 0;
        break;
      case 'x':
        export = 1;
        debug = 0;
        break;
      case 'r':
        sscanf(argv[i]+2,"%d",&r);
        srand(r);
        printf("First rand = %d\n",rand());
        break;
      default:
        printf("Unknown option ignored '%s'\n",argv[i]);
      }

  if (debug)
  {
    printf("Year-end conference scheduling tool\n");

    printf("======================================\n");
    printf("Reading data file\n");
  }

  ReadFile(fn);

  FinishInit();

  if (debug)
  {
    printf("======================================\n");
    printf("First pass assignment\n");
  }

  if (!num_student)
    printf("You must have at least one student.\n");
  else if (!num_topic)
    printf("You must have at least one topic.\n");
  else if (!num_period)
    printf("You must have at least one period.\n");
  else if (max_class<2)
    printf("You must have at least one classroom per period.\n");
  else
  {
    Assignment(num_period);

    Optimizer();

    WriteOutput("stdout");
  }

  return 0;
}