hamster.c

数据挖掘中de一个算法 hamster的实例

/*----------------------------------------------------------------------
  File    : hamster.c
  Contents: main program for hamster (Unix command line version)
  Author  : Christian Borgelt
  History : 03.01.1997 file created
            08.03.1999 `#include <sys/types.h>' added
            27.03.1999 check of running time added
----------------------------------------------------------------------*/
#define _POSIX_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <limits.h>
#include <time.h>
#include <sys/types.h>
#include <sys/times.h>
#include <unistd.h>
#include <signal.h>
#include "server.h"

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define BDPENALTY  1000         /* penalty for program breakdown */
#define TIMELIMIT   600         /* max. computation time in seconds */

/* --- error codes --- */
#define OK            0         /* no error */
#define E_NONE        0         /* no error */
#define E_NOMEM     (-1)        /* not enough memory */
#define E_FOPEN     (-2)        /* file open failed */
#define E_FREAD     (-3)        /* file read failed */
#define E_FWRITE    (-4)        /* file write failed */
#define E_OPTION    (-5)        /* illegal option */
#define E_OPTARG    (-6)        /* missing option argument */
#define E_ARGCNT    (-7)        /* wrong number of arguments */
#define E_POPEN     (-8)        /* pipe open failed */
#define E_PREAD     (-9)        /* pipe read failed */
#define E_PWRITE   (-10)        /* pipe write failed */
#define E_PBROKEN  (-11)        /* broken pipe */
#define E_FORK     (-12)        /* cannot fork child process */
#define E_EXEC     (-13)        /* cannot execute program */
#define E_TIME     (-14)        /* time limit exceeded */
#define E_UNKNOWN  (-15)        /* unknown error */

/*----------------------------------------------------------------------
  Constants
----------------------------------------------------------------------*/
const char *errmsgs[] = {       /* error messages */
  /* E_NONE      0 */  "no error\n",
  /* E_NOMEM    -1 */  "not enough memory\n",
  /* E_FOPEN    -2 */  "cannot open file `%s'\n",
  /* E_FREAD    -3 */  "read error on file `%s'\n",
  /* E_FWRITE   -4 */  "write error on file `%s'\n",
  /* E_OPTION   -5 */  "unknown option -%c\n",
  /* E_OPTARG   -6 */  "missing option argument\n",
  /* E_ARGCNT   -7 */  "wrong number of arguments\n",
  /* E_POPEN    -8 */  "cannot open pipe\n",
  /* E_PREAD    -9 */  "read error on pipe\n",
  /* E_PWRITE  -10 */  "write error on pipe\n",
  /* E_PBROKEN -11 */  "broken pipe\n",
  /* E_FORK    -12 */  "cannot fork child process\n",
  /* E_EXEC    -13 */  "cannot execute program `%s'\n",
  /* E_UNKNOWN -14 */  "time limit exceeded\n",
  /* E_UNKNOWN -15 */  "unknown error\n"
};

/*----------------------------------------------------------------------
  Global Variables
----------------------------------------------------------------------*/
static char    *prgname;        /* program name for error messages */
static pid_t   pid = -1;        /* child process identifier */
static FILE    *p_in;           /* input  pipe (to be read from) */
static FILE    *p_out;          /* output pipe (to be written to) */
static char    *fn_maze = NULL; /* name of maze file */
static char    *fn_prog = NULL; /* name of hamster program */
static MAZE    *maze    = NULL; /* maze the hamster is in */
static HAMSTER *hamsters[1] = { /* the hamsters */
                 NULL };        /* (currently at most one) */

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

static void error (int code, ...)
{                               /* --- print error message */
  va_list    args;              /* list of variable arguments */
  const char *msg;              /* buffer for error message */

  if ((code > 0) || (code < E_UNKNOWN))
    code = E_UNKNOWN;           /* check error code */
  msg = errmsgs[-code];         /* get error message */
  if (!msg) msg = errmsgs[-E_UNKNOWN];
  fprintf(stderr, "\n%s: ", prgname);  /* print program name */
  va_start(args, code);         /* get variable arguments */
  vfprintf(stderr, msg, args);  /* print error message */
  va_end(args);                 /* end variable argument evaluation */
  exit(code);                   /* abort programm */
}  /* error() */

/*--------------------------------------------------------------------*/

