/*****************************************************************************/
/*                                                                           */
/*  tteval.c                                                                 */
/*  Jeffrey H. Kingston                                                      */
/*  22 July 2003                                                             */
/*                                                                           */
/*  This program reads and checks a tutor allocation problem instance and    */
/*  optionally a solution as well.  If there is something wrong it prints    */
/*  an error message and exits with status 1.  If there are no problems it   */
/*  either exits silently (when checking an instance) or prints an           */
/*  evaluation (when checking a solution).                                   */
/*                                                                           */
/*  See PrintUsageAndExit just below for usage information.                  */
/*                                                                           */
/*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <time.h>


/*****************************************************************************/
/*                                                                           */
/*  Instance path and log file - where the program goes to find its          */
/*  instances, and log its evaluations, when the -s flag is set.             */
/*                                                                           */
/*****************************************************************************/

#define	INSTANCE_PATH	"/usr/staff/jeff/tteval"
#define	LOG_FILE	"/usr/staff/jeff/tteval/tteval_log"


/*****************************************************************************/
/*                                                                           */
/*  void PrintUsageAndExit(FILE *fp)                                         */
/*                                                                           */
/*  Print tteval usage and exit.                                             */
/*                                                                           */
/*****************************************************************************/

void PrintUsageAndExit(FILE *fp)
{
  fprintf(fp, "usage:  tteval [ options ] [ filename ]\n");
  fprintf(fp, "\n");
  fprintf(fp, "-s        If evaluation is successful, submit it for logging\n");
  fprintf(fp, "-u        Print this usage message and exit\n");
  fprintf(fp, "-r<seed>  Print random solution to instance; seed optional\n");
  fprintf(fp, "\n");
  fprintf(fp, "-v1       Minimal verbosity (final score only) - the default\n");
  fprintf(fp, "-v2       Moderate verbosity\n");
  fprintf(fp, "-v3       Maximal verbosity (every defect will be listed)\n");
  fprintf(fp, "\n");
  fprintf(fp, "Filename may be an instance file, which will be checked,\n");
  fprintf(fp, "or it may be a solution file, which will be evaluated.\n");
  fprintf(fp, "If filename is not given, stdin is used.\n");
  fprintf(fp, "\n");
  fprintf(fp, "By default, the instance file named in the solution file\n");
  fprintf(fp, "is searched for in the current directory.  But when -s is\n");
  fprintf(fp, "used, the instance file is searched for in a standard\n");
  fprintf(fp, "place (%s) only, for reliable certification.\n", INSTANCE_PATH);
  exit(1);
}

/*****************************************************************************/
/*                                                                           */
/*  Compile time limits - all are checked and may be freely increased.       */
/*                                                                           */
/*****************************************************************************/

#define	MAX_LINE	 200		/* maximum length of an input line   */
#define MAX_TIMES	 100		/* maximum number of times in week   */
#define	MAX_UNITS	 100		/* maximum number of units of study  */
#define MAX_TUTORS	 200		/* maximum number of tutors          */
#define	MAX_MEETINGS	1000		/* maximum number of meetings        */


/*****************************************************************************/
/*                                                                           */
/*  Miscellaneous general-purpose stuff                                      */
/*                                                                           */
/*****************************************************************************/

/* formats for defect messages */
#define FMT1	"%-15s %-30s %10s\n"
#define FMT2	"%-15s %-35s %5d\n"
#define FMT3	"%-15s %-30s %5d\n"

#define	BOOLEAN		unsigned
#define	FALSE		0
#define	TRUE		1

#define GetMemory(var, type) (var) = (type) malloc(sizeof(*(var)))

char *save_string(char *str)
{
  char *res = malloc((strlen(str) + 1) * sizeof(char));
  strcpy(res, str);
  return res;
}

BOOLEAN is_punct(char ch)
{
  char *p;
  char *punct = "!\"#$%&'()*+,./:;<=>?[\\]^`{|}~";  /* NB "-_" allowed */
  for( p = punct;  *p != '\0';  p++ )
    if( ch == *p )
      return TRUE;
  return FALSE;
}

void check_punctuation(char *str, char *file_name, int line_num)
{
  int i, len;
  len = strlen(str);
  for( i = 0; i < len;  i++ )
    if( str[i] < ' ' || str[i] > '~' || is_punct(str[i]) )
    {
      fprintf(stderr, "file %s, line %d: punctuation character in header\n",
	file_name, line_num);
      exit(1);
    }
}

void error(char *file_name, int line_num, char *message)
{
  fprintf(stderr, "file %s, line %d: %s\n", file_name, line_num, message);
  exit(1);
}


/*****************************************************************************/
/*                                                                           */
/*  Instance name, solution name, etc.                                       */
/*                                                                           */
/*****************************************************************************/

char	instance_name[MAX_LINE];	/* name of instance                  */
char	solution_name[MAX_LINE];	/* name of solution                  */
char	author_name[MAX_LINE];		/* name of author		     */
char	method_name[MAX_LINE];		/* name of method		     */


/*****************************************************************************/
/*                                                                           */
/*  Entity typedefs                                                          */
/*                                                                           */
/*****************************************************************************/

typedef struct thing_rec *THING;
typedef struct time_rec *TIME;
typedef struct unit_rec *UNIT;
typedef struct tutor_rec *TUTOR;
typedef struct meeting_rec *MEETING;

struct thing_rec {
  int	num;				/* 0 for first defined, 1 for next.. */
  char	*name;				/* name of this thing                */
  int	line_num;			/* line num where declared           */
};

struct time_rec {
  int	num;				/* 0 for first defined, 1 for next.. */
  char	*name;				/* name of this time                 */
  int	line_num;			/* line num where time is declared   */
};

struct unit_rec {
  int	num;				/* 0 for first defined, 1 for next.. */
  char	*name;				/* name of this unit                 */
  int	line_num;			/* line num where unit is declared   */
};

