プラレールの直線レールと曲線レールを合わせて N 本使ってできる閉路は何通りあるか。
曲線レールは直線レールの長さを半径とする中心角 45 度の円弧とする。
ある閉路とそれを回転または裏返してできる閉路は同じと見なす。
これは平面上の線分と円弧の配置を数える問題である。実際にプラレールで組み立てることができなくてもよい。
例えば、レールが交差している場所があってもよい。レールだけなら多少歪ませれば組み立てられるが、列車を走らせるにはポイントレールや坂レールを使って平面交差や立体交差を作らなければならない。
更に、レールが重なっている場所があってもよい。曲線レールを 8 本使った円を 2 周して 16 本使ったことにしてよい。実際に 16 本使って円を 2 周させるとコイルになってしまい始点と終点を繋ぐことができない。
三谷先生のツイート
閉路の数が一致するまで三谷先生のプログラムを見ないで作った。座標の変化をまとめた配列が似ているのは偶然。
1: //------------------------------------------------------------------------------------------------ 2: // 3: // ファイル名 4: // plarail.c 5: // 6: // 作った人 7: // Makoto Kamada 8: // 9: // 更新した日 10: // 2019-06-15 11: // 12: // ウェブサイト 13: // https://stdkmd.net/plarail/ 14: // 15: //------------------------------------------------------------------------------------------------ 16: // 17: // タイトル 18: // プラレールの閉路の数え上げ 19: // 20: // 問題 21: // プラレールの直線レールと曲線レールを合わせて N 本使ってできる閉路は何通りあるか。 22: // 23: // 条件 24: // 曲線レールは直線レールの長さを半径とする中心角 45 度の円弧とする。 25: // ある閉路とそれを回転または裏返してできる閉路は同じと見なす。 26: // 27: // 参考 28: // 三谷先生のツイート 29: // https://twitter.com/jmitani/status/880070117635235840 30: // https://twitter.com/jmitani/status/1136228098314125313 31: // 32: //------------------------------------------------------------------------------------------------ 33: 34: #include <stdio.h> 35: #include <stdlib.h> 36: #include <string.h> 37: #include <math.h> 38: #include <time.h> 39: 40: //レールの座標 41: // 右が+x、下が+yの平面座標を用いる 42: // ┌→+x 43: // ↓ 44: // +y 45: // 直線レールはS、曲線レールは進行方向に対して右に曲がるものをR、左に曲がるものをLと書く 46: // Sは長さが2の線分、RとLは半径が2で中心角が45度の円弧とする 47: // 右を向いているとき 48: // Sは右に2進む 49: // Rは右にsqrt(2)、下に2-sqrt(2)進み、右に45度方向転換する 50: // Lは右にsqrt(2)、上に2-sqrt(2)進み、左に45度方向転換する 51: // ○ 52: // ／│ 53: // ／ │ 54: // ／ │ 55: // ●ＳＳＳＳＳＳＳＳＳ●ＲＲ────┐ ／ │ 56: // │ ＲＲ │ ／ │ 57: // │ ＲＲ│／ │ 58: // │ ● │ 59: // │ ／ ＬＬ │ 60: // │ ／ ＼ＬＬ │ 61: // │ ／ ＼ ＬＬ● 62: // │ ／ ＼ ／ 63: // │ ／ 64: // │／ 65: // ○ 66: // +-----+---------------------------+-------------------------------+-------------------------------+ 67: // | | S=0 | R=1 | L=2 | 68: // | h +----------+----------+-----+------------+------------+-----+------------+------------+-----+ 69: // | | dx | dy | dh | dx | dy | dh | dx | dy | dh | 70: // +-----+----------+----------+-----+------------+------------+-----+------------+------------+-----+ 71: // | 0 | 2 | 0 | 0 | sqrt(2) | 2-sqrt(2) | 45 | sqrt(2) | -2+sqrt(2) | -45 | 72: // | 45 | sqrt(2) | sqrt(2) | 0 | 2-sqrt(2) | sqrt(2) | 45 | sqrt(2) | 2-sqrt(2) | -45 | 73: // | 90 | 0 | 2 | 0 | -2+sqrt(2) | sqrt(2) | 45 | 2-sqrt(2) | sqrt(2) | -45 | 74: // | 135 | -sqrt(2) | sqrt(2) | 0 | -sqrt(2) | 2-sqrt(2) | 45 | -2+sqrt(2) | sqrt(2) | -45 | 75: // | 180 | -2 | 0 | 0 | -sqrt(2) | -2+sqrt(2) | 45 | -sqrt(2) | 2-sqrt(2) | -45 | 76: // | 225 | -sqrt(2) | -sqrt(2) | 0 | -2+sqrt(2) | -sqrt(2) | 45 | -sqrt(2) | -2+sqrt(2) | -45 | 77: // | 270 | 0 | -2 | 0 | 2-sqrt(2) | -sqrt(2) | 45 | -2+sqrt(2) | -sqrt(2) | -45 | 78: // | 315 | sqrt(2) | -sqrt(2) | 0 | sqrt(2) | -2+sqrt(2) | 45 | 2-sqrt(2) | -sqrt(2) | -45 | 79: // +-----+----------+----------+-----+------------+------------+-----+------------+------------+-----+ 80: // 座標を2*a+sqrt(2)*bの形で表現する 81: static const int coeff[3][8][5] = { 82: { //S 83: { 1, 0, 0, 0, 0 }, // 0 84: { 0, 1, 0, 1, 0 }, // 45 85: { 0, 0, 1, 0, 0 }, // 90 86: { 0, -1, 0, 1, 0 }, //135 87: { -1, 0, 0, 0, 0 }, //180 88: { 0, -1, 0, -1, 0 }, //225 89: { 0, 0, -1, 0, 0 }, //270 90: { 0, 1, 0, -1, 0 }, //315 91: }, 92: { //R 93: { 0, 1, 1, -1, 1 }, // 0 94: { 1, -1, 0, 1, 1 }, // 45 95: { -1, 1, 0, 1, 1 }, // 90 96: { 0, -1, 1, -1, 1 }, //135 97: { 0, -1, -1, 1, 1 }, //180 98: { -1, 1, 0, -1, 1 }, //225 99: { 1, -1, 0, -1, 1 }, //270 100: { 0, 1, -1, 1, 1 }, //315 101: }, 102: { //L 103: { 0, 1, -1, 1, -1 }, // 0 104: { 0, 1, 1, -1, -1 }, // 45 105: { 1, -1, 0, 1, -1 }, // 90 106: { -1, 1, 0, 1, -1 }, //135 107: { 0, -1, 1, -1, -1 }, //180 108: { 0, -1, -1, 1, -1 }, //225 109: { -1, 1, 0, -1, -1 }, //270 110: { 1, -1, 0, -1, -1 }, //315 111: }, 112: }; 113: 114: //文字 115: // S=0,R=1,L=2 116: static const char chr[4] = { 'S', 'R', 'L', 'X' }; 117: 118: // メイン 119: int main (int argc, char *argv[]) { 120: 121: //パラメータ 122: int numofRails = 8; //レールの数 123: char outputFileName[1024] = ""; //出力ファイル名 124: switch (argc) { 125: case 3: 126: if (sscanf (argv[2], "%1023[-().0-9A-Z_a-z~]", outputFileName) != 1) { 127: goto help; 128: } 129: case 2: 130: if (sscanf (argv[1], "%d", &numofRails) != 1 || 131: numofRails < 2 || 32 < numofRails) { //レールの数が2～32でない 132: goto help; 133: } 134: break; 135: default: 136: help: 137: printf ("usage: plarail <number-of-rails(8-32)> <output-file-name>\n"); 138: return 1; 139: } 140: 141: //計測開始 142: struct timespec startTime; 143: clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &startTime); 144: 145: //最上位の3進数のリストを作る 146: int (*ternaryList1)[8192] = calloc (8192 * (8 + 1), sizeof (ternaryList1[0][0])); //最上位の3進数のリスト 147: ternaryList1[0][0] = 0; //0桁 148: ternaryList1[0][1] = -1; 149: for (int d = 1; d <= 8; d++) { //最上位の桁数 150: int w = d << 1; //ビット数 151: int m = 0xffff >> (16 - w); //下位wビットが1 152: int *p = ternaryList1[d]; //d桁の3進数のリストの先頭 153: for (int n = 0; n <= m; n++) { //nはd桁の4進数 154: int x = (n >> 1) & n & 0x5555; //3を抽出する 155: if (x) { //3があるとき 156: n |= (x & -x) - 1; //一番右にある3の右側をすべて3にする 157: continue; 158: } 159: //nはd桁の3進数 160: for (int i = w - 2; 0 < i; i -= 2) { 161: if ((n & (m >> i)) < (n >> i)) { //下位w-iビットが上位w-iビットより若い 162: goto nextN; 163: } 164: } 165: x = ((n >> 1) & 0x5555) | ((n & 0x5555) << 1); //RとLを入れ替える 166: for (int i = w - 2; 0 <= i; i -= 2) { 167: if ((x & (m >> i)) < (n >> i)) { //RとLを入れ替えた下位w-iビットが元の上位w-iビットより若い 168: goto nextN; 169: } 170: } 171: //逆順にする 172: x = ((n & 0x3333) << 2) | ((n >> 2) & 0x3333); 173: x = ((x & 0x0f0f) << 4) | ((x >> 4) & 0x0f0f); 174: x = ((x << 8) | (x >> 8)) & 0xffff; 175: x >>= 16 - w; 176: for (int i = w - 2; 0 <= i; i -= 2) { 177: if ((x & (m >> i)) < (n >> i)) { //逆順にした下位w-iビットが元の上位w-iビットより若い 178: goto nextN; 179: } 180: } 181: x = ((x >> 1) & 0x5555) | ((x & 0x5555) << 1); //RとLを入れ替える 182: for (int i = w - 2; 0 <= i; i -= 2) { 183: if ((x & (m >> i)) < (n >> i)) { //逆順にしてRとLを入れ替えた下位w-iビットが元の上位w-iビットより若い 184: goto nextN; 185: } 186: } 187: *p++ = n; 188: nextN: 189: ; 190: } 191: *p = -1; //番兵 192: } 193: 194: //最上位以外の3進数のリストを作る 195: int *ternaryList2 = calloc (8192, sizeof (ternaryList2[0])); //最上位以外の3進数のリスト 196: { 197: int *p = ternaryList2; //8桁の3進数のリストの先頭 198: for (int n = 0x0000; n <= 0xffff; n++) { //nは8桁の4進数 199: int x = (n >> 1) & n & 0x5555; //3を抽出する 200: if (x) { //3があるとき 201: n |= (x & -x) - 1; //一番右にある3の右側をすべて3にする 202: continue; 203: } 204: //nは8桁の3進数 205: *p++ = n; 206: } 207: *p = -1; //番兵 208: } 209: 210: //8桁の3進数の閉路条件のハッシュテーブルを作る 211: // 下位8桁の3進数の方向条件と閉路条件の符号を反転する 212: // 下位8桁が0の3進数の閉路条件(xa,xb,ya,yb)のハッシュ関数を(((xa*7+xb)*7+ya)*7+yb)&(512-1)とする 213: // 下位8桁が0の3進数の方向条件(h0)毎に8個のハッシュテーブルを作る 214: // 下位8桁が0の3進数の方向条件と閉路条件に合う下位8桁を連結することで方向条件と閉路条件を満たす3進数を構成する 215: #define CIRCUIT_HASH_SIZE 512 216: #define CIRCUIT_LIST_SIZE 256 217: // circuitHashTable[h0][g][5*i]={n,-xa,-xb,-ya,-yb} 218: // [CIRCUIT_LIST_SIZE-1]はカウンタ。ハッシュテーブルを作るときだけ使うので邪魔にならないところに置く 219: int (*circuitHashTable)[CIRCUIT_HASH_SIZE][CIRCUIT_LIST_SIZE] = 220: calloc (CIRCUIT_LIST_SIZE * CIRCUIT_HASH_SIZE * 8, sizeof (circuitHashTable[0][0][0])); 221: for (int h0 = 0; h0 < 8; h0++) { 222: for (int g = 0; g < CIRCUIT_HASH_SIZE; g++) { 223: circuitHashTable[h0][g][CIRCUIT_LIST_SIZE - 1] = 0; //カウンタ 224: } 225: } 226: for (int n = 0x0000; n <= 0xffff; n++) { //nは8桁の4進数 227: int x = (n >> 1) & n & 0x5555; //3を抽出する 228: if (x) { //3があるとき 229: n |= (x & -x) - 1; //一番右にある3の右側をすべて3にする 230: continue; 231: } 232: //nは8桁の3進数 233: for (int h0 = 0; h0 < 8; h0++) { 234: //方向条件と閉路条件を計算する 235: int xa = 0; 236: int xb = 0; 237: int ya = 0; 238: int yb = 0; 239: int h = h0; 240: for (int i = 2 * 8 - 2; 0 <= i; i -= 2) { 241: const int *c = coeff[(int) (n >> i) & 3][h]; 242: xa += c[0]; 243: xb += c[1]; 244: ya += c[2]; 245: yb += c[3]; 246: h = (h + c[4]) & 7; 247: } 248: if (h == 0) { //方向条件 249: xa = -xa; 250: xb = -xb; 251: ya = -ya; 252: yb = -yb; 253: //ハッシュテーブルを更新する 254: int g = (((xa * 7 + xb) * 7 + ya) * 7 + yb) & (CIRCUIT_HASH_SIZE - 1); //ハッシュコード 255: int *p = circuitHashTable[h0][g]; 256: int i = p[CIRCUIT_LIST_SIZE - 1]; 257: p[i ] = n; 258: p[i + 1] = xa; 259: p[i + 2] = xb; 260: p[i + 3] = ya; 261: p[i + 4] = yb; 262: p[CIRCUIT_LIST_SIZE - 1] = i + 5; 263: } //if 方向条件 264: } //for h0 265: } //for n 266: for (int h0 = 0; h0 < 8; h0++) { 267: for (int g = 0; g < CIRCUIT_HASH_SIZE; g++) { 268: circuitHashTable[h0][g][circuitHashTable[h0][g][CIRCUIT_LIST_SIZE - 1]] = -1; //番兵 269: } 270: } 271: 272: //閉路の配列を確保する 273: // 8 10 12 14 16 18 20 22 24 26 28 30 32 レールの数 n 274: // 1 1 4 9 42 161 847 4739 29983 198683 1375928 9786630 35658701? 閉路の数 275: // 1 2 6 18 61 238 1058 5380 31012 201439 1465610 11879054 106724526 確保する数 floor(pow(0.03*n+0.8,n+0.7)) 276: unsigned long long *uniqueCircuitArray = 277: calloc ((size_t) floor (pow (0.03 * (double) numofRails + 0.8, (double) numofRails + 0.7)), 278: sizeof (unsigned long long)); //閉路の配列 279: 280: //閉路を作る 281: int circuitWidth = numofRails << 1; //閉路のビット数 282: unsigned long long circuitMask = 0xffffffffffffffffULL >> (64 - circuitWidth); //閉路のマスク。(1ULL<<circuitWidth)-1ULLは不可 283: unsigned long long invertedCircuitMask = ~circuitMask; 284: unsigned long long invertedCircuitMask1 = invertedCircuitMask | 0x000000000000ffffULL; 285: unsigned long long invertedCircuitMask2 = invertedCircuitMask | 0x00000000ffffffffULL; 286: unsigned long long circuitRSS = 1ULL << (circuitWidth - 2); //RSS...SSである閉路 287: unsigned long long circuitSRSS = 1ULL << (circuitWidth - 4); //SRSS...SSである閉路 288: unsigned long long circuitSSRSS = 1ULL << (circuitWidth - 6); //SSRSS...SSである閉路 289: size_t numofUniqueCircuits = 0; //重複を除いた閉路の数 290: int *tp3 = numofRails <= 24 ? ternaryList1[0] : ternaryList1[numofRails - 24]; 291: int *tp2 = numofRails <= 16 ? ternaryList1[0] : numofRails <= 24 ? ternaryList1[numofRails - 16] : ternaryList2; 292: int *tp1 = numofRails <= 8 ? ternaryList1[0] : numofRails <= 16 ? ternaryList1[numofRails - 8] : ternaryList2; 293: while (0 <= *tp3) { 294: unsigned long long n000 = (unsigned long long) *tp3++ << 48; //ビット63～48 295: while (0 <= *tp2) { 296: unsigned long long n00 = n000 | ((unsigned long long) *tp2++ << 32); //ビット47～32を連結する 297: //先頭がSでないときSを含むものを除く 298: if (circuitRSS <= n00) { 299: unsigned long long x = n00 | invertedCircuitMask2; 300: if ((~((x >> 1) | x) & 0x5555555555555555ULL) != 0) { //00がある 301: continue; 302: } 303: } 304: //先頭がSSでないときSSを含むものを除く 305: if (circuitSRSS <= n00) { 306: unsigned long long x = n00 | invertedCircuitMask2; 307: if ((~((x >> 3) | (x >> 2) | (x >> 1) | x) & 0x5555555555555555ULL) != 0) { //0000がある 308: continue; 309: } 310: } 311: //先頭がSSSでないときSSSを含むものを除く 312: if (circuitSSRSS <= n00) { 313: unsigned long long x = n00 | invertedCircuitMask2; 314: if ((~((x >> 5) | (x >> 4) | (x >> 3) | (x >> 2) | (x >> 1) | x) & 0x5555555555555555ULL) != 0) { //000000がある 315: continue; 316: } 317: } 318: while (0 <= *tp1) { 319: unsigned long long n0 = n00 | ((unsigned long long) *tp1++ << 16); //ビット31～16を連結する 320: //n0はnumofRails桁の先頭が2ではない下位8桁が0の3進数 321: //先頭がSでないときSを含むものを除く 322: if (circuitRSS <= n0) { 323: unsigned long long x = n0 | invertedCircuitMask1; 324: if ((~((x >> 1) | x) & 0x5555555555555555ULL) != 0) { //00がある 325: continue; 326: } 327: } 328: //先頭がSSでないときSSを含むものを除く 329: if (circuitSRSS <= n0) { 330: unsigned long long x = n0 | invertedCircuitMask1; 331: if ((~((x >> 3) | (x >> 2) | (x >> 1) | x) & 0x5555555555555555ULL) != 0) { //0000がある 332: continue; 333: } 334: } 335: //先頭がSSSでないときSSSを含むものを除く 336: if (circuitSSRSS <= n0) { 337: unsigned long long x = n0 | invertedCircuitMask1; 338: if ((~((x >> 5) | (x >> 4) | (x >> 3) | (x >> 2) | (x >> 1) | x) & 0x5555555555555555ULL) != 0) { //000000がある 339: continue; 340: } 341: } 342: //方向条件と閉路条件を計算する 343: int xa = 0; 344: int xb = 0; 345: int ya = 0; 346: int yb = 0; 347: int h = 0; 348: for (int i = circuitWidth - 2; 2 * 8 <= i; i -= 2) { //下位8桁はここにはない 349: const int *c = coeff[(int) (n0 >> i) & 3][h]; 350: xa += c[0]; 351: xb += c[1]; 352: ya += c[2]; 353: yb += c[3]; 354: h = (h + c[4]) & 7; 355: } 356: if (xa < -8 || 8 < xa || xb < -8 || 8 < xb || 357: ya < -8 || 8 < ya || yb < -8 || 8 < yb) { //閉路条件 358: continue; 359: } 360: for (int *p = circuitHashTable[h][(((xa * 7 + xb) * 7 + ya) * 7 + yb) & (CIRCUIT_HASH_SIZE - 1)]; 361: 0 <= *p; 362: p += 5) { 363: if (p[1] == xa && p[2] == xb && p[3] == ya && p[4] == yb) { //閉路条件 364: unsigned long long circuit = n0 | (unsigned long long) *p; //ビット15～0を連結する 365: //circuitはnumofRails桁の3進数で方向条件と閉路条件を満たしている 366: //先頭がSでないときSを含むものを除く 367: if (circuitRSS <= circuit) { 368: unsigned long long x = circuit | invertedCircuitMask; 369: x = ~((x >> 1) | x) & 0x5555555555555555ULL; //00を抽出する 370: if (x != 0) { //00がある 371: circuit |= (x & -x) - 1ULL; //一番右にある00の右側をすべて1にする 372: goto nextCircuit; 373: } 374: } 375: //先頭がSSでないときSSを含むものを除く 376: if (circuitSRSS <= circuit) { 377: unsigned long long x = circuit | invertedCircuitMask; 378: x = ~((x >> 3) | (x >> 2) | (x >> 1) | x) & 0x5555555555555555ULL; //0000を抽出する 379: if (x != 0) { //0000がある 380: circuit |= (x & -x) - 1ULL; //一番右にある0000の右側をすべて1にする 381: goto nextCircuit; 382: } 383: } 384: //先頭がSSSでないときSSSを含むものを除く 385: if (circuitSSRSS <= circuit) { 386: unsigned long long x = circuit | invertedCircuitMask; 387: x = ~((x >> 5) | (x >> 4) | (x >> 3) | (x >> 2) | (x >> 1) | x) & 0x5555555555555555ULL; //000000を抽出する 388: if (x != 0) { //000000がある 389: circuit |= (x & -x) - 1ULL; //一番右にある000000の右側をすべて1にする 390: goto nextCircuit; 391: } 392: } 393: //ローテートすると若くなるものを除く 394: { 395: unsigned long long x = circuit; 396: for (int i = circuitWidth - 2; 0 < i; i -= 2) { 397: if ((unsigned long long) (((x << (circuitWidth - i)) | (x >> i)) & circuitMask) < circuit) { 398: goto nextCircuit; 399: } 400: } 401: } 402: //RとLを入れ替えてローテートすると若くなるものを除く 403: { 404: unsigned long long x = circuit; 405: x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL); //RとLを入れ替える 406: if (x < circuit) { 407: goto nextCircuit; 408: } 409: for (int i = circuitWidth - 2; 0 < i; i -= 2) { 410: if ((unsigned long long) (((x << (circuitWidth - i)) | (x >> i)) & circuitMask) < circuit) { 411: goto nextCircuit; 412: } 413: } 414: } 415: //逆順に繋いだ閉路を作る 416: unsigned long long reversedCircuit; 417: { 418: //16ビットずつテーブルを使って反転するより速い 419: unsigned long long x = circuit; 420: //x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL); 421: x = ((x & 0x3333333333333333ULL) << 2) | ((x >> 2) & 0x3333333333333333ULL); 422: x = ((x & 0x0f0f0f0f0f0f0f0fULL) << 4) | ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL); 423: x = ((x & 0x00ff00ff00ff00ffULL) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffULL); 424: x = ((x & 0x0000ffff0000ffffULL) << 16) | ((x >> 16) & 0x0000ffff0000ffffULL); 425: x = (x << 32) | (x >> 32); 426: reversedCircuit = x >> (64 - circuitWidth); 427: } 428: //逆順に繋いでローテートすると若くなるものを除く 429: { 430: unsigned long long x = reversedCircuit; 431: if (x < circuit) { 432: goto nextCircuit; 433: } 434: for (int i = circuitWidth - 2; 0 < i; i -= 2) { 435: if ((unsigned long long) (((x << (circuitWidth - i)) | (x >> i)) & circuitMask) < circuit) { 436: goto nextCircuit; 437: } 438: } 439: } 440: //逆順に繋いでRとLを入れ替えてローテートすると若くなるものを除く 441: { 442: unsigned long long x = reversedCircuit; 443: x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL); //RとLを入れ替える 444: if (x < circuit) { 445: goto nextCircuit; 446: } 447: for (int i = circuitWidth - 2; 0 < i; i -= 2) { 448: if ((unsigned long long) (((x << (circuitWidth - i)) | (x >> i)) & circuitMask) < circuit) { 449: goto nextCircuit; 450: } 451: } 452: } 453: //重複を除いた閉路を記録する 454: uniqueCircuitArray[numofUniqueCircuits++] = circuit; 455: nextCircuit: 456: ; 457: } //if 閉路条件 458: } //for p 459: } //while tp1 460: tp1 = ternaryList2; 461: } //while tp2 462: tp2 = ternaryList2; 463: } //while tp3 464: 465: //計測終了 466: struct timespec endTime; 467: clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &endTime); 468: time_t sec = endTime.tv_sec - startTime.tv_sec; 469: long nsec = endTime.tv_nsec - startTime.tv_nsec; 470: if (nsec < 0) { 471: sec--; 472: nsec += 1000000000L; 473: } 474: double elapsedTime = (double) sec + (double) nsec / 1000000000.0; 475: 476: //閉路を出力する 477: // 閉路は昇順に見つかるのでソートする必要はない 478: if (outputFileName[0] != '\0') { 479: FILE *fp; 480: if (strcmp (outputFileName, "-") == 0) { 481: fp = stdout; 482: } else { 483: fp = fopen (outputFileName, "wb"); 484: if (fp == NULL) { 485: printf ("%s cannot be opened for writing.\n", outputFileName); 486: } 487: } 488: if (fp != NULL) { 489: for (size_t index = 0; index < numofUniqueCircuits; index++) { 490: unsigned long long circuit = uniqueCircuitArray[index]; 491: char text[256]; 492: char *p = text; 493: for (int i = circuitWidth - 2; 0 <= i; i -= 2) { 494: *p++ = chr[(int) (circuit >> i) & 3]; 495: } 496: *p = '\0'; 497: fprintf (fp, "%s\n", text); //比較するとき邪魔なので個々の閉路に番号を振らない 498: } 499: if (fp != stdout) { 500: fclose (fp); 501: printf ("%s has been updated.\n", outputFileName); 502: } 503: } 504: } 505: 506: //閉路の数と所要時間を出力する 507: printf ("It took %.3lf seconds to find %zd circuits made by connecting %d rails.\n", 508: elapsedTime, numofUniqueCircuits, numofRails); 509: 510: return 0; 511: } 512:
動作を確認した環境は Intel Core i7-3770 3.4GHz、RAM 8GB、Windows 10 Pro、Cygwin。
makoto@betelgeuse ~ $ gcc -finput-charset=utf-8 -fexec-charset=utf-8 -std=c11 -pedantic-errors -Wall -O3 -march=native -o plarail plarail.c makoto@betelgeuse ~ $ ./plarail 8 answer8.txt answer8.txt has been updated. It took 0.000 seconds to find 1 circuits made by connecting 8 rails. makoto@betelgeuse ~ $ ./plarail 10 answer10.txt answer10.txt has been updated. It took 0.000 seconds to find 1 circuits made by connecting 10 rails. makoto@betelgeuse ~ $ ./plarail 12 answer12.txt answer12.txt has been updated. It took 0.000 seconds to find 4 circuits made by connecting 12 rails. makoto@betelgeuse ~ $ ./plarail 14 answer14.txt answer14.txt has been updated. It took 0.016 seconds to find 9 circuits made by connecting 14 rails. makoto@betelgeuse ~ $ ./plarail 16 answer16.txt answer16.txt has been updated. It took 0.000 seconds to find 42 circuits made by connecting 16 rails. makoto@betelgeuse ~ $ ./plarail 18 answer18.txt answer18.txt has been updated. It took 0.000 seconds to find 161 circuits made by connecting 18 rails. makoto@betelgeuse ~ $ ./plarail 20 answer20.txt answer20.txt has been updated. It took 0.016 seconds to find 847 circuits made by connecting 20 rails. makoto@betelgeuse ~ $ ./plarail 22 answer22.txt answer22.txt has been updated. It took 0.031 seconds to find 4739 circuits made by connecting 22 rails. makoto@betelgeuse ~ $ ./plarail 24 answer24.txt answer24.txt has been updated. It took 0.203 seconds to find 29983 circuits made by connecting 24 rails. makoto@betelgeuse ~ $ ./plarail 26 answer26.txt answer26.txt has been updated. It took 3.281 seconds to find 198683 circuits made by connecting 26 rails. makoto@betelgeuse ~ $ ./plarail 28 answer28.txt answer28.txt has been updated. It took 19.500 seconds to find 1375928 circuits made by connecting 28 rails. makoto@betelgeuse ~ $ ./plarail 30 answer30.txt answer30.txt has been updated. It took 151.219 seconds to find 9786630 circuits made by connecting 30 rails. makoto@betelgeuse ~ $ ./plarail 32 answer32.txt answer32.txt has been updated. It took 448.578 seconds to find 35658701 circuits made by connecting 32 rails. makoto@betelgeuse ~ $
プログラムを更新。先頭 1～8 桁の 3 進数のリストを作るとき後で除かれることが明らかなものを予め除いておくようにした。30 本のとき 2 分台になった。
ログを追加。
公開。
プログラムを更新。先頭が S でないとき S を含むものを除く処理を閉路を作る途中に入れた。30 本のとき 30 分近くかかっていたが 5 分台になった。