/* opt_bfs v0.1 - Core War optima number calculator by John Metcalf * using the bomb-free space method * Usage: opt_bfs coresize [modulo] */ #include #include #define MAXCORESIZE 65535 #define TOPX 20 int gcd( int a, int b ) { return !b ? a : gcd( b, a % b ); } int qcmp(const void *pa, const void *pb ) { const unsigned *a = pa; const unsigned *b = pb; if ( a[1] < b[1] ) return -1; if ( a[1] > b[1] ) return 1; return 0; } int optima(int step, int coresize) { int high, low, pos, score = coresize - 1; high = low = pos = step; while (pos) { pos = (pos + step) % coresize; if (pos > high) high = pos; if (pos < low) low = pos; score += coresize - high + low - 1; } return score; } int main(int argc, char *argv[]) { unsigned scores[MAXCORESIZE][2] = {0}; unsigned step, coresize, i, index=0, modulo=1; if (argc == 1) { printf("\nOPTIMA - Core War optima number calculator\n" "\nUsage: %s coresize [modulo]\n",argv[0]); return 0; } coresize = atoi(argv[1]); if (argc > 2) { modulo = atoi(argv[2]); } if (coresize%modulo != 0) { printf("\nERROR: modulo is not a factor of coresize\n"); return 1; } if (coresize > MAXCORESIZE) { printf("\nERROR: coresize out of range\n"); return 1; } for (step = modulo; step < (coresize + 1) / 2; step += modulo) { if (gcd(coresize, step) == modulo) { scores[index][0] = step; scores[index][1] = optima(step, coresize); index++; } } qsort(scores, index, sizeof scores[0], qcmp); printf("\n Step Score\n\n"); for (i = 0; i < index && i < TOPX; i++) { printf("%7u %7u\n", scores[i][0], scores[i][1]); } }