struct tutor_rec {
  int	   num;				/* 0 for first defined, 1 for next.. */
  char	   *name;			/* name of this tutor                */
  int	   line_num;			/* line num where tutor is declared  */
  int	   max_contact_hours;		/* max contact hours of this tutor   */
  BOOLEAN  qualified_for[MAX_UNITS];	/* units qualified for               */
  BOOLEAN  unavailable[MAX_TIMES];	/* unavailable times		     */
  BOOLEAN  preferred[MAX_TIMES];	/* preferred times                   */
  int	   simultaneous[MAX_TIMES];	/* number of simultaneous duties     */
  MEETING  attending[MAX_TIMES];	/* one meeting attending, else NULL  */
  int	   contact_hours;		/* contact hours assigned            */
};

struct meeting_rec {
  int	num;				/* 0 for first defined, 1 for next.. */
  char	*name;				/* name of this meeting              */
  int	line_num;			/* line num where meet. is declared  */
  UNIT	requires_tutor;			/* req tutor qualified for this unit */
  int	hours_attends;			/* number of hours tutor attends     */
  int   time_count;			/* number of times in meeting        */
  TIME	times[MAX_TIMES];		/* meeting times, in 0..time_count-1 */
  TUTOR	tutors[MAX_TIMES];		/* assigned tutors in 0..time_count-1*/
};


/*****************************************************************************/
/*                                                                           */
/*  THING                                                                    */
/*                                                                           */
/*  THING is the abstract supertype of TIME, UNIT, TUTOR, and MEETING.       */
/*                                                                           */
/*  Add()  - Add new_thing to the end of things, fail if overflow.           */
/*  Sort() -  Copy into things_by_name, sort, and check for duplicates.      */
/*  Find() -  Search sorted array for thing, error if not found.             */
/*                                                                           */
/*****************************************************************************/

Add(THING new_thing, THING *things, int *things_count, int max_things,
  char *thing_str, char *file_name, int line_num)
{
  /* make sure we have space for new_thing */
  if( *things_count >= max_things )
  {
    fprintf(stderr, "file %s, line %d: too many %s objects (max is %d)\n",
      file_name, line_num, thing_str, max_things);
    exit(1);
  }

  /* set new_thing's sequence number */
  new_thing->num = *things_count;

  /* add new_thing to unsorted things array */
  things[(*things_count)++] = new_thing;
}

int thingcmp1(THING *thing1, THING *thing2)
{
  return strcmp((*thing1)->name, (*thing2)->name);
}

Sort(THING *things, THING *things_by_name, int things_count, char *file_name)
{
  int i;
  for( i = 0;  i < things_count;  i++ )
    things_by_name[i] = things[i];
  qsort(things_by_name, things_count, sizeof(THING), &thingcmp1);
  for( i = 1;  i < things_count;  i++ )
    if( strcmp(things[i-1]->name, things[i]->name) == 0 )
    {
      fprintf(stderr, "file %s, line %d: duplicate name %s (see line %d)\n",
	file_name, things[i-1]->line_num, things[i-1]->name,
	things[i]->line_num);
      exit(1);
    }
}

int thingcmp2(char *key, THING *thing)
{
  return strcmp(key, (*thing)->name);
}

THING Find(char *str, THING *things_by_name, int things_count,
    char *file_name, int line_num)
{
  void *p = bsearch(str, things_by_name, things_count,sizeof(THING),&thingcmp2);
  if( p == NULL )
  {
    fprintf(stderr, "file %s, line %d: %s unknown\n", file_name, line_num, str);
    exit(1);
  }
  else
    return * (THING *) p;
}


/*****************************************************************************/
/*                                                                           */
/*  TIME                                                                     */
/*                                                                           */
/*  A TIME is a time.                                                        */
/*                                                                           */
/*****************************************************************************/

TIME	times[MAX_TIMES];		/* the times in file order           */
TIME	times_by_name[MAX_TIMES];	/* the times, sorted by name         */
BOOLEAN times_sorted = FALSE;		/* TRUE after times are sorted       */
int	times_count = 0;		/* the number of times               */

TIME TimeNew(char *name, char *file_name, int line_num)
{
  TIME res;
  assert(!times_sorted);
  GetMemory(res, TIME);
  res->name = save_string(name);
  res->line_num = line_num;
  Add((THING) res, (THING *) times, &times_count, MAX_TIMES,
    "time", file_name, line_num);
  return res;
}

void TimeSort(char *file_name)
{
  assert(!times_sorted);
  Sort( (THING *) times, (THING *) times_by_name, times_count, file_name);
  times_sorted = TRUE;
}

TIME TimeFind(char *name, char *file_name, int line_num)
{
  assert(times_sorted);
  return (TIME) Find(name, (THING *) times_by_name, times_count,
    file_name, line_num);
}


/*****************************************************************************/
/*                                                                           */
/*  UNIT                                                                     */
/*                                                                           */
/*  A UNIT is a unit.                                                        */
/*                                                                           */
/*****************************************************************************/

UNIT	units[MAX_UNITS];		/* the units in file order           */
UNIT	units_by_name[MAX_UNITS];	/* the units, sorted by name         */
BOOLEAN units_sorted = FALSE;		/* TRUE after units are sorted       */
int	units_count = 0;		/* the number of units               */

UNIT UnitNew(char *name, char *file_name, int line_num)
{
  UNIT res;
  assert(!units_sorted);
  GetMemory(res, UNIT);
  res->name = save_string(name);
  res->line_num = line_num;
  Add((THING) res, (THING *) units, &units_count, MAX_UNITS,
    "unit", file_name, line_num);
  return res;
}

void UnitSort(char *file_name)
{
  assert(!units_sorted);
  Sort( (THING *) units, (THING *) units_by_name, units_count, file_name);
  units_sorted = TRUE;
}

UNIT UnitFind(char *name, char *file_name, int line_num)
{
  assert(units_sorted);
  return (UNIT) Find(name, (THING *) units_by_name, units_count,
    file_name, line_num);
}


/*****************************************************************************/
/*                                                                           */
/*  TUTOR                                                                    */
/*                                                                           */
/*  A TUTOR is a tutor.                                                      */
/*                                                                           */
/*****************************************************************************/

