bridgit.c

数据挖掘中的bridgit算法的例子。 非常经典

  ||  (bi->moves[bi->curr] != bridge)) {
    bi->moves[bi->curr] = bridge;
    bi->mvcnt = bi->curr +1;    /* note the new bridge */
  }                             /* and adapt the move counter */
  bi->curr++;                   /* increment the move counter */
  r = bi_index(bi, col, row);   /* get the resistor index and */
  bi->states[r] = bridge;       /* set the state of the point */
  if (bi_player(bridge) & BI_HORZ) { v = 1e+10; h = 1e-10; }
  else                             { v = 1e-10; h = 1e+10; }
  n = bi->ptcnt >> 1;           /* get the new resistor values and */
  for (i = n; --i >= 0; ) {     /* traverse the mesh equations */
    o = mat_get(bi->horz, i,   r); /* adapt horizontal network */
    if (o != 0) mat_set(bi->horz, i,   r, (o > 0) ? h : -h);
    o = mat_get(bi->vert, i+n, r); /* adapt vertical   network */
    if (o != 0) mat_set(bi->vert, i+n, r, (o > 0) ? v : -v);
  }                             /* (open/close connections) */
}  /* bi_build() */

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

int bi_state (BRIDGIT *bi, int col, int row)
{                               /* --- get the state of a crossing */
  assert(bi);                   /* check the function arguments */
  assert(bi_cross(bi,col,row)); /* check for a correct crossing point */
  return bi->states[bi_index(bi, col, row)];
}  /* bi_state() */             /* return the state of the crossing */

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

int bi_undo (BRIDGIT *bi)
{                               /* --- undo a move */
  int    bridge;                /* the bridge to remove */
  int    i, n, r;               /* loop variables, resistor index */
  int    col, row;              /* coordinates of crossing point */
  double o;                     /* old resistor value */

  assert(bi);                   /* check the function arguments */
  if (bi->curr <= 0)            /* if there are no more moves, */
    return BI_NONE;             /* abort the function */
  bridge = bi_move(bi, --bi->curr);
  col    = bi_col(bridge);      /* get the bridge to remove and the */
  row    = bi_row(bridge);      /* coordinates of the crossing point */
  assert(bi_cross(bi,col,row)); /* check for a correct crossing point */
  r = bi_index(bi, col, row);   /* get the resistor index and */
  bi->states[r] = BI_NONE;      /* reset the state of the point */
  n = bi->ptcnt >> 1;           /* get the number of meshes and */
  for (i = n; --i >= 0; ) {     /* traverse the mesh equations */
    o = mat_get(bi->horz, i,   r); /* adapt horizontal network */
    if (o != 0) mat_set(bi->horz, i,   r, (o > 0) ? 1 : -1);
    o = mat_get(bi->vert, i+n, r); /* adapt vertical   network */
    if (o != 0) mat_set(bi->vert, i+n, r, (o > 0) ? 1 : -1);
  }                             /* (reset connections) */
  return bridge;                /* return the removed bridge */
}  /* bi_undo() */

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

int bi_redo (BRIDGIT *bi)
{                               /* --- redo a move */
  int bridge;                   /* the bridge to rebuild */

  assert(bi);                   /* check the function arguments */
  if (bi->curr >= bi->mvcnt)    /* if there are no more moves, */
    return BI_NONE;             /* abort the function */
  bridge = bi_move(bi,bi->curr);/* get the corresponding bridge */
  bi_build(bi, bridge);         /* and rebuild it */
  return bridge;                /* return the rebuilt bridge */
}  /* bi_redo() */

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

int bi_save (BRIDGIT *bi, FILE *file)
{                               /* --- save a bridg-it game */
  int i;                        /* loop variable */

  fprintf(file, "%d %d\n", bi->size, bi->curr);
  for (i = 0; i < bi->mvcnt; i++)
    fprintf(file, "%06x\n", bi->moves[i]);
  return ferror(file) ? -1 : 0; /* print all moves made and */
}  /* bi_save() */              /* return the write status */

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

BRIDGIT* bi_load (FILE *file)
{                               /* --- load a bridg-it game */
  int     size, cnt;            /* board size, move counter */
  unsigned int bridge;          /* to traverse the bridges */
  int     player;               /* player that built the bridge */
  int     row, col;             /* row and column of crossing point */
  BRIDGIT *bi;                  /* loaded game */

  if ((fscanf(file, "%d%d", &size, &cnt) != 2)
  ||  (size < 2)) return NULL;  /* read and check the board size */
  bi = bi_create(size);         /* and the current move number */
  if (!bi) return NULL;         /* and create a bridg-it game */
  bi_init(bi);                  /* initialize the bridg-it game */
  while (bi->mvcnt < bi->ptcnt){/* traverse the possible moves */
    if (fscanf(file, "%x", &bridge) != 1) {
      if (ferror(file)) { bi_delete(bi); return NULL; }
      break;                    /* read the next bridge and */
    }                           /* check for error and end of file */
    player = bridge & 0xff;     /* get the parameters of the bridge */
    col    = bi_col(bridge);    /* (the player that built the bridge */
    row    = bi_row(bridge);    /* and the coords. of the crossing) */
    if (((player != BI_HORZ) && (player != BI_VERT))
    ||  !bi_cross(bi, col, row) /* check for a valid player and */
    ||  (bridge >> 24 != 0)) {  /* for a valid crossing point */
      bi_delete(bi); return NULL; }
    bi->moves[bi->mvcnt++] = bridge;
  }                             /* store the loaded bridge */
  if (cnt > bi->mvcnt) {        /* check the current move number */
    bi_delete(bi); return NULL; }
  while (--cnt >= 0)            /* traverse the loaded moves */
    bi_redo(bi);                /* and execute them */
  return bi;                    /* return the loaded game */
}  /* bi_load() */

