//========================================
// Valid CRC / Chess960 Position generator
//========================================
// Reference Implementation, (C) 2005 by
// Reinhard Scharnagl, Munich, Germany
//----------------------------------------
// Correction 2005-Feb-28 (GC-Nearness)
//========================================

#include < string.h>
#include < stdio.h>

#define TXT_LIM 160

static char FenZone[TXT_LIM];

// insert a symbol into FEN-String 
// -------------------------------
// color could be:
// col <  0 => not specified
// col == 0 => bright square
// col == 1 => dark square
void PlaceIntoFEN
  (int cntFree, char symbol, int fieldColor)
{
  for (int pos = 0, free = 0; ; ++pos) {
    if (fieldColor < 0 || ((fieldColor ^ pos) & 1)) {
      if (!FenZone[pos] && cntFree == free++) {
        FenZone[pos] = symbol;
        break;
      }
    }
  }
}

// generating of FEN strings
// -------------------------
// nr could be
// nr >= 0 creating Chess960 position (1 ... 960)
// nr <  0 creating CRC position    (1 ... 48000)
const char *GetFen(int nr)
{
  // knight distributions over 5 free squares
  static const int knight_pos[10] = {
     3, // xx--- (binary encoded)
     5, // x-x--
     9, // x--x-
    17, // x---x
     6, // -xx--
    10, // -x-x-
    18, // -x--x
    12, // --xx-
    20, // --x-x
    24  // ---xx
  };

  // clear the working area
  int bit, pos = TXT_LIM;
  while (--pos >= 0) { FenZone[pos] = '\0'; }

  // test whether CRC is requested
  bool isCRC = (nr <= 0);

  if (isCRC) {
    nr = -nr;
    bool q_first = ((nr % 2) != 0);
    nr /= 2;
    PlaceIntoFEN(nr % 5, q_first ? 'q' : 'a', 0);
    nr /= 5;
    PlaceIntoFEN(nr % 5, q_first ? 'a' : 'q', 1);
    nr /= 5;
  }

  PlaceIntoFEN(nr % 4, 'b', 0);
  nr /= 4;
  PlaceIntoFEN(nr % 4, 'b', 1);
  nr /= 4;
  PlaceIntoFEN(nr % 6, isCRC ? 'c' : 'q', -1);
  nr /= 6;
  pos = knight_pos[nr % 10];
  for (bit = 5; --bit >= 0; ) {
    if ((pos & (1 << bit)) != 0)
      PlaceIntoFEN(bit, 'n', -1);
  }

  PlaceIntoFEN(2, 'r', -1);
  PlaceIntoFEN(1, 'k', -1);
  PlaceIntoFEN(0, 'r', -1);

  int width = isCRC ? 10 : 8;
  char *pC = &FenZone[width];
  *pC++ = '/';
  for (pos = width; --pos >= 0; ) {
    *pC++ = 'p';
  }
  for (pos = 4; --pos >= 0; ) {
    *pC++ = '/';
    if (width >= 10) {
      *pC++ = '1';
    }
    *pC++ = (char)('0' + width % 10);
  }
  *pC++ = '/';
  for (pos = width; --pos >= 0; ) {
    *pC++ = 'P'; 
  }
  *pC++ = '/';
  for (pos = 0; pos < width; ++pos) {
    *pC++ = FenZone[pos] ^ ('a'^'A');
  }
  strcpy(pC, ' w KQkq - 0 1');

  return FenZone;
}

// check if FEN is valid for CRC
// -----------------------------
bool IsValidCRC(const char *pFen) 
{
  // to be avoided GC position
  static const char *gcArray = 'rnbqckabnr';
  // pawn covering pieces (like a rook)
  static const char *covNear = 'rcqk';
  // pawn covering pieces (like a bishop)
  static const char *covDiag = 'baqk';
  // pawn covering pieces (like a knight)
  static const char *covDist = 'nac';

  int size = (int)(strchr(pFen, '/') - pFen);
  int diff = 0;
  for (int n = size; --n >= 0; ) {
    // different to GC?
    if (pFen[n] != gcArray[n]) {
      ++diff;
    }
    // unprotected pawns?
    if (strchr(covNear, pFen[n]))
      continue;
    if ((n+1) < size && strchr(covDiag, pFen[n+1]))
      continue;
    if ((n-1) >=   0 && strchr(covDiag, pFen[n-1]))
      continue;
    if ((n+2) < size && strchr(covDist, pFen[n+2]))
      continue;
    if ((n-2) >=   0 && strchr(covDist, pFen[n-2]))
      continue;
    return false;
  }
  // GC-near position?
  if (diff < 3 && size == (int)strlen(gcArray)) {
    return false;
  }

  return true;
}

// test output
// -----------
int main(void)
{
  puts('\nfirst Chess960 positions');
  for (int nrFRC = 0; ++nrFRC <= 10; ) {
    printf('(%03d) %s\n',
      nrFRC, GetFen(nrFRC));
  }

  puts('\nfirst CRC positions');
  int cntValid = 0;
  for (int nrCRC = 0; ++nrCRC <= 48000; ) {
    const char *pFEN = GetFen(-nrCRC);
    bool valid = IsValidCRC(pFEN); 
    if (nrCRC <= 32) {
      printf('(%05d %s) %s\n',
        nrCRC, valid ? 'ok' : '--', pFEN);
    }
    if (valid) {
      ++cntValid;
    }
  }

  printf('\n%d valid CRC arrays\n', cntValid);

  return 0;
}