TUTOR	tutors[MAX_TUTORS];		/* the tutors in file order          */
TUTOR	tutors_by_name[MAX_TUTORS];	/* the tutors, sorted by name        */
BOOLEAN tutors_sorted = FALSE;		/* true after tutors are sorted      */
int	tutors_count = 0;		/* the number of tutors              */


TUTOR TutorNew(char *name, char *file_name, int line_num)
{
  TUTOR res;  int i;
  assert(!tutors_sorted);
  GetMemory(res, TUTOR);
  res->name = save_string(name);
  res->line_num = line_num;
  res->max_contact_hours = -1;
  for( i = 0;  i < MAX_UNITS;  i++ )
    res->qualified_for[i] = FALSE;
  for( i = 0;  i < MAX_TIMES;  i++ )
  {
    res->unavailable[i] = res->preferred[i] = FALSE;
    res->simultaneous[i] = 0;
    res->attending[i] = NULL;
  }
  res->contact_hours = 0;
  Add((THING) res, (THING *) tutors, &tutors_count, MAX_TUTORS,
    "tutor", file_name, line_num);
  return res;
}


void TutorSort(char *file_name)
{
  assert(!tutors_sorted);
  Sort( (THING *) tutors, (THING *) tutors_by_name, tutors_count, file_name);
  tutors_sorted = TRUE;
}


TUTOR TutorFind(char *name, char *file_name, int line_num)
{
  assert(tutors_sorted);
  return (TUTOR) Find(name, (THING *) tutors_by_name, tutors_count,
    file_name, line_num);
}


void TutorAssignMeeting(MEETING meeting, TIME time, TUTOR tutor,
  char *file_name, int line_num)
{
  if( !tutor->qualified_for[meeting->requires_tutor->num] )
    error(file_name, line_num, "tutor not qualified for this meeting");
  if( tutor->attending[time->num] == NULL )
    tutor->attending[time->num] = meeting;
  tutor->simultaneous[time->num]++;
  tutor->contact_hours++;
}


int TutorEvaluateClashes(TUTOR tutor, FILE *fp, int verbosity)
{
  int i, defects, defects_subtotal, badness, badness_subtotal;
  char label[MAX_LINE], message[MAX_LINE];

  sprintf(label, "%s:", tutor->name);
  badness_subtotal = defects_subtotal = 0;
  for( i = 0;  i < times_count;  i++ )
  {
    if( tutor->simultaneous[i] > 1 )
    {
      defects = tutor->simultaneous[i] - 1;
      defects_subtotal += defects;
      badness = defects * 20;
      badness_subtotal += badness;
      if( verbosity >= 3 )
      {
	sprintf(message, "%d %s at time %s", defects,
	  (defects > 1 ? "clashes" : "clash"), times[i]->name);
	fprintf(fp, FMT3, label, message, badness);
      }
    }
  }
  if( verbosity >= 2 && defects_subtotal > 0 )
  {
    sprintf(message, "%d clashes over all times", defects_subtotal);
    fprintf(fp, FMT2, label, message, badness_subtotal);
  }
  return badness_subtotal;
}


int TutorEvaluatePreferred(TUTOR tutor, FILE *fp, int verbosity)
{
  int i, defects, defects_subtotal, badness, badness_subtotal;
  char label[MAX_LINE], message[MAX_LINE];

  sprintf(label, "%s:", tutor->name);
  badness_subtotal = defects_subtotal = 0;
  for( i = 0;  i < times_count;  i++ )
  {
    if( tutor->attending[i] != NULL && !tutor->preferred[i] )
    {
      defects = 1;
      defects_subtotal += defects;
      badness = defects * 1;
      badness_subtotal += badness;
      if( verbosity >= 3 )
      {
	sprintf(message, "used time %s not preferred", times[i]->name);
	fprintf(fp, FMT3, label, message, badness);
      }
    }
  }
  if( verbosity >= 2 && defects_subtotal > 0 )
  {
    sprintf(message, "%d not preferred times altogether", defects_subtotal);
    fprintf(fp, FMT2, label, message, badness_subtotal);
  }
  return badness_subtotal;
}


int TutorEvaluateTotalHours(TUTOR tutor, FILE *fp, int verbosity)
{
  int i, defects_subtotal, badness_subtotal;
  char label[MAX_LINE], message[MAX_LINE];

  sprintf(label, "%s:", tutor->name);
  defects_subtotal = tutor->contact_hours > tutor->max_contact_hours ?
    tutor->contact_hours - tutor->max_contact_hours : 0;
  badness_subtotal = defects_subtotal * 100;
  if( verbosity >= 2 && defects_subtotal > 0 )
  {
    sprintf(message, "%d too many hours allocated", defects_subtotal);
    fprintf(fp, FMT2, label, message, badness_subtotal);
  }
  return badness_subtotal;
}


int TutorEvaluateShortBlocks(TUTOR tutor, FILE *fp, int verbosity)
{
  int i, defects, defects_subtotal, badness, badness_subtotal;
  int start_block, block_length;
  char label[MAX_LINE], message[MAX_LINE];
  enum { InBlock, NotInBlock } state;

  sprintf(label, "%s:", tutor->name);
  state = NotInBlock;
  badness_subtotal = defects_subtotal = 0;
  for( i = 0;  i < times_count + 1;  i++ )
  {
    switch( state )
    {
      case NotInBlock:

	if( i < times_count && tutor->attending[i] != NULL )
	{
	  start_block = i;
	  state = InBlock;
	}
	break;


      case InBlock:

	if( i >= times_count || tutor->attending[i] == NULL )
	{
	  block_length = i - start_block;
	  if( block_length < 3 )
	  {
	    defects = (3 - block_length);
	    badness = defects * 2;
	    defects_subtotal += defects;
	    badness_subtotal += badness;
	    if( verbosity >= 3 )
	    {
	      if( block_length == 1 )
		sprintf(message, "size 1 block %s", times[start_block]->name);
	      else
		sprintf(message, "size %d block %s to %s", block_length,
		  times[start_block]->name, times[i-1]->name);
	      fprintf(fp, FMT3, label, message, badness);
	    }
	  }
	  state = NotInBlock;
	}
	break;

    }
  }
  if( verbosity >= 2 && defects_subtotal > 0 )
  {
    sprintf(message, "%d block defects altogether", defects_subtotal);
    fprintf(fp, FMT2, label, message, badness_subtotal);
  }
  return badness_subtotal;
}