static void stop (int errcode)
{                               /* --- stop hamster process */
  int score;                    /* score achieved */

  kill(pid, SIGKILL);           /* kill child process */
  fclose(p_in); fclose(p_out);  /* and close both pipes */
  if (hamsters[0])              /* get hamster score */
    score = hms_score(hamsters[0]);
  if (errcode == E_NONE) printf("done.\n");
  else                   printf("aborted.\n");
  if (hamsters[0]) {            /* if a hamster exists */
    printf("corncnt: %d\n", hms_corncnt(hamsters[0]));
    printf("movecnt: %d\n", hms_movecnt(hamsters[0]));
    printf("crshcnt: %d\n", hms_crshcnt(hamsters[0]));
    score = hms_score(hamsters[0]);
    if (errcode == E_NONE)      /* if correct program termination */
      printf("score  : %d\n", score);
    else {                      /* if breakdown occured */
      score = (score < INT_MIN +BDPENALTY)
            ? INT_MIN : (score -BDPENALTY);
      printf("score  : *%d\n", score);
    }                           /* subtract breakdown penalty */
    hms_delete(hamsters[0]);    /* print result and */
  }                             /* delete hamster */
  fflush(stdout);               /* flush the output buffer */
  if (errcode != E_NONE) error(errcode, fn_prog);
}  /* stop() */

/*--------------------------------------------------------------------*/

static void start (void)
{                               /* --- start hamster process */
  int     p2c[2];               /* pipe from parent to child */
  int     c2p[2];               /* pipe from child to parent */
  int     fd_out, fd_in;        /* buffers for file descriptors */
  FILE    *file;                /* maze file */
  HAMSTER *hms;                 /* hamster to control */
  char    cmd;                  /* command read */
  int     id = 0;               /* hamster identifier */
  int     arg;                  /* command argument */
  int     x, y;                 /* hamster position */
  time_t  t;                    /* process start time */
 
  /* --- load maze --- */
  printf("reading %s ... ", fn_maze); fflush(stdout);
  file = fopen(fn_maze, "r");   /* open maze file */
  if (!file) error(E_FOPEN, fn_maze);
  maze = mz_load(file);         /* read maze description */
  if (!maze) error(E_FREAD, fn_maze);
  fclose(file);                 /* close maze file */
  printf("done.\n");

  /* --- open pipes and fork child process --- */
  printf("running %s ... ", fn_prog); fflush(stdout);
  if ((pipe(p2c) != 0) || (pipe(c2p) != 0)) {
    error(E_POPEN); return; }   /* create pipes and */
  pid = fork();                 /* fork child process */
  if (pid == -1) { error(E_FORK); return; }

  /* --- child process --- */
  if (pid ==  0) {              /* if this is the child process */
    close(STDOUT_FILENO);       /* connect first  pipe to stdout */
    fd_out = dup2(c2p[1], STDOUT_FILENO);
    close(STDIN_FILENO);        /* connect second pipe to stdin */
    fd_in  = dup2(p2c[0], STDIN_FILENO);
    close(c2p[0]); close(c2p[1]);  /* close pipe handles */
    close(p2c[0]); close(p2c[1]);  /* and check for success */
    if ((fd_out != STDOUT_FILENO) || (fd_in != STDIN_FILENO)) {
      printf("@ 0\n"); fflush(stdout); _exit(-1); }
    execl(fn_prog, fn_prog, NULL);
    printf("@ 1\n"); fflush(stdout); _exit(-1);
  }                             /* execute child program */

  /* --- parent process --- */
  close(p2c[0]); close(c2p[1]); /* if this is the parent process, */
  p_in  = fdopen(c2p[0], "r");  /* close child ends of pipes, */
  p_out = fdopen(p2c[1], "w");  /* open streams on both pipes, */
  if (!p_in || !p_out) {        /* and check for success */
    close(p2c[1]); close(c2p[0]); stop(E_POPEN); return; }
  t = time(NULL);               /* get the start time */

  /* --- process pipe input --- */
  while (1) {                   /* pipe input loop */

    /* -- read command from pipe -- */
    if ( (fscanf(p_in, " %c", &cmd) != 1)
    ||  ((cmd != 'c')
    &&   (fscanf(p_in, " %d", &id)  != 1))
    ||  (((cmd == 't') || (cmd == 'l'))
    &&   (fscanf(p_in, " %d", &arg) != 1))
    ||   (getc(p_in) != '\n')){ /* read next command from pipe */
      stop(feof(p_in) ? E_PBROKEN : E_PREAD); return; }
    if (time(NULL) -t >= TIMELIMIT) {
      stop(E_TIME); return; }   /* check the program running time */

    /* -- evaluate command -- */
    hms = hamsters[0];          /* get hamster to control */
    switch (cmd) {              /* evaluate command read */
      case '@':                 /* --- error in child process */
        stop((id) ? E_EXEC : E_POPEN);
        return;                 /* stop execution */

      case 'c':                 /* --- create hamster */
        if (hms) {              /* if a hamster already exists */
          fprintf(p_out, "c -1\n");
          break;                /* deny creation request and */
        }                       /* abort command evaluation */
        hamsters[0] = hms = hms_create(maze, 0, HMS_EAST, (DISPFN)0);
        if (!hms) { stop(E_NOMEM); return; }
        hms_pos(hms, &x, &y);   /* get hamster position */
        fprintf(p_out, "c %d %d %d %d %d %d %d\n",
          hms_id(hms), x, y, hms_dir(hms), hms_look(hms),
          hms_corn(hms), hms_load(hms));
        break;                  /* send hamster data */

      case 'd':                 /* --- delete hamster */
        fprintf(p_out,"d 0\n"); /* echo delete command, */
        fflush(p_out);          /* flush pipe buffer */
        stop(E_NONE); return;   /* and stop execution */

      case 'm':                 /* --- move hamster */
        hms_move(hms);          /* move hamster forward */
        hms_pos(hms, &x, &y);   /* and get new position */
        fprintf(p_out, "m %d %d %d %d %d\n",
          hms_id(hms), x, y, hms_look(hms), hms_corn(hms));
        break;                  /* reply with new hamster data */

      case 't':                 /* --- turn hamster */
        hms_turn(hms, arg);     /* turn hamster around */
        fprintf(p_out, "t %d %d %d\n",
          hms_id(hms), hms_dir(hms), hms_look(hms));
        break;                  /* reply with new hamster data */

      case 'l':                 /* --- take/drop corn */
        hms_take(hms, arg);     /* take/drop some corn */
        fprintf(p_out, "l %d %d %d\n",
          hms_id(hms), hms_corn(hms), hms_load(hms));
        break;                  /* send new hamster data */

      default:                  /* --- unknown command */
        stop(E_PREAD); return;  /* stop execution */
    }
    fflush(p_out);              /* flush pipe buffer */
  }  /* while (1) .. */
}  /* start() */