/*--------------------------------------------------------------------*/
#ifndef NDEBUG

void bi_show (BRIDGIT *bi, int player)
{                               /* --- show currents in network */
  int x, y, o;                  /* loop variables, offset */
  int nl;                       /* number of longitudinal resistors */
  int s;                        /* state of crossing point */

  nl = bi->size * bi->size;     /* get the number of long. resistors */
  if (player == BI_HORZ) {      /* if to show the horizontal network */
    for (y = 0; y < bi->size-1; y++) {
      for (o = y *bi->size, x = 0; x < bi->size; x++)
        printf("*-%5.3f-", fabs(vec_get(bi->sol, o +x)));
      printf("*\n ");           /* horizontal currents */
      for (x = bi->size-1; --x >= 0; ) printf("       |");
      printf("\n   ");          /* vertical connections */
      for (o = nl +y *(bi->size-1), x = 0; x < bi->size-1; x++)
        printf("   %5.3f", fabs(vec_get(bi->sol, o +x)));
      printf("\n ");            /* vertical currents */
      for (x = bi->size-1; --x >= 0; ) printf("       |");
      printf("\n");             /* vertical connections */
    }
    for (o = y *bi->size, x = 0; x < bi->size; x++)
      printf("*-%5.3f-", fabs(vec_get(bi->sol, o +x)));
    printf("*\n"); }            /* horizontal currents in last row */
  else if (player == BI_VERT) { /* if to show the vertical network */
    for (x = bi->size-1; --x >= 0; ) printf("    *   ");
    printf("    *\n    ");      /* first line (connection panel) */
    for (y = 0; y < bi->size; y++) {
      for (x = bi->size-1; --x >= 0; ) printf("|       ");
      printf("|\n  ");          /* vertical connections */
      for (o = y *bi->size, x = 0; x < bi->size-1; x++)
        printf("%5.3f   ",  fabs(vec_get(bi->sol, o +x)));
      printf("%5.3f\n    ", fabs(vec_get(bi->sol, o +x)));
      for (x = bi->size-1; --x >= 0; ) printf("|       ");
      printf("|\n    ");        /* vertical connections */
      if (y >= bi->size-1) break;
      for (o = nl +y *(bi->size-1), x = 0; x < bi->size-1; x++)
        printf("*-%5.3f-", fabs(vec_get(bi->sol, o +x)));
      printf("*\n    ");        /* horizontal currents */
    }
    for (x = bi->size-1; --x >= 0; ) printf("*       ");
    printf("*\n"); }          /* last line (connection panel) */
  else {                        /* if to show the bridges built */
    printf("    ");             /* (that is, the current board) */
    for (x = bi->size-1; --x >= 0; ) printf("oooooooo");
    printf("o\n");              /* print connection panel */
    for (x = 0; x < bi->size; x++) {
      if (bi->states[x] & BI_VERT) printf("    o   ");
      else                         printf("        ");
    }                           /* first part of vertical bridges */  
    printf("\n");               /* of vertical network (if present) */
    for (y = 0; y < bi->size; y++) {
      for (o = x = 0; x < bi->size; x++) {
        s = bi->states[y *bi->size +x];
        if      (s & BI_HORZ) printf("********");
        else if (s & BI_VERT) printf("*   o   ");
        else                  printf("*       ");
      }                         /* horz. bridges of horz. network */
      printf("*\n");            /* and 2nd part of vertical bridges */
      if (y >= bi->size-1) break;
      printf("*");              /* abort loop after last row */
      for (x = 0; x < bi->size; x++) {
        s = bi->states[y *bi->size +x];
        if (s & BI_VERT) printf("   o");
        else             printf("    ");
        if (x >= bi->size-1)    /* third part of vertical bridges */
          break;                /* of vertical network (if present) */
        s = bi->states[nl +y *(bi->size-1) +x];
        if (s & BI_HORZ) printf("   *");
        else             printf("    ");
      }                         /* first part of vertical bridges */
      printf("   *\n*   ");     /* of horizontal network (if present) */
      for (x = 0; x < bi->size-1; x++) {
        s = bi->states[nl +y *(bi->size-1) +x];
        if      (s & BI_VERT) printf("oooooooo");
        else if (s & BI_HORZ) printf("o   *   ");
        else                  printf("o       ");
      }                         /* horz. bridges of vertical network */
      printf("o   *\n*");       /* and 2nd part of vertical bridges */
      for (x = 0; x < bi->size; x++) {
        s = bi->states[(y+1) *bi->size +x];
        if (s & BI_VERT) printf("   o");
        else             printf("    ");
        if (x >= bi->size-1)    /* first part of vertical bridges */
          break;                /* of vertical network (if present) */
        s = bi->states[nl +y *(bi->size-1) +x];
        if (s & BI_HORZ) printf("   *");
        else             printf("    ");
      }                         /* third part of vertical bridges */
      printf("   *\n");         /* of horizontal network (if present) */
    }
    for (x = 0; x < bi->size; x++) {
      s = bi->states[y *bi->size +x];
      if (s & BI_VERT) printf("    o   ");
      else             printf("        ");
    }                           /* third part of vertical bridges */  
    printf("\n    ");           /* of vertical network (if present) */
    for (x = bi->size-1; --x >= 0; ) printf("oooooooo");
    printf("o\n");              /* print connection panel */
  }
}  /* bi_show() */

#endif