int TutorEvaluate(TUTOR tutor, FILE *fp, int verbosity)
{
  int badness_total = 0;
  badness_total += TutorEvaluateTotalHours(tutor, fp, verbosity);
  badness_total += TutorEvaluateClashes(tutor, fp, verbosity);
  badness_total += TutorEvaluateShortBlocks(tutor, fp, verbosity);
  badness_total += TutorEvaluatePreferred(tutor, fp, verbosity);
  return badness_total;
}


/*****************************************************************************/
/*                                                                           */
/*  MEETING                                                                  */
/*                                                                           */
/*  A MEETING is a meeting.                                                  */
/*                                                                           */
/*****************************************************************************/

MEETING	meetings[MAX_MEETINGS];		/* the meetings in file order        */
MEETING	meetings_by_name[MAX_MEETINGS];	/* the meetings, sorted by name      */
BOOLEAN meetings_sorted = FALSE;	/* true after meetings are sorted    */
int	meetings_count = 0;		/* the number of meetings            */

MEETING MeetingNew(char *name, char *file_name, int line_num)
{
  MEETING res;
  assert(!meetings_sorted);
  GetMemory(res, MEETING);
  res->name = save_string(name);
  res->line_num = line_num;
  res->requires_tutor = NULL;
  res->hours_attends = -1;
  res->time_count = 0;
  Add((THING) res, (THING *) meetings, &meetings_count, MAX_MEETINGS,
    "meeting", file_name, line_num);
  return res;
}

void MeetingSort(char *file_name)
{
  assert(!meetings_sorted);
  Sort( (THING *) meetings, (THING *) meetings_by_name, meetings_count,
    file_name);
  meetings_sorted = TRUE;
}

MEETING MeetingFind(char *name, char *file_name, int line_num)
{
  assert(meetings_sorted);
  return (MEETING) Find(name, (THING *) meetings_by_name, meetings_count,
    file_name, line_num);
}

void MeetingAssignTutor(MEETING meeting, TIME time, TUTOR tutor,
  char *file_name, int line_num)
{
  int i;

  /* assign tutor */
  for( i = 0;  i < meeting->time_count && meeting->times[i] != time;  i++ );
  if( i >= meeting->time_count )
    error(file_name, line_num, "meeting does not occur at given time");
  else if( meeting->tutors[i] != NULL )
    error(file_name, line_num, "meeting already has tutor at given time");
  else
    meeting->tutors[i] = tutor;

  /* ensure meeting is not split between two tutors */
  for( i = 0;  i < meeting->time_count;  i++ )
    if( meeting->tutors[i] != NULL && meeting->tutors[i] != tutor )
      error(file_name, line_num, "meeting previously assigned different tutor");
}

int MeetingEvaluate(MEETING meeting, FILE *fp, int verbosity)
{
  int i, filled_slots, defects, badness;
  char label[MAX_LINE], message[MAX_LINE];

  /* find how many filled slots there are */
  filled_slots = 0;
  for( i = 0;  i < meeting->time_count; i++ )
    if( meeting->tutors[i] != NULL )
      filled_slots++;

  /* find and print the badness of that */
  if( filled_slots < meeting->hours_attends )
  {
    defects = meeting->hours_attends - filled_slots;
    badness = defects * 20;
    sprintf(label, "%s:", meeting->name);
    sprintf(message, "%d %s not assigned", defects,
      defects > 1 ? "hours" : "hour");
    if( verbosity >= 2 )
      fprintf(fp, FMT2, label, message, badness);
  }
  else
    badness = 0;

  /* return the badness */
  return badness;
}

/*****************************************************************************/
/*                                                                           */
/*  void ReadInstance(FILE *fp, char *file_name)                             */
/*                                                                           */
/*  Read a tutor allocation instance from fp (called file_name) and set the  */
/*  times, units, tutors, and meetings arrays to contain it.  Print an error */
/*  message and exit with status 1 if there are any problems with the file.  */
/*                                                                           */
/*  Note: at the moment this is called, the first line, containing the       */
/*  instance name, will have already been read and instance_name assigned.   */
/*  So the first line read by this file is line 2.                           */
/*                                                                           */
/*****************************************************************************/

typedef enum { Outside, Times, Units, Tutor, Meeting, End } INSTANCE_STATE;