/*--------------------------------------------------------------------*/

int main (int argc, char *argv[])
{                               /* --- main function */
  int  i, k = 0;                /* loop variables, counters */
  char *s;                      /* to traverse options */
  char **optarg = NULL;         /* option argument */

  prgname = argv[0];            /* get program name for error msgs. */

  /* --- print startup/usage message --- */
  if (argc > 1) {               /* if arguments given */
    printf("%s - hamster program, command line version", argv[0]);
    fflush(stdout); }           /* print startup message */
  else {                        /* if no argument given */
    printf("usage: %s mazefile prog\n", argv[0]);
    printf("run hamster program `prog' on maze in `mazefile'\n");
    return 0;                   /* print a usage message */
  }                             /* and abort the program */

  /* --- evaluate arguments --- */
  for (i = 1; i < argc; i++) {  /* traverse arguments */
    if (argv[i][0] == '-') {    /* -- if argument is an option */
      if (optarg) error(E_OPTARG);
      s = argv[i]+1;            /* get pointer */
      while (*s) {              /* traverse options */
        switch (*s++) {         /* evaluate option */
          default : error(E_OPTION, *(--s));    break;
        }                       /* set option variables */
        if (optarg && *s) { *optarg = s; optarg = NULL; break; }
      } }                       /* get option argument */
    else {                      /* -- if argument is no option */
      if (optarg) {             /* get option argument */
        *optarg = argv[i]; optarg = NULL; continue; }
      switch (k++) {            /* evaluate non-option */
        case  0: fn_maze = argv[i]; break;
        case  1: fn_prog = argv[i]; break;
        default: error(E_ARGCNT);   break;
      }                         /* note filenames */
    }
  }
  if (optarg) error(E_OPTARG);  /* check option argument */
  if (k < 2)  error(E_ARGCNT);  /* check number of arguments */
  printf("\n");                 /* terminate startup message */

  /* --- run hamster --- */
  srand((unsigned)time(NULL));  /* init. random number generator */
  start();                      /* start hamster */
  return 0;                     /* return 'ok' */
}  /* main() */