void ReadInstance(FILE *fp, char *file_name)
{
  int line_num;  INSTANCE_STATE state;
  char line[MAX_LINE], command[MAX_LINE], value[MAX_LINE];
  TUTOR current_tutor = NULL;
  MEETING current_meeting = NULL;

  /* read each line */
  state = Outside;
  line_num = 1; /* ready for line 2 */
  while( fgets(line, MAX_LINE, fp) )
  {
    /* find ordinary line and read command, the initial keyword */
    line_num++;
    /* fprintf(stderr, "# line %d state %d: %s", line_num, state, line); */
    if( line[0] == '\0' || line[0] == '\n' || line[0] == '#' )
      continue;
    if( sscanf(line, "%s", command) != 1 )
      error(file_name, line_num, "cannot find initial keyword");

    switch( state )
    {
      case Outside:

	/* we are outside any major construct */
	if( strcmp(command, "begintimes") == 0 )
	  state = Times;
	else if( strcmp(command, "beginunits") == 0 )
	  state = Units;
	else if( strcmp(command, "begintutor") == 0 )
	{
	  if( sscanf(line, "%s %s\n", command, value) != 2 )
	    error(file_name, line_num, "tutor name missing");
	  current_tutor = TutorNew(value, file_name, line_num);
	  state = Tutor;
	}
	else if( strcmp(command, "beginmeeting") == 0 )
	{
	  if( sscanf(line, "%s %s\n", command, value) != 2 )
	    error(file_name, line_num, "meeting name missing");
	  current_meeting = MeetingNew(value, file_name, line_num);
	  state = Meeting;
	}
	else if( strcmp(command, "endinstance") == 0 )
	{
	  if( sscanf(line, "%s %s\n", command, value) != 2 )
	    error(file_name, line_num, "instance name missing");
	  if( strcmp(instance_name, value) != 0 )
	    error(file_name, line_num, "instance name disagrees with previous");
	  TutorSort(file_name);
	  MeetingSort(file_name);
	  state = End;
	}
	else
	  error(file_name, line_num, "expected begin, or endinstance");
	break;


      case Times:

	/* we are between begintimes and endtimes */
	if( strcmp(command, "time") == 0 )
	{
	  if( sscanf(line, "%s %s\n", command, value) != 2 )
	    error(file_name, line_num, "time name missing");
	  TimeNew(value, file_name, line_num);
	}
	else if( strcmp(command, "endtimes") == 0 )
	{
	  TimeSort(file_name);
	  state = Outside;
	}
	else
	  error(file_name, line_num, "expected time or endtimes here");
	break;


      case Units:

	/* we are between beginunits and endunits */
	if( strcmp(command, "unit") == 0 )
	{
	  if( sscanf(line, "%s %s\n", command, value) != 2 )
	    error(file_name, line_num, "unit name missing");
	  UnitNew(value, file_name, line_num);
	}
	else if( strcmp(command, "endunits") == 0 )
	{
	  UnitSort(file_name);
	  state = Outside;
	}
	else
	  error(file_name, line_num, "expected unit or endunits here");
	break;


      case Tutor:

	/* we are between begintutor and endtutor */
	if( strcmp(command, "maxcontacthours") == 0 )
	{
	  if( sscanf(line, "%s %d", command,
	      &current_tutor->max_contact_hours) != 2 )
	    error(file_name, line_num, "cannot read maxcontacthours\n");
	}
	else if( strcmp(command, "qualifiedfor") == 0 )
	{
	  UNIT unit;
	  if( sscanf(line,"%s %s", command, value) !=2 )
	    error(file_name, line_num, "cannot read qualifiedfor\n");
	  unit = UnitFind(value, file_name, line_num);
	  current_tutor->qualified_for[unit->num] = TRUE;
	}
	else if( strcmp(command, "unavailable") == 0 )
	{
	  TIME time;
	  if( sscanf(line,"%s %s", command, value) !=2 )
	    error(file_name, line_num, "cannot read unavailable\n");
	  time = TimeFind(value, file_name, line_num);
	  current_tutor->unavailable[time->num] = TRUE;
	  current_tutor->simultaneous[time->num]++;
	}
	else if( strcmp(command, "preferred") == 0 )
	{
	  TIME time;
	  if( sscanf(line,"%s %s", command, value) !=2 )
	    error(file_name, line_num, "cannot read preferred\n");
	  time = TimeFind(value, file_name, line_num);
	  current_tutor->preferred[time->num] = TRUE;
	}
	else if( strcmp(command, "endtutor") == 0 )
	{
	  if( current_tutor->max_contact_hours == -1 )
	    error(file_name, line_num, "missing maxcontacthours");
	  state = Outside;
	}
	else
	  error(file_name, line_num, "expected tutor option or endtutor here");
	break;


      case Meeting:

	/* we are between beginmeeting and endmeeting */
	if( strcmp(command, "requirestutor") == 0 )
	{
	  UNIT unit;
	  if( current_meeting->requires_tutor != NULL )
	    error(file_name, line_num, "requirestutor twice in one meeting");
	  if( sscanf(line,"%s %s", command, value) != 2 )
	    error(file_name, line_num, "cannot read requirestutor\n");
	  unit = UnitFind(value, file_name, line_num);
	  current_meeting->requires_tutor = unit;
	}
	else if( strcmp(command, "hourstutorattends") == 0 )
	{
	  if( current_meeting->hours_attends != -1 )
	    error(file_name, line_num, "hoursattends twice in one meeting");
	  if( sscanf(line, "%s %d", command,
	      &current_meeting->hours_attends) != 2 )
	    error(file_name, line_num, "cannot read hoursattends\n");
	}
	else if( strcmp(command, "time") == 0 )
	{
	  TIME time;
	  if( sscanf(line,"%s %s", command, value) != 2 )
	    error(file_name, line_num, "cannot read meeting time\n");
	  time = TimeFind(value, file_name, line_num);
	  current_meeting->tutors[current_meeting->time_count] = NULL;
	  current_meeting->times[current_meeting->time_count++] = time;
	}
	else if( strcmp(command, "endmeeting") == 0 )
	{
	  if( current_meeting->requires_tutor == NULL )
	    error(file_name, current_meeting->line_num,"missing requirestutor");
	  if( current_meeting->time_count == 0  )
	    error(file_name, current_meeting->line_num, "meeting has no times");
	  if( current_meeting->hours_attends == -1 )
	    current_meeting->hours_attends = current_meeting->time_count;
	  if( current_meeting->hours_attends > current_meeting->time_count )
	    error(file_name, current_meeting->line_num,"oversize hoursattends");
	  state = Outside;
	}
	else
	  error(file_name, line_num,
	    "expected meeting option or endmeeting here");
	break;


      case End:

	error(file_name, line_num, "file should have ended with previous line");
	break;

    }
  }
  if( state != End )
  {
    fprintf(stderr, "file %s, line %d: file ends unexpectedly\n",
      file_name, line_num);
    exit(1);
  }
}


/*****************************************************************************/
/*                                                                           */
/*  EchoInstance(FILE *fp)                                                   */
/*                                                                           */
/*  Print instance to fp.                                                    */
/*                                                                           */
/*****************************************************************************/

void EchoTutor(TUTOR t, FILE *fp)
{
  int i;

  /* print tutor name and contact hours */
  fprintf(fp, "begintutor %s\n", t->name);
  fprintf(fp, "maxcontacthours %d\n", t->max_contact_hours);

  /* print units qualified for */
  for( i = 0;  i < units_count;  i++ )
    if( t->qualified_for[i] )
      fprintf(fp, "qualifiedfor %s\n", units[i]->name);

  /* print unavailable times */
  for( i = 0;  i < times_count;  i++ )
    if( t->unavailable[i] )
      fprintf(fp, "unavailable %s\n", times[i]->name);

  /* print preferred times */
  for( i = 0;  i < times_count;  i++ )
    if( t->preferred[i] )
      fprintf(fp, "preferred %s\n", times[i]->name);

  /* print footer */
  fprintf(fp, "endtutor %s\n\n", t->name);

}

void EchoMeeting(MEETING m, FILE *fp)
{
  int i;

  /* print meeting name, requires_tutor, hours_attends */
  fprintf(fp, "beginmeeting %s\n", m->name);
  fprintf(fp, "requirestutor %s\n", m->requires_tutor->name);
  fprintf(fp, "hourstutorattends %d\n", m->hours_attends);

  /* print meeting times */
  for( i = 0;  i < m->time_count;  i++ )
    fprintf(fp, "time %s\n", m->times[i]->name);

  /* end meeting */
  fprintf(fp, "endmeeting %s\n\n", m->name);
}

void EchoInstance(FILE *fp)
{
  int i, j;

  /* print instance header */
  fprintf(fp, "begininstance %s\n\n", instance_name);

  /* print times */
  fprintf(fp, "begintimes\n");
  for( i = 0;  i < times_count;  i++ )
    fprintf(fp, "time %s\n", times[i]->name);
  fprintf(fp, "endtimes\n\n");

  /* print units */
  fprintf(fp, "beginunits\n");
  for( i = 0;  i < units_count;  i++ )
    fprintf(fp, "unit %s\n", units[i]->name);
  fprintf(fp, "endunits\n\n");

  /* print tutors */
  for( i = 0;  i < tutors_count;  i++ )
    EchoTutor(tutors[i], fp);

  /* print meetings */
  for( i = 0;  i < meetings_count;  i++ )
    EchoMeeting(meetings[i], fp);

  /* print instance footer */
  fprintf(fp, "endinstance %s\n", instance_name);
}


/*****************************************************************************/
/*                                                                           */
/*  void RandomSolution(unsigned int seed)                                   */
/*                                                                           */
/*  Assign a random solution to the instance.                                */
/*                                                                           */
/*  For each meeting, make 100 random attempts to find a tutor who is        */
/*  qualified for that meeting and would not be overloaded if assigned it.   */
/*  If no such tutor is found within the 100 attempts, leave the meeting     */
/*  If a tutor is found, assign the tutor to the first so many times of the  */
/*  meeting, however many are required.                                      */
/*                                                                           */
/*****************************************************************************/

void RandomSolution(unsigned int seed)
{
  int i, j, k;  MEETING m;  TUTOR tutor;

  /* set random number seed for random() */
  srandom(seed);

  /* set header stuff */
  sprintf(solution_name, "Random%d", seed);
  sprintf(author_name, "Jeff Kingston");
  sprintf(method_name, "Random Qualified Tutor");

  /* examine each meeting */
  for( i = 0;  i < meetings_count;  i++ )
  {
    /* make up to 50 attempts to find a qualified tutor for this meeting */
    m = meetings[i];
    for( j = 0;  j < 100;  j++ )
    {
      tutor = tutors[random() % tutors_count];
      if( tutor->qualified_for[m->requires_tutor->num] &&
	(tutor->max_contact_hours - tutor->contact_hours) >= m->hours_attends )
      {
	/* found qualified tutor, so assign and break */
	for( k = 0;  k < m->hours_attends;  k++ )
	{
	  MeetingAssignTutor(m, m->times[k], tutor, "random", 0);
	  TutorAssignMeeting(m, m->times[k], tutor, "random", 0);
	}
	break;
      }
    }
  }
}


/*****************************************************************************/
/*                                                                           */
/*  void ReadSolution(FILE *fp, char *file_name, BOOLEAN logging)            */
/*                                                                           */
/*  Read solution file fp, named file_name, and evaluate it.                 */
/*  Use logging to decide which instance file to open.                       */
/*                                                                           */
/*  The first line, containing the solution name, has already been read.     */
/*                                                                           */
/*****************************************************************************/

typedef enum { Instance, Author, Method, Assign, SolnEnd } SOLUTION_STATE;

void ReadSolution(FILE *fp, char *file_name, BOOLEAN logging)
{
  int line_num;  int state;  FILE *instance_fp;
  char line[MAX_LINE], command[MAX_LINE], value[MAX_LINE];
  char instance_filename[MAX_LINE];

  /* read each line */
  line_num = 1; /* ready for line 2 */
  state = Instance;
  while( fgets(line, MAX_LINE, fp) )
  {
    /* find ordinary line and read command, the initial keyword */
    line_num++;
    /* fprintf(stderr, "# line %d state %d: %s", line_num, state, line); */
    if( line[0] == '\0' || line[0] == '\n' || line[0] == '#' )
      continue;
    if( sscanf(line, "%s", command) != 1 )
      error(file_name, line_num, "cannot find initial keyword");

    switch( state )
    {
      case Instance:
	
	if( strcmp(command, "instance") == 0 )
	{
	  /* open instance_fp depending on logging */
	  if( sscanf(line, "%s %s", command, value) != 2 )
	    error(file_name, line_num, "cannot find instance file name");
          check_punctuation(value, file_name, line_num);
	  if( logging )
	    sprintf(instance_filename, "%s/%s", INSTANCE_PATH, value);
	  else
	    sprintf(instance_filename, "%s", value);
	  instance_fp = fopen(instance_filename, "r");
	  if( instance_fp == NULL )
	  {
	    fprintf(stderr, "cannot open instance file %s\n",instance_filename);
	    exit(1);
	  }

	  /* read the first line of instance_fp (begininstance, it must be) */
	  if( !fgets(line, MAX_LINE, instance_fp) )
	  {
	    fprintf(stderr, "tteval: cannot read first line of file %s\n",
	      instance_filename);
	    exit(1);
	  }
	  if( sscanf(line, "%s %s", command, value) != 2 )
	  {
	    fprintf(stderr, "tteval: error on first line of file %s\n",
	      instance_filename);
	    exit(1);
	  }
	  if( strcmp(command, "begininstance") != 0 )
	  {
	    fprintf(stderr,
	      "tteval: begininstance missing from first line of file %s\n",
	      instance_filename);
	    exit(1);
	  }
          check_punctuation(value, instance_filename, 1);
	  strcpy(instance_name, value);

	  /* read the rest of the instance */
	  ReadInstance(instance_fp, instance_filename);
	  /* EchoInstance(stdout); */
	  state = Author;
	}
	else
	  error(file_name, line_num, "expected instance line here");
	break;
	

      case Author:
	
	if( strcmp(command, "author") == 0 )
	{
	  if( sscanf(line, "%s %[-_ a-zA-Z0-9]", command, value) != 2 )
	    error(file_name, line_num, "cannot find author name");
          check_punctuation(value, file_name, line_num);
	  strcpy(author_name, value);
	  state = Method;
	}
	else
	  error(file_name, line_num, "expected author line here");
	break;

	
      case Method:
	
	if( strcmp(command, "method") == 0 )
	{
	  if( sscanf(line, "%s %[-_ a-zA-Z0-9]", command, value) != 2 )
	    error(file_name, line_num, "cannot find method name");
          check_punctuation(value, file_name, line_num);
	  strcpy(method_name, value);
	  state = Assign;
	}
	else
	  error(file_name, line_num, "expected method line here");
	break;
	

      case Assign:
	
	if( strcmp(command, "assign") == 0 )
	{
	  char meeting_name[MAX_LINE],time_name[MAX_LINE],tutor_name[MAX_LINE];
	  MEETING meeting;  TIME time;  TUTOR tutor;
	  if( sscanf(line, "%s %s %s %s", command, meeting_name, time_name,
		tutor_name) != 4 )
	    error(file_name, line_num, "syntax error in assign line");
	  meeting = MeetingFind(meeting_name, file_name, line_num);
	  time = TimeFind(time_name, file_name, line_num);
	  tutor = TutorFind(tutor_name, file_name, line_num);
	  MeetingAssignTutor(meeting, time, tutor, file_name, line_num);
	  TutorAssignMeeting(meeting, time, tutor, file_name, line_num);
	}
	else if( strcmp(command, "endsolution") == 0 )
	{
	  if( sscanf(line, "%s %s", command, value) != 2 )
	    error(file_name, line_num, "cannot find closing solution name");
	  if( strcmp(value, solution_name) != 0 )
	    error(file_name, line_num, "unexpected closing solution name");
	  state = SolnEnd;
	}
	else
	  error(file_name, line_num, "expected method line here");
	break;
	

      case SolnEnd:
       
	error(file_name, line_num, "file should have ended with previous line");
	break;
    }
  }

  /* make sure file ended gracefully */
  if( state != SolnEnd )
    error(file_name, line_num, "missing endsolution line");
}


/*****************************************************************************/
/*                                                                           */
/*  void EchoSolution(FILE *fp)                                              */
/*                                                                           */
/*  Echo solution onto fp.                                                   */
/*                                                                           */
/*****************************************************************************/

void EchoSolution(FILE *fp)
{
  int i, j;

  /* header lines */
  fprintf(fp, "beginsolution %s\n", solution_name);
  fprintf(fp, "instance %s\n", instance_name);
  fprintf(fp, "author %s\n", author_name);
  fprintf(fp, "method %s\n", method_name);
  fprintf(fp, "\n");

  /* assign lines */
  for( i = 0;  i < meetings_count;  i++ )
  {
    for( j = 0;  j < meetings[i]->time_count;  j++ )
    {
      if( meetings[i]->tutors[j] != NULL )
      {
	fprintf(fp, "assign %s", meetings[i]->name);
	fprintf(fp, " %s", meetings[i]->times[j]->name);
	fprintf(fp, " %s\n", meetings[i]->tutors[j]->name);
      }
      /* *** it's working, don't really need this
      else
	fprintf(fp, "# not assigned: %s %s\n", meetings[i]->name,
	  meetings[i]->times[j]->name);
      *** */
    }
  }


  /* footer lines */
  fprintf(fp, "\n");
  fprintf(fp, "endsolution %s\n", solution_name);
}


/*****************************************************************************/
/*                                                                           */
/*  int EvaluateSolution(int verbosity, FILE *fp)                            */
/*                                                                           */
/*  Evaluate solution, printing report on fp.  Return final score as result. */
/*                                                                           */
/*****************************************************************************/

int EvaluateSolution(int verbosity, FILE *fp)
{
  int i, badness = 0;

  /* header line if verbose */
  if( verbosity > 1 )
  {
    fprintf(fp, FMT1, "Entity", "Number and kind of defect", "Badness");
    fprintf(fp, "---------------------------------------------------------\n");
  }

  /* evaluate tutors */
  for( i = 0;  i < tutors_count;  i++ )
    badness += TutorEvaluate(tutors[i], fp, verbosity);

  /* evaluate meetings */
  for( i = 0;  i < meetings_count;  i++ )
    badness += MeetingEvaluate(meetings[i], fp, verbosity);

  /* closing line if verbose */
  if( verbosity > 1 )
  {
    fprintf(fp, "---------------------------------------------------------\n");
    fprintf(fp, FMT2, "Total Badness", "", badness);
  }
  else
    fprintf(fp, "%d\n", badness);

  return badness;
}


/*****************************************************************************/
/*                                                                           */
/*  char *Today()                                                            */
/*                                                                           */
/*  A string representing today's date.                                      */
/*                                                                           */
/*****************************************************************************/

char *Today()
{
  static char time_str[20];
  time_t curr_time;  struct tm *t;  char day_str[4], mon_str[4];

  time(&curr_time);
  t = localtime(&curr_time);
  sprintf(day_str, "%s%d", t->tm_mday < 10 ? "0" : "", t->tm_mday);
  sprintf(mon_str, "%s%d", t->tm_mon + 1 < 10 ? "0" : "", t->tm_mon + 1);
  sprintf(time_str, "%d/%s/%s", t->tm_year + 1900, mon_str, day_str);
  return time_str;
}


/*****************************************************************************/
/*                                                                           */
/*  main(argc, argv)                                                         */
/*                                                                           */
/*****************************************************************************/

main(int argc, char *argv[])
{
  char line[MAX_LINE], command[MAX_LINE], value[MAX_LINE];
  FILE *fp, *log_fp;
  char *file_name = NULL;
  BOOLEAN logging = FALSE;
  BOOLEAN random_soln = FALSE;
  unsigned int random_seed = 314159;
  int score, i, verbosity = 0;

  /* read options */
  for( i = 1;  i < argc;  i++ )
  {
    if( argv[i][0] == '-' )
    {
      switch( argv[i][1] )
      {
	case 'v':

	  /* -v1, -v2, -v3: set verbosity level */
	  if( verbosity != 0 )
	  {
	    fprintf(stderr, "tteval: -v flag given twice\n");
	    exit(1);
	  }
	  if( random_soln )
	  {
	    fprintf(stderr, "tteval: -r and -v flags incompatible\n");
	    exit(1);
	  }
	  if( strcmp(&argv[i][2], "1") == 0 )
	    verbosity = 1;
	  else if( strcmp(&argv[i][2], "2") == 0 )
	    verbosity = 2;
	  else if( strcmp(&argv[i][2], "3") == 0 )
	    verbosity = 3;
	  else
	  {
	    fprintf(stderr, "tteval: illegal value for -v flag\n");
	    exit(1);
	  }
	  break;


	case 'r':

	  /* -r: generate random solution */
	  if( logging )
	  {
	    fprintf(stderr, "tteval: -s and -r flags incompatible\n");
	    exit(1);
	  }
	  if( verbosity != 0 )
	  {
	    fprintf(stderr, "tteval: -v and -r flags incompatible\n");
	    exit(1);
	  }
	  random_soln = TRUE;
	  if( argv[i][2] != '\0' && sscanf(&argv[i][2], "%d", &random_seed)!=1 )
	  {
	    fprintf(stderr, "tteval: error in seed following -r flag\n");
	    exit(1);
	  }
	  break;


	case 's':

	  /* -s: submit successful solution to log */
	  if( logging )
	  {
	    fprintf(stderr, "tteval: -s flag given twice\n");
	    exit(1);
	  }
	  if( random_soln )
	  {
	    fprintf(stderr, "tteval: -r and -s flags incompatible\n");
	    exit(1);
	  }
	  logging = TRUE;
	  break;


	case 'u':

	  /* -u: print usage */
	  PrintUsageAndExit(stderr);
	  break;


	default:

	  PrintUsageAndExit(stderr);
	  break;
      }
    }
    else
    {
      /* option is a file name */
      if( file_name != NULL )
	PrintUsageAndExit(stderr);
      file_name = argv[i];
    }
  }

  /* open the file */
  if( file_name == NULL )
  {
    fp = stdin;
    file_name = "stdin";
  }
  else
  {
    fp = fopen(file_name, "r");
    if( fp == NULL )
    {
      fprintf(stderr, "tteval: cannot open file %s\n", file_name);
      exit(1);
    }
  }

  /* read the first line (begininstance or beginsolution) */
  if( !fgets(line, MAX_LINE, fp) )
  {
    fprintf(stderr, "tteval: cannot read first line of file %s\n", file_name);
    exit(1);
  }

  /* read begininstance <instance_name> or beginsolution <solution_name> */
  if( sscanf(line, "%s %s", command, value) != 2 )
  {
    fprintf(stderr, "tteval: error on first line of file %s\n", file_name);
    exit(1);
  }

  /* handle instance or solution */
  if( strcmp(command, "begininstance") == 0 )
  {
    /* file is an instance file; check consistency with command line options */
    if( logging )
    {
      fprintf(stderr, "tteval: have instance file only, -s does not apply\n");
      exit(1);
    }
    if( verbosity > 0 )
    {
      fprintf(stderr, "tteval: have instance file only, -v does not apply\n");
      exit(1);
    }

    /* save instance_name and read instance */
    check_punctuation(value, file_name, 1);
    strcpy(instance_name, value);
    ReadInstance(fp, file_name);
    /* EchoInstance(stdout); */

    /* print random solution if that's what's wanted */
    if( random_soln )
    {
      RandomSolution(random_seed);
      EchoSolution(stdout);
    }
  }
  else if( strcmp(command, "beginsolution") == 0 )
  {
    /* file is a solution file; check consistency with command line options */
    if( random_soln )
    {
      fprintf(stderr, "tteval: have solution file, -r does not apply\n");
      exit(1);
    }
    if( verbosity == 0 )
      verbosity = 1;

    /* save solution_name and read solution */
    check_punctuation(value, file_name, 1);
    strcpy(solution_name, value);
    ReadSolution(fp, file_name, logging);

    /* now get score */
    score = EvaluateSolution(verbosity, stderr);

    /* now log if that is required */
    if( logging )
    {
      log_fp = fopen(LOG_FILE, "a");
      if( log_fp == NULL )
      {
	fprintf(stderr, "cannot append to log file %s\n", LOG_FILE);
	exit(1);
      }
      fprintf(log_fp, "%s::%s::%s::%s::%s::%s::%d\n", Today(), solution_name,
	instance_name, author_name, method_name, getlogin(), score);
    }
  }
  else
  {
    fprintf(stderr,
      "tteval: begininstance or beginsolution missing from file %s\n",
      file_name);
    exit(1);
  }
}